Boost graph designing without adjacency list or adjacency matrix [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

Is there any way to create a graph structure without using adjacency list or adjacency matrix in C++ boost? (a vertex structure using pointers which points to its neighbour vertices)

Answer 1

It is possible, of course, provided your data has "traits" of a theoretical graph, meaning you essentially deal with "vertices" and "edges", even if in your code they are called, say, "nodes" and "links".

This construct is called "BGL graph adapter". It can be a little challenging C++ exercise, though. The general idea is to teach BGL a lot of details about your data:

1. what C++ types of your data mean in your imaginary graph and
2. how to iterate over your vertices and edges.

So you define a class, say MyGraph, which is typically a very light-weight and just keeps few pointers to your data. Then you define its traits by providing template specialization of BGL graph_traits:

#include <boost/graph/graph_traits.hpp>
namespace boost {
    template <>
    struct graph_traits<MyGraph> 
{
    typedef ... vertex_descriptor; //what plays a role of vertex in your data
    typedef ... edge_descriptor; //what plays a role of edge in your data

    //other typedefs from graph_traits like edge_iterator, out_edge_iterator, etc.

    //plus, you specify "categories" of your graph explaining what types of traversal are
    //available (more the better)
    struct traversal_category
        : public virtual boost::vertex_list_graph_tag
        , public virtual boost::adjacency_graph_tag
        , public virtual boost::bidirectional_graph_tag //means we provide access to in_edges
                                                        //and to out_edges of a given vertex
    {
    };    
};
}

After that you implement global functions which provide access and iterator over your graph structure, for example:

MyGraph::vertex_descriptor 
source(MyGraph::edge_descriptor e, const MyGraph & g); 

and

std::pair<MyGraph::out_edge_iterator,
          MyGraph::out_edge_iterator>
out_edges(MyGraph::::vertex_descriptor vd, const MyGraph & g )

There is about dozens of such traverse functions predefined in BGL graph concepts. You have to provide at least those which relevant for your traversal_category declared above.

If everything is done right, you can use your data directly with BGL algorithms, without using one of predefined BGL graphs.

A good explanation on the subject is given in BGL chapter How to Convert Existing Graphs to BGL