<code>boost::adjacency_list</code>または<code>boost::adjacency_matrix</code>のいずれかによって表される基本となるグラフから隣接行列</strong>を抽出し、私は<strong>への道を探しています<strong>ブーストグラフライブラリ</strong>を使用してBGLグラフ

Question

から隣接行列を抽出します。この行列をboost::numeric::ublasと組み合わせて使用​​して、連立1次方程式系を解きたい。

は、ここであなたが軌道に乗るために、最小限の例です。

#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_matrixへのadjacency_listを変換する最も簡単な方法は、boost::copy_graphが

ublasまたは類似と隣接行列を使用するように、今

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

を次のようにMatrixGraph mgのためのあなたのコードを変更する必要があり、あなたが書くことができます使用することですシンプルな "アクセス"クラスで、構文をより多くのublasに準拠させることができます。前のスニペットを続け、我々が得る：

あなたadjacency_matrixは、いくつかのエッジ・バンドルの特性を有している場合には

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

、あなたはMatrixAccessorに（）演算子を変更する必要があります。

使用するuBLASの量に応じて、MatrixAccessorをさらに絞り込むことができます。たとえば、MatrixGraphの特定の頂点に対するout_edge_iteratorは、実際には行列の列に対するイテレータです。 vertex_iteratorは、行列行などのイテレータとして扱うことができます。

もちろん、グラフマトリックスは不変であり、注意して使用する必要があります。

Answer 2

adjacency_matrixのcurrent revisionには、文書化されていない公開メンバm_matrix（640行目参照）があります。しかし、これはタプル<bool, bundled_properties>（512行目）のフラットなベクトルです。基礎となるストレージは表層行列と大きく異なるため、エッジを反復する以外にグラフを行列に変換することは不可能です。

Answer 3

簡単な方法として、私はどれくらい効果的かわかりません。 これは私が思いついたものです：

私は小さな世界グラフを使用して隣接行列を印刷しました。

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/small_world_generator.hpp> 
#include <boost/random/linear_congruential.hpp> 

using namespace std; 
using namespace boost; 

typedef adjacency_list<vecS, vecS, undirectedS> Graph; 
typedef small_world_iterator<boost::minstd_rand, Graph> SWGen; 

int main() 
{ 

    boost::minstd_rand gen; 
    int N = 20; 
    int degree = 4; 
    double rewiring = 0.; 

    Graph g(SWGen(gen, N, degree, rewiring), SWGen(), 20); 

    cout << num_edges(g)<< '\n'; 

    typedef graph_traits<Graph>::edge_iterator edge_iterator; 
    pair<edge_iterator, edge_iterator> ei = edges(g); 

    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) { 
     cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n"; 
    } 
    vector<vector<int> > mat(N,vector<int>(N)); 

    for (edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter){ 
     int a = source(*edge_iter, g); 
     int b = target(*edge_iter, g); 
     mat[a][b] = 1; 
     mat[b][a] = 1; 
    } 


    for (int i=0; i<N; i++){ 
     for (int j=0; j<N; j++){ 
      cout << mat[i][j]<<" "; 
     } 
     cout <<endl; 
    } 

    return 0; 
} 

出力：

0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0