如何将图表读入 Boost 图表库中的邻接矩阵?
How Can I Read in a Graph to an Adjacency Matrix In the Boost Graph Library?
在 boost 图形库中,有两个流行的函数可以从文件中读取图形:
boost::read_graphviz()
, and boost::read_graphml()
, for the GraphViz and the GraphML format,分别
现在两者都通读为任何类型的 boost::adjacency_list<...>
,因为它们是 Mutable Graph 概念的模型:
#include <string>
#include <fstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graphml.hpp>
#include <boost/graph/graph_traits.hpp>
template <typename GraphType>
GraphType load(std::string filename, std::string format) {
GraphType g(0);
std::ifstream t(filename.c_str());
boost::dynamic_property dp(boost::ignore_other_properties);
if (format == "graphml")
boost::read_graphml(t, g, dp);
else
boost::read_graphviz(t, g, dp);
return g;
}
如果你要测试
load<boost::adjacency_matrix<boost::undirectedS> >("my_file.gv", "graphviz");
你可能会得到类似
的东西
Assertion failed: (false), function add_vertex, file /usr/local/include/boost/graph/adjacency_matrix.hpp, line 966.
Abort trap: 6
那么我怎样才能包括读取 boost::adjacency_matrix<...>
的可能性,最好不必从中间邻接列表复制图形,如 in this SO post 所述(图形可能非常大) .
我不明白的是,为了复制,(复制目标)图apparently 也必须是一个可变图,所以我们怎么能然后复制到邻接矩阵?而不是读成一个?
感谢您的帮助!
备注
boost/graph/graphml.hpp
库不是 header-only 并且需要链接,例如当 compiling/linking 时直接从 CLI 附加 -lboost_graph
,如
g++ -lboost_graph my_file.cc
关于copy_graph
What I don't understand is, that for copying, the (copy target) graph apparently also has to be a Mutable Graph, so how can we then copy to an adjacency matrix? And not read into one?
我同意。那没有意义。看起来 copy_graph
应该不起作用 或 文档化的概念要求已过时。
也许它总是过度约束,或者专门为 adjacency_matrix
添加了专业化。
粗略地看一眼就知道它可能被过度约束了,因为显然 adjacency_matrix 不存在 specializations/overloads。
在我们测试之前,让我们看一下断言。
关于断言
断言源于此:
template < typename D, typename VP, typename EP, typename GP, typename A >
inline typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor
add_vertex(adjacency_matrix< D, VP, EP, GP, A >& g)
{
// UNDER CONSTRUCTION
BOOST_ASSERT(false);
return *vertices(g).first;
}
如您所见,这已经是一个正在规划更多灵活性的领域。如果您保留足够的 space,您似乎可以阅读图表。
可能已经为 copy_graph
提供了相同的功能(因为当容量已经足够时,只是避免了 add_vertex
;即使 add_vertex
在技术上仍然是(概念上) 是必需的,它可能并不总是。
检验假设
让我们来测试一下。看看我们是否真的可以从邻接表复制到矩阵中:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
using boost::vecS;
using D = boost::undirectedS¹;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;
int main() {
{ L list(0); M matrix(20); copy_graph(matrix, list); } // okay
{ L list(0); M matrix(20); copy_graph(list, matrix); } // okay
{ L list(1); M matrix(1); copy_graph(list, matrix); } // ASSERTS
{ L list(1); M matrix(20); copy_graph(list, matrix); } // ASSERTS
}
(¹ 方向性实际上并没有什么不同,我测试了)
我们的谜语有了答案。我们不能实际复制。
它确实可以编译,但如果没有断言则不会 运行。
现在,您可能认为您可以 #define NDEBUG
并压制断言。然而,看看上面的代码,很明显你 不能 期望它起作用,因为它总是 return 顶点 0
:
#define NDEBUG
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/graph_utility.hpp>
using boost::vecS;
using D = boost::undirectedS;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;
int main() {
L list(5);
M matrix(10);
add_edge(1, 4, list);
add_edge(3, 1, list);
copy_graph(list, matrix);
print_graph(list, std::cout << "\nlist:");
print_graph(matrix, std::cout << "\nmatrix:");
}
版画
list:0 -->
1 --> 4
2 -->
3 --> 1
4 -->
matrix:0 --> 0
1 -->
2 -->
3 -->
4 -->
这显然不正确,尽管这是您阅读代码时所期望的。
结束语
手动编写一些解析代码可能会更容易。如果必须的话,您可能会先读入经过高度优化的邻接列表。例如,您可以完全将其内存映射。
如果 boost::adjacency_list
不允许,您可以考虑提供自己的数据结构,对可变图概念进行建模。这听起来可能令人生畏,但实际上比您预期的要少:
- 使其适用于更多算法的后续行动:
- 关于在映射内存中存储复杂的数据结构,我有很多使用 Boost Interprocess 的答案
坦率地说,这些答案没有我刚刚针对您的其他问题所做的 复杂。一定要给他们阅读以获取灵感(从第一本开始)
在 boost 图形库中,有两个流行的函数可以从文件中读取图形:
boost::read_graphviz()
, and boost::read_graphml()
, for the GraphViz and the GraphML format,分别
现在两者都通读为任何类型的 boost::adjacency_list<...>
,因为它们是 Mutable Graph 概念的模型:
#include <string>
#include <fstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graphml.hpp>
#include <boost/graph/graph_traits.hpp>
template <typename GraphType>
GraphType load(std::string filename, std::string format) {
GraphType g(0);
std::ifstream t(filename.c_str());
boost::dynamic_property dp(boost::ignore_other_properties);
if (format == "graphml")
boost::read_graphml(t, g, dp);
else
boost::read_graphviz(t, g, dp);
return g;
}
如果你要测试
load<boost::adjacency_matrix<boost::undirectedS> >("my_file.gv", "graphviz");
你可能会得到类似
的东西Assertion failed: (false), function add_vertex, file /usr/local/include/boost/graph/adjacency_matrix.hpp, line 966.
Abort trap: 6
那么我怎样才能包括读取 boost::adjacency_matrix<...>
的可能性,最好不必从中间邻接列表复制图形,如 in this SO post 所述(图形可能非常大) .
我不明白的是,为了复制,(复制目标)图apparently 也必须是一个可变图,所以我们怎么能然后复制到邻接矩阵?而不是读成一个?
感谢您的帮助!
备注
boost/graph/graphml.hpp
库不是 header-only 并且需要链接,例如当 compiling/linking 时直接从 CLI 附加 -lboost_graph
,如
g++ -lboost_graph my_file.cc
关于copy_graph
What I don't understand is, that for copying, the (copy target) graph apparently also has to be a Mutable Graph, so how can we then copy to an adjacency matrix? And not read into one?
我同意。那没有意义。看起来 copy_graph
应该不起作用 或 文档化的概念要求已过时。
也许它总是过度约束,或者专门为 adjacency_matrix
添加了专业化。
粗略地看一眼就知道它可能被过度约束了,因为显然 adjacency_matrix 不存在 specializations/overloads。
在我们测试之前,让我们看一下断言。
关于断言
断言源于此:
template < typename D, typename VP, typename EP, typename GP, typename A >
inline typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor
add_vertex(adjacency_matrix< D, VP, EP, GP, A >& g)
{
// UNDER CONSTRUCTION
BOOST_ASSERT(false);
return *vertices(g).first;
}
如您所见,这已经是一个正在规划更多灵活性的领域。如果您保留足够的 space,您似乎可以阅读图表。
可能已经为 copy_graph
提供了相同的功能(因为当容量已经足够时,只是避免了 add_vertex
;即使 add_vertex
在技术上仍然是(概念上) 是必需的,它可能并不总是。
检验假设
让我们来测试一下。看看我们是否真的可以从邻接表复制到矩阵中:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
using boost::vecS;
using D = boost::undirectedS¹;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;
int main() {
{ L list(0); M matrix(20); copy_graph(matrix, list); } // okay
{ L list(0); M matrix(20); copy_graph(list, matrix); } // okay
{ L list(1); M matrix(1); copy_graph(list, matrix); } // ASSERTS
{ L list(1); M matrix(20); copy_graph(list, matrix); } // ASSERTS
}
(¹ 方向性实际上并没有什么不同,我测试了)
我们的谜语有了答案。我们不能实际复制。
它确实可以编译,但如果没有断言则不会 运行。
现在,您可能认为您可以 #define NDEBUG
并压制断言。然而,看看上面的代码,很明显你 不能 期望它起作用,因为它总是 return 顶点 0
:
#define NDEBUG
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/graph_utility.hpp>
using boost::vecS;
using D = boost::undirectedS;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;
int main() {
L list(5);
M matrix(10);
add_edge(1, 4, list);
add_edge(3, 1, list);
copy_graph(list, matrix);
print_graph(list, std::cout << "\nlist:");
print_graph(matrix, std::cout << "\nmatrix:");
}
版画
list:0 -->
1 --> 4
2 -->
3 --> 1
4 -->
matrix:0 --> 0
1 -->
2 -->
3 -->
4 -->
这显然不正确,尽管这是您阅读代码时所期望的。
结束语
手动编写一些解析代码可能会更容易。如果必须的话,您可能会先读入经过高度优化的邻接列表。例如,您可以完全将其内存映射。
如果 boost::adjacency_list
不允许,您可以考虑提供自己的数据结构,对可变图概念进行建模。这听起来可能令人生畏,但实际上比您预期的要少:
- 使其适用于更多算法的后续行动:
- 关于在映射内存中存储复杂的数据结构,我有很多使用 Boost Interprocess 的答案
坦率地说,这些答案没有我刚刚针对您的其他问题所做的