8

ブースト グラフ ライブラリを使用して、またはで表される基になるグラフから隣接行列を抽出する方法を探しています。この行列を と組み合わせて使用​​して、連立一次方程式を解きたいと思います。boost::adjacency_listboost::adjacency_matrixboost::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 と互換性があります。グラフ全体の反復を回避する方法があるのだろうか。

4

3 に答える 3

4

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 は、行列の行などに対するイテレータとして扱うことができます。

もちろん、グラフ行列は不変であるため、注意して使用する必要があります。

于 2014-04-20T22:54:45.443 に答える
1

の現在のリビジョンにadjacency_matrixは、文書化されていない public メンバーがありm_matrixます (640 行を参照)。ただし、これはタプルのフラット ベクトルです<bool, bundled_properties>(512 行目)。基礎となるストレージは ublas 行列とは非常に異なるように見えるため、エッジを反復処理する以外にグラフを行列に変換することはほとんど不可能です。

于 2013-03-22T14:44:35.697 に答える