Extract adjacency matrix from BGL plot

Question

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

The following is a minimal example that will help you:

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

If anyone could find an effective way to get the adjacency matrix, I would be very obliged. Ideally, the solution is compatible with uBLAS. I wonder if there is a way to avoid iterating all over the graph.

Answer 1

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

Your code for MatrixGraph mg should be modified as follows

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

Now, to use the adjacency matrix with ublas or the like, you can write a simple access class to make the syntax more compatible with ublas. Continuing the previous fragment, 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); } 

If your adjacency_matrix has some edge related properties, you may need to modify the () operator in MatrixAccessor.

Depending on how much UBLAS you use, you may want to check out MatrixAccessor. For example, out_edge_iterator for a given vertex MatrixGraph is actually an iterator over the matrix column; vertex_iterator can be thought of as an iterator over matrix rows, etc.

Of course, the graph matrix is ​​unchanged and as such should be used with caution.

Answer 2

The current version of adjacency_matrix has the undocumented public member m_matrix (see line 640). However, this is a flat vector of tuples <bool, bundled_properties> (line 512). Since the underlying storage looks as strong as that of an ublas-matrix, it is most likely impossible to transform the graph into a matrix, except for iteration along the edges.

Answer 3

as an easy way, and I don’t know how effective it is. Here is what I came up with:

I used a small graph of the world and printed an adjacency matrix.

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

Output:

 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