如何在Boost Graph库中将图形读入邻接矩阵？

Question

在boost图形库中，有两个流行的函数可以从文件中读取图形： boost::read_graphviz()和boost::read_graphml()，分别用于GraphViz和GraphML格式。

现在，它们都可以通用地读取任何类型的boost::adjacency_list<...>，因为它们是可变图概念的模型：

#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<...>中呢？这在这个SO帖子中有所解释（图可能非常大）。

我不理解的是，为了复制，（复制目标）图形 显然 也必须是可变图形，那么我们如何将其复制到邻接矩阵中？而不是读取到其中一个中呢？

感谢任何帮助！

注意

boost/graph/graphml.hpp库不是头文件，并且需要链接，例如通过在编译/链接时直接从CLI附加-lboost_graph来链接。

g++ -lboost_graph my_file.cc

- gitchhiker

---

“as they are derived from the Mutable Graph concept” 应该翻译为“因为它们是可变图概念的模型”，这是一个明显不同的概念。 - sehe

Answer 1

关于copy_graph

我不理解的是，为了复制，（复制目标）图表显然也必须是可变图表，那么我们如何将其复制到邻接矩阵中？而不是读取一个邻接矩阵？

我同意。这没有意义。看起来copy_graph应该不能工作或者文档中的概念要求已过时。

也许它一直过度约束，或者专门为adjacency_matrix添加了特殊化。

粗略地看，它可能被过度约束，因为明显不存在邻接矩阵的特殊化/重载。

在我们测试之前，让我们看一下断言。

关于断言

断言源于此处：

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;
}

正如您所看到的，这已经是一个计划增加更多灵活性的领域。如果您保留足够的空间，可能能够读取图表。

同样的策略可能已经在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来消除断言。然而，从上面的代码中可以清楚地看出，你不能指望这样做能够奏效，因为它总是会返回顶点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无法满足您的需求，您可以考虑提供自己的数据结构来建模可变图概念。这听起来可能很令人生畏，但实际上比您想象的要少工作：

• 如何在现有数据结构上使用BGL算法（将边和顶点作为vector<Object *>）？
• 一个后续问题，使其可以与更多算法一起使用：自定义BGL图形所需的内容以使其与拓扑排序一起工作？
• 关于在映射内存中存储复杂数据结构的问题，我有很多使用Boost Interprocess的答案

坦白地说，这些答案比我在你的另一个问题上刚刚制作的奖励部分要简单得多。请阅读它们以获取灵感（从第一个开始）。

- sehe