Boost图形库 - 找不到adjacent_vertices函数

Question

Boost图形库 - 找不到adjacent_vertices函数

3

我正在尝试编写一种算法，用于（贪心地）寻找图的色数。为此，我需要能够查询给定顶点的邻接顶点。

我的函数如下：

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;
}

我收到的错误与调用以下操作有关：

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

这导致编译错误：“错误：未找到匹配的函数调用‘boost :: adjacency_iterator ...”（部分复制）。注释与函数adjacency相关的代码使其编译，因此我确定这是有问题的代码。一些在函数中使用的typedef：

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;

有人能给我一个线索，我做错了什么吗？

- Zafi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sehe · Accepted Answer

两个问题：

the first argument needs to be a vertex descriptor, not the property bundle. Change

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

into

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

the return type is std::pair<adjacency_iterator, adjacency_iterator>. However, you defined adjacency_iterator as

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

when it needs to be

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

进一步说明：

It's easier to work with separate iterators instead of vp.first and vp.second (use boost::tie to assign both at once)
You have a "poisonous" unsigned value in your comparison, write it explicitly as
```
if(it->second > static_cast<int>(colour_number))
```
Or review the logic with possible -1 values in the map.
it's likely very inefficient to keep the colour map indexed by Vertex::name (which is a string). You should consider indexing by vertex_descriptor.

Now, since your vertex model uses vecS for the VertexContainer, you could actually use the fact that this descriptor is an integral index in the range [0, num_vertices(g)).

Therefore you can replace the map<> (which has bad memory locality) with a vector<int> (where the vertex descriptor is the vector index).

If you want to support other graph models, you can let the caller pass in an IndexMap that maps vertex-descriptor to similar consecutive indices. Lots of algorithms in the BGL use this approach.
Obviously, bool[] could (should) be std::bitset or even std::vector<bool>. Boost has the dynamic_bitset which is probably best here.

(I'd need to understand your algorithm a lot better. Perhaps a set of "taken" colour would be even better. And implemented as an unsorted contiguous collection for speed, unless you anticipate the number of colour to get big enough that an ordered/hash lookup would be faster (?!).

始终使您的代码自我包含：

演示：在 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() { }