c++ - 如何从提升图列表容器中查看顶点/边

Question

我正在尝试使用 listS 作为顶点/边容器，以便我可以安全地移除边。但是，我遇到了一个问题——我不知道如何查看我的顶点或边!当我尝试遍历它们并将它们打印出来时，出于某种原因它只会打印出它们的地址。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <utility>

using namespace std;

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits <Graph>::edge_iterator edgeIt;
typedef boost::graph_traits<Graph>::vertex_iterator vertexIt;
typedef map<vertex_t,size_t> IndexMap;

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

    Graph g;

    IndexMap mapIndex;

    vertex_t v0 = boost::add_vertex(g);
    vertex_t v1 = boost::add_vertex(g);
    vertex_t v2 = boost::add_vertex(g);
    vertex_t v3 = boost::add_vertex(g);
    mapIndex[v0] = 0;
    mapIndex[v1] = 1;
    mapIndex[v2] = 2;
    mapIndex[v3] = 3;
    boost::add_edge(v0,v2,g);
    boost::add_edge(v1,v3,g);
    boost::add_edge(v1,v0,g);


    for(pair<vertexIt,vertexIt> vi = boost::vertices(g); vi.first != vi.second; ++vi.first) {
        cout << *vi.first << endl;
    }

    for(pair<edgeIt,edgeIt> ei = boost::edges(g); ei.first != ei.second; ++ei.first) {
        cout << source(*ei.first, g) << " -> " << target(*ei.first, g) << endl;
        cout << *ei.first << endl;
    }
}

输出是:

0x7f9409404b10
0x7f9409404b70
0x7f9409404c00
0x7f9409404c40
0x7f9409404b10 -> 0x7f9409404c00
(0x7f9409404b10,0x7f9409404c00)
0x7f9409404b70 -> 0x7f9409404c40
(0x7f9409404b70,0x7f9409404c40)
0x7f9409404b70 -> 0x7f9409404b10
(0x7f9409404b70,0x7f9409404b10)

如果我使用 vecS 而不是 listS，它工作正常，但是在删除顶点时我遇到了麻烦。那么如何使用 listS 查看边/顶点呢？

编辑:解决方案

解决方案 1:

使用结构体来存储属性:

struct vertex {
    int id;
}

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, vertex> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits <Graph>::edge_iterator edgeIt;
typedef boost::graph_traits<Graph>::vertex_iterator vertexIt;
typedef map<vertex_t,size_t> IndexMap;

//MAKE YOUR GRAPH
...
//

//Assign vertex IDs
int currentID = 0;
for(pair<vertexIt,vertexIt> it = boost::vertices(g); it.first != it.second; ++it.first) {
    g[*it.first].id = currentID++;
}

//Access them when displaying edges:
for(pair<vertexIt,vertexIt> it = boost::vertices(g); it.first != it.second; ++it.first) {
    cout << g[*it.first].id << endl;
}

//Access them when displaying vertices:
for(pair<edgeIt,edgeIt> it = boost::edges(g); it.first != it.second; ++it.first) {
    cout << g[source(*it.first,g)].id << " " << g[target(*it.first,g)].id << endl;
}

解决方案 2:

使用属性映射(从我的第一个代码继续)

for(pair<vertexIt,vertexIt> vi = boost::vertices(g); vi.first != vi.second; ++vi.first) {
    cout << mapIndex[*vi.first] << endl;
}

for(IndexMap::iterator it = mapIndex.begin(); it != mapIndex.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

Answer 1

Boost中的顶点和边数据类型抽象为descriptors .它们或多或少是指针。

当使用vecS时，描述符是size_t索引，它们对应的顶点和边索引图默认是可用的。如果你想用 listS 为你的边和顶点创建一个整数索引，你必须自己创建它。

我认为以类似于 Boost 的方式执行此操作的一个好方法是这样的。

typedef std::map<vertex_descriptor,size_t> StdVertexIndexMap;
StdVertexIndexMap viMap;
typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
VertexIndexMap v_index(viMap);
vertex_iterator vi,ve;
size_t i = 0;
for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){
    boost::put(v_index,*vi,i);
    ++i;
}

与边类似。看我的old question对于上下文。将它包装在 boost::associative_property_map 或类似的东西中是 Boost 方式，以便使用 boost::get 和 boost::put 将正常工作。

如果您不打算在提升算法中使用它，您可以只使用一个简单的 std::map。