Search code examples
c++boostgraphadjacency-matrixboost-graph

How Can I Read in a Graph to an Adjacency Matrix In the Boost Graph Library?

In the boost graph library, there are two popular functions to read in graphs from a file: boost::read_graphviz(), and boost::read_graphml(), for the GraphViz and the GraphML format, respectively.

Now both read generically to any type of boost::adjacency_list<...>, as they are models of the Mutable Graph concept:

#include <string>
#include <fstream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graphml.hpp>
#include <boost/graph/graph_traits.hpp>

template <typename GraphType>
GraphType load(std::string filename, std::string format) {

    GraphType g(0);

    std::ifstream t(filename.c_str());
    boost::dynamic_property dp(boost::ignore_other_properties);

    if (format == "graphml")
        boost::read_graphml(t, g, dp);
    else
        boost::read_graphviz(t, g, dp);

    return g;
}

If you were to test

load<boost::adjacency_matrix<boost::undirectedS> >("my_file.gv", "graphviz");

you might get something like

Assertion failed: (false), function add_vertex, file /usr/local/include/boost/graph/adjacency_matrix.hpp, line 966.
Abort trap: 6

So how can I include the possibility to read to a boost::adjacency_matrix<...>, preferably without having to copy the graph from an intermediate adjacency list, as explained in this SO post (the graph may be really large).

What I don't understand is, that for copying, the (copy target) graph apparently also has to be a Mutable Graph, so how can we then copy to an adjacency matrix? And not read into one?

Thanks for any help!

Note

The boost/graph/graphml.hpp library is not header-only and needs to be linked against, for example by appending -lboost_graph when compiling/linking directly from the CLI, as in

g++ -lboost_graph my_file.cc
Solution

  • Regarding copy_graph

    What I don't understand is, that for copying, the (copy target) graph apparently also has to be a Mutable Graph, so how can we then copy to an adjacency matrix? And not read into one?

    I agree. That doesn't make sense. For all it appears the copy_graph should not work or the documented concept requirement is out-of-date.

    Perhaps it was always over-constrained, or specializations have been added specifically for adjacency_matrix.

    A cursory glance tells that it might have been over-constrained since clearly no specializations/overloads exist for adjacency_matrix.

    Before we test, let's look at the assertion.

    Regarding the Assertion

    The assert stems here:

    template < typename D, typename VP, typename EP, typename GP, typename A >
inline typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor
add_vertex(adjacency_matrix< D, VP, EP, GP, A >& g)
{
    // UNDER CONSTRUCTION
    BOOST_ASSERT(false);
    return *vertices(g).first;
}

    As you can see this was already an area where more flexibility was being planned. It does seem likely that if you reserve enough space, you might be able to read the graph.

    The same might be what already powers copy_graph (in that add_vertex is just avoided when the capacity already suffices; even though add_vertex is still technically (conceptually) required, it may not always be.

    Testing The Hypotheses

    Let's put it to the test. See whether we can actually copy from adjacency list into a matrix:

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
using boost::vecS;
using D = boost::undirectedS¹;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;

int main() {
    { L list(0); M matrix(20); copy_graph(matrix, list);   } // okay
    { L list(0); M matrix(20); copy_graph(list,   matrix); } // okay
    { L list(1); M matrix(1);  copy_graph(list,   matrix); } // ASSERTS
    { L list(1); M matrix(20); copy_graph(list,   matrix); } // ASSERTS
}

    (¹ The directionality doesn't actually make a difference, I tested)

    There's the answer to our riddle. We can't actually copy.

    It does compile but it doesn't run without assertion.

    Now, you are probably thinking you can #define NDEBUG and silence the assertion. However, looking at the code above it's clear that you cannot expect this to work, because it will always return vertex 0:

    Sad Trombone:

    #define NDEBUG
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/graph_utility.hpp>
using boost::vecS;
using D = boost::undirectedS;
using L = boost::adjacency_list<vecS, vecS, D>;
using M = boost::adjacency_matrix<D>;

int main() {
    L list(5);
    M matrix(10);

    add_edge(1, 4, list);
    add_edge(3, 1, list);

    copy_graph(list, matrix);

    print_graph(list, std::cout << "\nlist:");
    print_graph(matrix, std::cout << "\nmatrix:");
}

    Prints

    list:0 --> 
1 --> 4 
2 --> 
3 --> 1 
4 --> 

matrix:0 --> 0 
1 --> 
2 --> 
3 --> 
4 -->

    That's cleary not correct, though it is what you'd expect from reading the code.

    Closing Words

    It could be easier to just write some parsing code manually. If you must you might read into a heavily optimized adjacency list first. For example you could memory map it completely.

    If boost::adjacency_list doesn't let you, you can consider providing your own datastructures modeling the Mutable Graph concept. That may sound daunting, but it's actually less work than you might expect:

    To be frank, those answers are less complex than the bonus section I just made on your other question. Do give them a read for inspiration (starting with the first one)