update source to Ceph Pacific 16.2.2

[ceph.git] / ceph / src / boost / libs / graph / test / parallel_edges_loops_test.cpp

//=======================================================================
// Copyright 2007 Aaron Windsor
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

/*

This test is almost identical to all_planar_input_files_test.cpp
except that parallel edges and loops are added to the graphs as
they are read in.

This test needs to be linked against Boost.Filesystem.

*/

#define BOOST_FILESYSTEM_VERSION 3

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <utility>

#include <boost/property_map/property_map.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/filesystem.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/core/lightweight_test.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/is_straight_line_drawing.hpp>
#include <boost/graph/is_kuratowski_subgraph.hpp>
#include <boost/graph/chrobak_payne_drawing.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_detail/add_edge_visitors.hpp>

using namespace boost;

struct coord_t
{
    std::size_t x;
    std::size_t y;
};

template < typename Graph >
void read_dimacs(Graph& g, const std::string& filename)
{

    // every <vertex_stride>th vertex has a self-loop
    int vertex_stride = 5;

    // on vertices with self loops, there are between 1 and
    // <max_loop_multiplicity> loops
    int max_loop_multiplicity = 6;

    // every <edge_stride>th edge is a parallel edge
    int edge_stride = 7;

    // parallel edges come in groups of 2 to <max_edge_multiplicity> + 1
    int max_edge_multiplicity = 5;

    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
    typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
    std::vector< vertex_t > vertices_by_index;

    std::ifstream in(filename.c_str());

    long num_edges_added = 0;
    long num_parallel_edges = 0;

    while (!in.eof())
    {

        char buffer[256];
        in.getline(buffer, 256);
        std::string s(buffer);

        if (s.size() == 0)
            continue;

        std::vector< std::string > v;
        split(v, buffer, is_any_of(" \t\n"));

        if (v[0] == "p")
        {
            // v[1] == "edge"
            long num_vertices = boost::lexical_cast< long >(v[2].c_str());
            g = Graph(num_vertices);

            vertex_iterator_t vi, vi_end;
            long count = 0;
            long mult_count = 0;
            for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
            {
                if (count % vertex_stride == 0)
                {
                    for (int i = 0;
                         i < (mult_count % max_loop_multiplicity) + 1; ++i)
                    {
                        add_edge(*vi, *vi, g);
                    }
                    ++mult_count;
                }
                ++count;
            }

            std::copy(vertices(g).first, vertices(g).second,
                std::back_inserter(vertices_by_index));
        }
        else if (v[0] == "e")
        {
            add_edge(
                vertices_by_index[boost::lexical_cast< long >(v[1].c_str())],
                vertices_by_index[boost::lexical_cast< long >(v[2].c_str())],
                g);

            if (num_edges_added % edge_stride == 0)
            {
                for (int i = 0;
                     i < (num_parallel_edges % max_edge_multiplicity) + 1; ++i)
                {
                    add_edge(vertices_by_index[boost::lexical_cast< long >(
                                 v[1].c_str())],
                        vertices_by_index[boost::lexical_cast< long >(
                            v[2].c_str())],
                        g);
                }
                ++num_parallel_edges;
            }
            ++num_edges_added;
        }
    }
}

struct face_counter : planar_face_traversal_visitor
{

    face_counter() : m_num_faces(0) {}

    void begin_face() { ++m_num_faces; }

    long num_faces() { return m_num_faces; }

private:
    long m_num_faces;
};

int test_graph(const std::string& dimacs_filename)
{

    typedef adjacency_list< listS, vecS, undirectedS,
        property< vertex_index_t, int >, property< edge_index_t, int > >
        graph;

    typedef graph_traits< graph >::edge_descriptor edge_t;
    typedef graph_traits< graph >::edge_iterator edge_iterator_t;
    typedef graph_traits< graph >::vertex_iterator vertex_iterator_t;
    typedef graph_traits< graph >::edges_size_type e_size_t;
    typedef graph_traits< graph >::vertex_descriptor vertex_t;
    typedef edge_index_update_visitor<
        property_map< graph, edge_index_t >::type >
        edge_visitor_t;

    vertex_iterator_t vi, vi_end;
    edge_iterator_t ei, ei_end;

    graph g;
    read_dimacs(g, dimacs_filename);

    // Initialize the interior edge index
    property_map< graph, edge_index_t >::type e_index = get(edge_index, g);
    e_size_t edge_count = 0;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        put(e_index, *ei, edge_count++);

    // Initialize the interior vertex index - not needed if the vertices
    // are stored with a vecS
    /*
    property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g);
    v_size_t vertex_count = 0;
    for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
      put(v_index, *vi, vertex_count++);
    */

    // This edge_updater will automatically update the interior edge
    // index of the graph as edges are created.
    edge_visitor_t edge_updater(get(edge_index, g), num_edges(g));

    // The input graph may not be maximal planar, but the Chrobak-Payne straight
    // line drawing needs a maximal planar graph as input. So, we make a copy of
    // the original graph here, then add edges to the graph to make it maximal
    // planar. When we're done creating a drawing of the maximal planar graph,
    // we can use the same mapping of vertices to points on the grid to embed
    // the original, non-maximal graph.
    graph g_copy(g);

    // Add edges to make g connected, if it isn't already
    make_connected(g, get(vertex_index, g), edge_updater);

    std::vector< graph_traits< graph >::edge_descriptor > kuratowski_edges;

    typedef std::vector< std::vector< edge_t > > edge_permutation_storage_t;
    typedef boost::iterator_property_map< edge_permutation_storage_t::iterator,
        property_map< graph, vertex_index_t >::type >
        edge_permutation_t;

    edge_permutation_storage_t edge_permutation_storage(num_vertices(g));
    edge_permutation_t perm(
        edge_permutation_storage.begin(), get(vertex_index, g));

    // Test for planarity, computing the planar embedding or the kuratowski
    // subgraph.
    if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
            boyer_myrvold_params::embedding = perm,
            boyer_myrvold_params::kuratowski_subgraph
            = std::back_inserter(kuratowski_edges)))
    {
        std::cerr << "Not planar. ";
        BOOST_TEST(is_kuratowski_subgraph(
            g, kuratowski_edges.begin(), kuratowski_edges.end()));

        return 0;
    }

    // If we get this far, we have a connected planar graph.
    make_biconnected_planar(g, perm, get(edge_index, g), edge_updater);

    // Compute the planar embedding of the (now) biconnected planar graph
    BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = perm));

    // If we get this far, we have a biconnected planar graph
    make_maximal_planar(
        g, perm, get(vertex_index, g), get(edge_index, g), edge_updater);

    // Now the graph is triangulated - we can compute the final planar embedding
    BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = perm));

    // Make sure Euler's formula holds
    face_counter vis;
    planar_face_traversal(g, perm, vis, get(edge_index, g));

    BOOST_TEST(num_vertices(g) - num_edges(g) + vis.num_faces() == 2);

    // Compute a planar canonical ordering of the vertices
    std::vector< vertex_t > ordering;
    planar_canonical_ordering(g, perm, std::back_inserter(ordering));

    BOOST_TEST(ordering.size() == num_vertices(g));

    typedef std::vector< coord_t > drawing_storage_t;
    typedef boost::iterator_property_map< drawing_storage_t::iterator,
        property_map< graph, vertex_index_t >::type >
        drawing_map_t;

    drawing_storage_t drawing_vector(num_vertices(g));
    drawing_map_t drawing(drawing_vector.begin(), get(vertex_index, g));

    // Compute a straight line drawing
    chrobak_payne_straight_line_drawing(
        g, perm, ordering.begin(), ordering.end(), drawing);

    std::cerr << "Planar. ";
    BOOST_TEST(is_straight_line_drawing(g, drawing));

    return 0;
}

int main(int argc, char* argv[])
{

    std::string input_directory_str = "planar_input_graphs";
    if (argc > 1)
    {
        input_directory_str = std::string(argv[1]);
    }

    std::cout << "Reading planar input files from " << input_directory_str
              << std::endl;

    filesystem::path input_directory
        = filesystem::system_complete(filesystem::path(input_directory_str));
    const std::string dimacs_extension = ".dimacs";

    filesystem::directory_iterator dir_end;
    for (filesystem::directory_iterator dir_itr(input_directory);
         dir_itr != dir_end; ++dir_itr)
    {

        if (dir_itr->path().extension() != dimacs_extension)
            continue;

        std::cerr << "Testing " << dir_itr->path().leaf() << "... ";
        BOOST_TEST(test_graph(dir_itr->path().string()) == 0);

        std::cerr << std::endl;
    }

    return boost::report_errors();
}