我正在尝试尽可能高效地构建一个图,并且由于我不需要在运行时更改我的图,所以我选择了 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);
// ...
}
最佳答案
可以使用连续容器(例如 std::vector
)批量定义图形:
boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), edge_weight.data(), 13);
关于c++ - boost 图 CRS : bulk weights and Dijkstra,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23110118/