Boost 图形库 - adjacent_vertices 未找到函数

Question

我正在尝试编写一个算法来（贪婪地）找到图形的色数。为此，我需要能够查询给定顶点的相邻顶点。我的功能如下：

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)

这会产生以下编译错误："error: no matching function for call to ‘boost::adjacency_iterator ... "（部分复制）。注释掉与函数邻接相关的代码可以让它编译，所以我确定这是有问题的代码。函数中使用的一些类型定义：

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;

谁能告诉我我做错了什么？

Answer 1

两个问题：

第一个参数需要是顶点描述符，而不是属性包。变化

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

进入

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

return type is std::pair<adjacency_iterator, adjacency_iterator>。但是，您将 adjacency_iterator 定义为

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

需要的时候

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

进一步说明：

使用单独的迭代器比使用 vp.first 和 vp.second 更容易（使用 boost::tie 一次分配）
你的比较中有一个"poisonous"无符号值，明确写为
```
if(it->second > static_cast<int>(colour_number))
```
或查看地图中可能具有 -1 个值的逻辑。
用 Vertex::name（字符串）索引颜色图可能效率很低。您应该考虑按 vertex_descriptor 建立索引。

现在，由于您的顶点模型使用 vecS 作为 VertexContainer，您实际上可以使用这个描述符是 [0, num_vertices(g)).
范围内的整数索引这一事实
因此您可以用 vector<int>（其中顶点描述符是向量索引）替换 map<>（它的内存局部性不好）。

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.
显然，bool[] 可以（应该）是 std::bitset 甚至 std::vector<bool>。 Boost 有 dynamic_bitset ，这可能是这里最好的。

(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 (?!).

始终使您的代码独立：

直播On 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() { }

Boost 图形库 - adjacent_vertices 未找到函数

Boost graph library - adjacent_vertices function not found

c++

boost

boost-graph

adjacency-list