c++ - boost 图 CRS : bulk weights and Dijkstra

Question

我正在尝试尽可能高效地构建一个图，并且由于我不需要在运行时更改我的图，所以我选择了 boost::compressed_sparse_row_graph。现在问题很简单:如何为边添加权重并调用 boost::dijkstra_shortest_paths？

到目前为止，我已经完成了创建图表的工作，但我不知道如何继续。

我的要求是:尽量少浪费内存和时间。我面临着许多节点可能达到 10^6 的图表。我正在关注这个 wiki entry，但我担心 property maps、index maps & Co.，正如我在 wiki 中看到的那样，会给我的程序带来额外的负担。

您认为有什么方法可以最大限度地减少内存占用吗？

感谢您的帮助!

// Properties: weights
typedef boost::property<boost::edge_weight_t, int> edge_weight;

// The graph itself as a compressed sparse row matrix
typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, boost::no_property, edge_weight> boost_graph;

// Vertex iterator
typedef boost::graph_traits<boost_graph>::vertex_iterator vertex_iterator;

// Edge iterator
typedef boost::graph_traits<boost_graph>::edge_iterator edge_iterator;

// Adjacent nodes iterator
typedef boost::graph_traits<boost_graph>::adjacency_iterator adjacency_iterator;
typedef boost::graph_traits<boost_graph>::out_edge_iterator  outward_iterator;
typedef boost::graph_traits<boost_graph>::in_edge_iterator   inward_iterator;

int main(int argc, const char * argv[])
{
    std::vector<std::pair<std::size_t, std::size_t>> graph_edges;
    std::vector<int>                                 edge_weight;

    graph_edges.push_back(std::make_pair( 0,  1)); edge_weight.push_back(1);
    graph_edges.push_back(std::make_pair( 0,  3)); edge_weight.push_back(2);
    graph_edges.push_back(std::make_pair( 1,  4)); edge_weight.push_back(2);
    graph_edges.push_back(std::make_pair( 2,  4)); edge_weight.push_back(3);
    graph_edges.push_back(std::make_pair( 3,  4)); edge_weight.push_back(1);
    graph_edges.push_back(std::make_pair( 4,  5)); edge_weight.push_back(1);
    graph_edges.push_back(std::make_pair( 4,  6)); edge_weight.push_back(5);
    graph_edges.push_back(std::make_pair( 5,  7)); edge_weight.push_back(4);
    graph_edges.push_back(std::make_pair( 7,  8)); edge_weight.push_back(1);
    graph_edges.push_back(std::make_pair( 8,  9)); edge_weight.push_back(3);
    graph_edges.push_back(std::make_pair( 8, 11)); edge_weight.push_back(2);
    graph_edges.push_back(std::make_pair( 8, 12)); edge_weight.push_back(3);
    graph_edges.push_back(std::make_pair( 9, 10)); edge_weight.push_back(2);
    graph_edges.push_back(std::make_pair(12, 10)); edge_weight.push_back(4);

    // Create the graph
    boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), 13);
    // ...

}

Answer 1

可以使用连续容器(例如 std::vector)批量定义图形:

    boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), edge_weight.data(), 13);