Boost Adapter class to convert matrix to to graph

Question

I need to find out the shortest path between two nodes in a 2D array. For that i would like to use boost graph library. But the boost graph library accepts graph as input. So i need to convert 2D array to graph. I have also heard that an adapter class matrix to graph can be used for this purpose. But when i went through that i couldn't clearly understand that too. Also i couldn't find any examples for that. So could anyone please give me a sample code regarding how to use that adapter code for converting matrix to graph?

Thanks

score 1 · Answer 1 · edited May 23 '17 at 10:33

Have a look at this piece of code linked in the comment to Extract the adjacency matrix from a BGL graph.

There doesn't seem to be an easier way than just iterating your matrix and adding edges to a graph for now.

for(i = 0; i < nrows; ++i)
    for(j = 0; j < ncols; ++j)  //of course in a graph nrows should equal ncols.
        if(matrix[i][j] != 0){
            add_edge(i,j,g);
        }

Provided you have a vecS vertex graph (integer vertex descriptors).

The matrix adapter class is undocumented in boost for now. After looking at the implementation and this mailing list post it seems that this is meant to work with the boost::numeric::ublas::mapped_matrix judging by the reference to the nnz method (number of non-zero elements).

Though not stated in the matrix adapter, the vector adapter and leda adapter, with the same authors states:

"This module requires the C++ compiler to support partial specialization for the graph_traits class, so this is not portable to VC++."

Thus even if you get these undocumented adapters to work they will not compile using VC++.

You will just have to iterate your matrix and add the edges by hand (as far as I know).

Boost Adapter class to convert matrix to to graph

1 Answers1