将 EdgeList 作为 unordered_set 存储在 Boost Graph Library 上

Question

我正在重现一个科学实验，我需要将图的边集存储为 unordered_set。我正在尝试使用 BGL adjacency_graph，我认为最后一个参数将是 hash_setS 而不是 listS。但是当我这样做时，我的程序无法运行。我在这里看到了一个类似的问题，其中有人说将结构数据调整为 BGL 的 EdgeListGraph 模型，但我什至不知道如何做到这一点。

有人可以帮忙吗？谢谢。

Answer 1

using namespace std;

typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty, boost::hash_setS> Graph;

int main()
{

ifstream arquivo_in ("shrd150-3.dis");
ofstream arquivo_out ("matriz.txt");

int numero, j, i;
Graph g(15);
EdgeWeightProperty e;
enum { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O };
const char name[] = "ABCDEFGHIJKLMNO";

boost::property_map<Graph, vertex_index_t>::type
vertex_id = get(vertex_index, g);
boost::property_map<Graph, edge_weight_t>::type
trans_delay = get(edge_weight, g);

j = 1;

for(i = 0; i < 15; ++i)
    Graph::vertex_descriptor i = boost::add_vertex(g);


for(j = 1; !arquivo_in.eof(); ++j)
{
    for(i = 0; i < j; ++i)
    {
        arquivo_in >> numero;
        e = numero;
        boost::add_edge(i, j, e, g);
    }
}

我不确定是否存储为 hash_set，但我会尝试一种方法来检查冲突。再次感谢！

Answer 2

我不知道为什么你需要“unordered_map”存储（你从未提到过）。但既然你说：

我不确定是否存储为 hash_set，但我会尝试一种方法来检查冲突

我的印象是您只是想防止重复的边缘。在这种情况下，只需使用

setS

作为

OutEdgeList

容器选择器即可。

此容器控制如何存储每个顶点的出边。如果它们是唯一的，那么根据定义，图形将不包含重复的边。

注意，如果图形模式为

undirectedS

，则Boost Graph Library将对源/目标顶点进行排序，使得

(0,1)

和

(1,0)

边在这里等效/

演示

*住在 Coliru **

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

typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty, boost::hash_setS> Graph;

int main()
{
    Graph g(15);

    assert( add_edge(0,1,g).second);
    assert( add_edge(1,2,g).second);
    assert( add_edge(0,2,g).second);
    assert( add_edge(0,3,g).second);
    assert(!add_edge(3,0,g).second);
}

Answer 3

如果需要单独存储边缘以进行进一步处理，可以使用

boost::unordered_set<edge_desc>

通过包括

#include <boost/unordered_set.hpp>

BGL 文档此处。