从BGL图提取邻接矩阵 [英] Extract the adjacency matrix from a BGL graph

问题描述

使用 Boost图表库我正在寻找从 boost :: adjacency_list表示的基础图中提取邻接矩阵的方法或 boost :: adjacency_matrix 。我想使用这个矩阵与 boost :: numeric :: ublas 结合来求解一个联立的线性方程组。

Using the Boost Graph Library I am looking for a way to extract the adjacency matrix from an underlying graph represented by either boost::adjacency_list or boost::adjacency_matrix. I'd like to use this matrix in conjunction with boost::numeric::ublas to solve a system of simultaneous linear equations.

这里是一个最小的例子，让你去：

Here is a minimal example to get you going:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;
typedef boost::adjacency_matrix< directedS > MatrixGraph;

int main(){ 

  ListGraph lg; 
  add_edge (0, 1, lg); 
  add_edge (0, 3, lg); 
  add_edge (1, 2, lg); 
  add_edge (2, 3, lg); 

  //How do I get the adjacency matrix underlying lg?

  MatrixGraph mg(3); 
  add_edge (0, 1, mg); 
  add_edge (0, 3, mg); 
  add_edge (1, 2, mg); 
  add_edge (2, 3, mg); 

  //How do I get the adjacency matrix underlying mg?

}

如果任何人能想出一种有效的方法来获得邻接矩阵我会很有责任。理想情况下，该解决方案与uBLAS兼容。

If anyone could come up with an efficient way to obtain the adjacency matrix I would be much obliged. Ideally the solution is compatible with uBLAS. I wonder if there is a way to avoid iteration through the entire graph.

推荐答案

将adjacency_list转换为adjacency_matrix的最简单方法是使用 boost :: copy_graph

The easiest way to convert adjacency_list into adjacency_matrix is to use boost::copy_graph

您的代码 MatrixGraph mg 应修改如下

#include <boost/graph/copy.hpp>
#include <cassert>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;
typedef boost::adjacency_matrix< directedS > MatrixGraph;

int main(){

    ListGraph lg;
    add_edge(0, 1, lg);
    add_edge(0, 3, lg);
    add_edge(1, 2, lg);
    add_edge(2, 3, lg);

    //How do I get the adjacency matrix underlying lg?

    //How do I get the adjacency matrix underlying mg?   
    MatrixGraph mg( num_vertices(lg));
    boost::copy_graph(lg, mg);
}

现在，要使用邻接矩阵与ublas或类似， 访问类，使语法更符合ublas。继续前面的代码片段，我们得到：

Now, to use adjacency matrix with ublas or similar, you can write a simple "access" class to make syntax more compliant with ublas. Continuing previous snippet we get:

template <class Graph>
class MatrixAccessor
{
public:
    typedef typename Graph::Matrix Matrix; //actually a vector<
    typedef typename Matrix::const_reference const_reference;


    MatrixAccessor(const Graph* g)
        : m_g(g)
    {
        static_assert(boost::is_same<size_t, typename Graph::vertex_descriptor>::value, "Vertex descriptor should be of integer type");
    }

    const_reference operator()(size_t u, size_t v) const
    {
        return m_g->get_edge(u, v);
    }

    const Graph* m_g;
};

void use_matrix(const MatrixGraph & mg)
{
    MatrixAccessor<MatrixGraph> matr(&mg);
    assert(matr(0, 1) == 1);
    assert(matr(0, 2) == 0);
}

如果你的adjacency_matrix有一些边集合属性，你可能需要修改

In case your adjacency_matrix has some edge-bundled properties, you might need to modify the operator() in MatrixAccessor.

根据您使用的uBLAS数量，您可以进一步细化MatrixAccessor。例如，对于MatrixGraph的给定顶点， out_edge_iterator 实际上是一个通过矩阵列的迭代器; vertex_iterator可以当作矩阵行等的迭代器处理。

Depending on how much uBLAS you use, you can refine MatrixAccessor further. For example, out_edge_iterator for a given vertex of a MatrixGraph is actually an iterator over matrix column; vertex_iterator can be treated as iterator over matrix rows, etc.

当然，图矩阵是不可变的，因此应谨慎使用。

Of course, graph matrix is immutable and as such should be used with care.

这篇关于从BGL图提取邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！