Clever Geek Handbook

Increase Graph Library - Adjacent_transforms function not found

I am trying to write an algorithm to (greedily) find the chromatic number of a graph. For this I need to be able to query adjacent vertices of a given vertex. My function is like this:

int Network::greedy_colouring() {
    // create an undirected graph with the vertices and edges of the first one
    UndirectedGraph g;
    copy_graph(network, g);

    int vertices_amount = num_vertices(g);
    // Assign the first color to first vertex
    std::map<std::string, int> vertex_colouring;
    vertex_pair_iterators vp = vertices(g);
    vertex_colouring[g[*vp.first].name] = 0;

    ++vp.first; // start from second vertex
    for (; vp.first != vp.second; ++vp.first)
        vertex_colouring[g[*vp.first].name] = -1;
    // A temporary array to store the available colors. True
    // value of available[cr] would mean that the color cr is
    // assigned to one of its adjacent vertices
    bool available[vertices_amount];
    for (int cr = 0; cr < vertices_amount; cr++)
        available[cr] = false;

    // Assign colors to remaining V-1 vertices
    vp = vertices(g); // reset to beginning
    ++vp.first; // start from second vertex
    for (; vp.first != vp.second; ++vp.first) {
        // Process all adjacent vertices and flag their colors
        // as unavailable
        for (std::pair<adjacency_it, adjacency_it> neighbours = boost::adjacent_vertices(g[*vp.first], g);
            neighbours.first != neighbours.second; ++neighbours.first)
            if (vertex_colouring[g[*neighbours.first].name] != -1)
                available[vertex_colouring[g[*neighbours.first].name]] = true;

        // Find the first available color
        int cr;
        for (cr = 0; cr < vertices_amount; cr++)
            if (available[cr] == false)
                break;

        vertex_colouring[g[*vp.first].name] = cr; // Assign the found color

        // Reset the values back to false for the next iteration
        neighbours = boost::adjacent_vertices(g[*vp.first], g); // reset to beginning

        for (; neighbours.first != neighbours.second; ++neighbours.first)
            if (vertex_colouring[g[*neighbours.first].name] != -1)
                available[vertex_colouring[g[*neighbours.first].name]] = false;
    }

    // print the result and find colour number
    unsigned colour_number = 0;
    for (std::map<std::string, int>::iterator it = vertex_colouring.begin(); it != vertex_colouring.end(); ++it) {
        std::cout << "Vertex " << it->first << " --->  Color " << it->second << std::endl;
        if (it->second > colour_number)
            colour_number = it->second;
    }
    return colour_number;
}

The error I'm getting is related to calling:

std::pair<adjacency_it, adjacency_it> neighbours = boost::adjacent_vertices(g[*vp.first],g)

Which gives the following compilation error: "error: there is no matching function to call" boost :: adjacency_iterator ... "(partial copy). Commenting out the code related to the adjacency_iterator allows it to compile, so I'm pretty sure this is the problem code. typedefs that are used in the function:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge > Graph;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge > UndirectedGraph; 

typedef std::pair<Vertex ,Vertex > vert_p;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
typedef boost::graph_traits<Graph>::in_edge_iterator in_edge_it;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
typedef boost::graph_traits<Graph>::edge_iterator edge_iter;
typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
typedef std::pair<vertex_iter, vertex_iter> vertex_pair_iterators;
typedef std::pair<in_edge_it, in_edge_it> edge_pair_iterators;
typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_it;

Can anyone give me an idea of ​​what I am doing wrong?

+3


source to share


1 answer


Two questions:

  • the first argument must be a vertex descriptor, not a set of properties. Change

    boost::adjacent_vertices(g[*vp.first], g)

    in

    boost::adjacent_vertices(*vp.first, g)

  • return typestd::pair<adjacency_iterator, adjacency_iterator>

    . However, you have defined adjacency_iterator

    as

    typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_it;

    when should it be

    typedef boost::graph_traits<UndirectedGraph>::adjacency_iterator adjacency_it;

Further notes:

  • Easier to work with separate iterators instead of vp.first

    and vp.second

    (use boost::tie

    to assign both at once)

  • You have an unsigned "poisonous" value in comparison, write it explicitly as

    if(it->second > static_cast<int>(colour_number))

    Or view the logic with possible values -1

    on the map.

  • it is probably very inefficient to keep an indexed colormap Vertex::name

    (which is a string). You should consider indexing on vertex_descriptor

    .

    Now, since your vertex model is using the vecS

    VertexContainer, you can actually take advantage of the fact that this handle is an integral index in the range [0, num_vertices(g))

    .

    So you can replace the map <> (which has poor memory locality) with vector<int>

    (where the vertex descriptor is a vector index).

    If you want to support other plotting models, you can let the caller pass in IndexMap

    , which maps the vertex descriptor to similar sequential indices. Many algorithms in BGL use this approach.

  • It is obvious that it bool[]

    can (should) be std::bitset

    or even std::vector<bool>

    . Boost has dynamic_bitset

    , which is probably the best thing here.

    (I will need to understand your algorithm a lot better. Perhaps the set of "accepted" colors will be even better. And implemented as an unsorted contiguous collection for speed, unless you expect the number of colors to get large enough that the ordered / hash lookup will be faster ( ?!).



Always create your code:

Live at Coliru 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/copy.hpp>
#include <iostream>

struct Vertex {
    std::string name;
};

struct Edge {
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge > Graph;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge > UndirectedGraph; 

Graph network;

int greedy_colouring() {
    using namespace boost;
    typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor  vertex_descriptor;
    static_assert(is_integral<vertex_descriptor>::value, "IndexMap not provided yet TODO");

    typedef boost::graph_traits<UndirectedGraph>::vertex_iterator    vertex_iter;
    typedef boost::graph_traits<UndirectedGraph>::adjacency_iterator adjacency_it;

    // create an undirected graph with the vertices and edges of the first one
    UndirectedGraph g;
    copy_graph(network, g);

    vertex_iter vit, vend;
    tie(vit, vend) = vertices(g);

    size_t const vertices_amount = num_vertices(g);
    std::vector<int> vertex_colouring(vertices_amount, -1);
    vertex_colouring[*vit] = 0; // Assign the first color to first vertex

    // A temporary array to store the available colors. 
    // - available[cr]:  assigned to one of its adjacent vertices
    std::vector<bool> available(vertices_amount, false);

    for (++vit; vit!=vend; ++vit)
    {
        // Process all adjacent vertices and flag their colors as unavailable
        adjacency_it neighbour, neighbour_end;
        for (tie(neighbour, neighbour_end) = adjacent_vertices(*vit, g); neighbour != neighbour_end; ++neighbour)
            if (vertex_colouring[*neighbour] != -1)
                available[vertex_colouring[*neighbour]] = true;

        // Find the first available color
        vertex_colouring[*vit] = distance(available.begin(), std::find(available.begin(), available.end(), false));

        // Reset the values back to false for the next iteration
        for (tie(neighbour, neighbour_end) = adjacent_vertices(*vit, g); neighbour != neighbour_end; ++neighbour)
            if (vertex_colouring[*neighbour] != -1)
                available[vertex_colouring[*neighbour]] = false;
    }

    // print the result and find colour number
    for (vertex_descriptor v = 0; v < vertices_amount; ++v)
        std::cout << "Vertex " << v << " --->  Color " << vertex_colouring[v] << std::endl;

    return *std::max_element(vertex_colouring.begin(), vertex_colouring.end());
}

int main() { }
+3


source






More articles:


All Articles