Estrarre la matrice di adiacenza da un grafico BGL

Question

Utilizzando la Boost Graph Library Sto cercando un modo per estrarre il matrice di adiacenza da un grafico sottostante rappresentato da uno o boost::adjacency_listboost::adjacency_matrix. Mi piacerebbe usare questa matrice insieme a boost::numeric::ublas per risolvere un sistema di equazioni lineari simultanee.

Ecco un esempio minimo per farti andare:

#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? 

} 

Se qualcuno potesse trovare un modo efficace per ottenere la matrice di adiacenza sarei molto grato. Idealmente la soluzione è compatibile con uBLAS. Mi chiedo se c'è un modo per evitare l'iterazione attraverso l'intero grafico.

Answer 1

Il modo più semplice per convertire adjacency_list in adjacency_matrix è quello di utilizzare boost::copy_graph

il codice per MatrixGraph mg dovrebbe essere modificato come segue

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

Ora, da usare matrice di adiacenza con uBLAS o simili, è possibile scrivere una semplice classe di "accesso" per rendere la sintassi più compatibile con Ublas. Proseguendo snippet di codice precedente otteniamo:

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

Nel caso il vostro adjacency_matrix ha alcune proprietà giuntati a bundle, potrebbe essere necessario modificare l'operatore() in MatrixAccessor.

A seconda della quantità di uBLAS che si utilizza, è possibile perfezionare ulteriormente MatrixAccessor. Ad esempio, out_edge_iterator per un dato vertice di un MatrixGraph è in realtà un iteratore su una colonna della matrice; vertex_iterator può essere trattato come iteratore su righe di matrici, ecc.

Naturalmente, la matrice di grafici è immutabile e come tale deve essere utilizzata con attenzione.

Answer 2

Il current revision del adjacency_matrix ha un membro pubblico non documentato m_matrix (vedere la riga 640). Tuttavia, è un vettore piatto di tuple <bool, bundled_properties> (riga 512). Dal momento che la memoria sottostante sembra così diversa da una matrice ublas, è molto probabile che non sia possibile convertire un grafico in una matrice oltre a scorrere i bordi.

Answer 3

altrettanto semplice e non so quanto sia efficiente. Questo è quello che mi è venuto in mente:

Ho usato un piccolo grafico mondiale e stampato la matrice di adiacenza.

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

uscita:

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