boost-graph 相关问题

Boost.Graph是一个包含通用图形组件和算法的C ++库。

我有一个带有自定义属性的增强图。我想复印一份。我按照以下方式尝试过，但出现了很多编译错误。这是我所做的：使用 BGType = boost::adjacency_list 我有一个带有自定义属性的增强图。我想复印一份。我按照以下方式尝试了，但出现了很多编译错误。这就是我所做的： using BGType = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, // Vertex Properties... vertexProps, // Edge Propereties... edgeProps, // Graph Properties graphProps>; vertexProps.h class vertexProps { public: explicit vertexProps(const std::string *moduleName = nullptr, const std::string *name = nullptr, long refPtr = 0 ) : _refPtr(refPtr), { _moduleName = moduleName ? *moduleName : ""; _name = name ? *name : ""; }; struct CustomVertexCopy { void operator()(const vertexProps& source_vertex, vertexProps& target_vertex) const { target_vertex._refPtr = source_vertex._refPtr; target_vertex._moduleName = source_vertex._moduleName; target_vertex._name = source_vertex._name; } edgeProps.h class edgeProps { public: explicit edgeProps(std::string name = "") : _name(name){}; std::string _name; }; struct CustomEdgeCopy { void operator()(const edgeProps& source_edge, edgeProps& target_edge) const { target_edge._name = source_edge._name; } }; 一些函数.cpp OnClick(BGType* bGraph) { // some code BGType* oldBg = new BGType; boost::copy_graph(bGraph, oldBg, boost::vertex_copy(CustomVertexCopy())); boost::copy_graph(bGraph, oldBg, boost::edge_copy(CustomEdgeCopy())); // some code } 我哪里错了？我还有一个疑问。如果 grpah 很大，这种深度复制会影响性能吗？如果是的话，有什么办法可以避免吗？命名参数是链接的，因此您可以在一个地方传递任意数量的参数： boost::copy_graph( // g1, g2, // boost::vertex_copy(CustomVertexCopy{}) // .edge_copy(CustomEdgeCopy{})); 请注意，.edge_copy 链接在 vertex_copy() 命名参数对象上。然后，仍然无法编译，因为自定义复制器应该采用描述符，而不是捆绑引用： struct CustomVertexCopy { BGType const& g1; BGType& g2; void operator()(BGType::vertex_descriptor v1, BGType::vertex_descriptor v2) const { vertexProps const& p1 = g1[v1]; vertexProps& p2 = g2[v2]; p2._refPtr = p1._refPtr; p2._moduleName = p1._moduleName; p2._name = p1._name; } }; 现在一切正常了：住在Coliru #include <boost/graph/adjacency_list.hpp> #include <boost/graph/copy.hpp> #include <boost/graph/graphviz.hpp> class vertexProps { public: explicit vertexProps(std::string const* mn = nullptr, std::string const* n = nullptr, long refPtr = 0) : _refPtr(refPtr) { _moduleName = mn ? *mn : ""; _name = n ? *n : ""; } std::string _moduleName; std::string _name; long _refPtr; }; class edgeProps { public: explicit edgeProps(std::string name = "") : _name(name){}; std::string _name; }; struct graphProps {}; using BGType = boost::adjacency_list< // boost::vecS, boost::vecS, boost::bidirectionalS, // vertexProps, edgeProps, graphProps>; struct CustomVertexCopy { BGType const& g1; BGType& g2; void operator()(BGType::vertex_descriptor v1, BGType::vertex_descriptor v2) const { vertexProps const& p1 = g1[v1]; vertexProps& p2 = g2[v2]; p2._refPtr = p1._refPtr; p2._moduleName = p1._moduleName; p2._name = p1._name; } }; struct CustomEdgeCopy { BGType const& g1; BGType& g2; void operator()(BGType::edge_descriptor e1, BGType::edge_descriptor e2) const { g2[e2]._name = g1[e1]._name; } }; int main() { BGType g1(3); std::string const names[] {"Hello", "world", "Goodbye", "moon", "Greetings", "Cosmos"}; g1[0] = vertexProps{names + 0, names + 1, 111}; g1[1] = vertexProps{names + 2, names + 3, 222}; g1[2] = vertexProps{names + 4, names + 5, 333}; add_edge(0, 1, edgeProps{"one"}, g1); add_edge(2, 0, edgeProps{"two"}, g1); BGType g2; boost::copy_graph( // g1, g2, // boost::vertex_copy(CustomVertexCopy{g1, g2}) // .edge_copy(CustomEdgeCopy{g1, g2})); boost::dynamic_properties dp; dp.property("node_id", get(boost::vertex_index, g2)); dp.property("moduleName", get(&vertexProps::_moduleName, g2)); dp.property("name", get(&vertexProps::_name, g2)); dp.property("ref", get(&vertexProps::_refPtr, g2)); dp.property("name", get(&edgeProps::_name, g2)); write_graphviz_dp(std::cout, g2, dp); } 打印 digraph G { 0 [moduleName=Hello, name=world, ref=111]; 1 [moduleName=Goodbye, name=moon, ref=222]; 2 [moduleName=Greetings, name=Cosmos, ref=333]; 0->1 [name=one]; 2->0 [name=two]; } 奖金简化！只需使属性可复制，就可以了，代码行数减少了 20 行，大约减少了 30% 的错误/悲观空间：住在Coliru #include <boost/graph/adjacency_list.hpp> #include <boost/graph/copy.hpp> #include <boost/graph/graphviz.hpp> class vertexProps { public: vertexProps(vertexProps const&) = default; vertexProps& operator=(vertexProps const&) = default; explicit vertexProps(std::string const* mn = nullptr, std::string const* n = nullptr, long refPtr = 0) : _refPtr(refPtr) { _moduleName = mn ? *mn : ""; _name = n ? *n : ""; } std::string _moduleName; std::string _name; long _refPtr; }; class edgeProps { public: edgeProps(edgeProps const&) = default; edgeProps& operator=(edgeProps const&) = default; explicit edgeProps(std::string name = "") : _name(name){}; std::string _name; }; struct graphProps {}; using BGType = boost::adjacency_list< // boost::vecS, boost::vecS, boost::bidirectionalS, // vertexProps, edgeProps, graphProps>; int main() { BGType g1(3); std::string const names[] {"Hello", "world", "Goodbye", "moon", "Greetings", "Cosmos"}; g1[0] = vertexProps{names + 0, names + 1, 111}; g1[1] = vertexProps{names + 2, names + 3, 222}; g1[2] = vertexProps{names + 4, names + 5, 333}; add_edge(0, 1, edgeProps{"one"}, g1); add_edge(2, 0, edgeProps{"two"}, g1); BGType g2; boost::copy_graph(g1, g2); boost::dynamic_properties dp; dp.property("node_id", get(boost::vertex_index, g2)); dp.property("moduleName", get(&vertexProps::_moduleName, g2)); dp.property("name", get(&vertexProps::_name, g2)); dp.property("ref", get(&vertexProps::_refPtr, g2)); dp.property("name", get(&edgeProps::_name, g2)); write_graphviz_dp(std::cout, g2, dp); } 仍在打印 digraph G { 0 [moduleName=Hello, name=world, ref=111]; 1 [moduleName=Goodbye, name=moon, ref=222]; 2 [moduleName=Greetings, name=Cosmos, ref=333]; 0->1 [name=one]; 2->0 [name=two]; }

c++ c++11 graph boost-graph

回答 1 投票 0

如何使用 boost::dijkstra_shortest_paths 计算具有“顶点权重”的最短路径？

我正在尝试计算具有顶点权重和边权重的图上的最短路径，但是 boost::dijkstra_shortest_paths 不计算通过顶点的权重。我试过了

c++ boost graph-theory dijkstra boost-graph

回答 2 投票 0

使用 BFS 查找 Boost BGL 图中所有可到达的顶点

我构建了一个boost BGL图：使用 vertex_t = std::variant; // 结构体使用edge_t = std::variant; // 枚举使用 Graph_t = bo...

c++ boost graph boost-graph

回答 1 投票 0

C++ Boost 图库：构建无向图搜索中访问的顶点向量？

据我所知，如何使用 BGL 来从已知的根节点调用图形的 DFS，我需要按照以下方式做一些事情：类 MyVisitor ：公共 boost::default_dfs_visitor {

c++ boost depth-first-search boost-graph

回答 2 投票 0

如何创建 C++ Boost 无向图并以深度优先搜索 (DFS) 顺序遍历它？

c++ boost-graph

回答 2 投票 0

如何使用 Boost.Graph 从有向图中提取子图？

我有一个非常大的图点文件，想要从给定的顶点提取子图。该子图应包含给定的顶点及其下方的所有顶点。 #包括我有一个非常大的图点文件，想要从给定的顶点提取子图。该子图应包含给定的顶点及其下方的所有顶点。 #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graphviz.hpp> #include <iostream> struct Vertex { std::string node; }; int main() { std::istringstream input( "digraph{" "0;1;2;3;4;5;6;7;8;9;" "0->1;1->2;2->3;2->6;3->4;4->5;5->8;6->7;6->5;7->8;8->9;" "}"); boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex> g(0); boost::dynamic_properties dp(boost::ignore_other_properties); dp.property("node_id", get(&Vertex::node, g)); boost::read_graphviz(input, g, dp); // delete everything that is not below Node 6 boost::write_graphviz(std::cout, g); } 在这个最小的示例中，给定的顶点的节点 ID 为 6。下图显示了我想要提取的内容：如何删除不低于节点6的节点和边？我尝试使用depth_first_search以某种方式解决这个问题，不幸的是没有成功。 ChatGPT 和文档也没有引导我实现目标。点文件转SVG图形： dot -Tsvg out.dot -o out.svg boost graph有一种将点文件读入boost graph的方法。从您指定的节点开始并执行 DFS 或 BFS。当您访问节点时标记它们。当搜索结束时，删除未标记的节点及其所有链接。

c++ graphviz boost-graph

回答 1 投票 0

C++ BGL Dijkstra 具有数字顶点 ID 和多个目标的最短路径

我一直在浏览这个网站上的帖子、图书馆的文档以及其他网站上的讨论和解释。然而，我很难理解 C++ Boost Graph 库是如何工作的......

c++ graph-theory shortest-path dijkstra boost-graph

回答 1 投票 0

为什么一个图（大约 10k 到 100k 条边和顶点）需要很长时间才能删除？

我正在编写一个程序来处理图形。我在循环中定义了一个图并向其添加了顶点和边（大约 4k 个顶点和 40k 个边）。但是当一轮循环结束时，需要很长的时间...

c++ graph boost-graph

回答 2 投票 0

Boost Graph Library 中的 PropertyGraph 概念

上下文我想重用这个离线标头中定义的 bidirectional_binary_tree 类的一些实现。此类不管理我需要的属性。为此我定义了一个