从BGL图中提取邻接矩阵

Question

使用Boost图库我正在寻找一种方法来提取邻接矩阵从由任一代表的底层的图boost::adjacency_list或boost::adjacency_matrix.我想结合使用这个矩阵boost::numeric::ublas来求解一个联立线性方程组.

这是一个让你前进的最小例子:

#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兼容.我想知道是否有办法避免遍历整个图形.

Answer 1

将 adjacency_list 转换为 adjacency_matrix 的最简单方法是使用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。继续前面的片段，我们得到：

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 具有一些边捆绑属性，您可能需要修改 MatrixAccessor 中的operator()。

根据您使用的 uBLAS 数量，您可以进一步优化 MatrixAccessor。例如，out_edge_iterator对于 MatrixGraph 的给定顶点，实际上是矩阵列上的迭代器；vertex_iterator 可以被视为矩阵行等的迭代器。

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