How to represent a group of C++ dynamically allocated objects as a BGL (Boost Graph Library) graph in order to obtain their dependency graph?

Question

There is a group of C++ dynamically allocated objects as:

class MyObject;
MyObject* a = ....;
MyObject* b = ....;
MyObject* c = ....;

with known dependencies:

• b depends on a
• c depends on b

How those objects can be represented as simple as possible as a BGL graph in order to obtain their dependency graph?

As result the dependency graph should be a list of pointers as: a, b, c (or in the reverse order).

I know the dependency graph can be obtained using boost::topological_sort. Until now I didn't found an example of a BGL graph dealing with pointers to objects. Instead I found many examples based on integers.

Answer 1

The integers are indices to the vertices and edges of the graph. So, in your example, the first vertex is a and the second vertex is b while the first edge connects vertices 1 and 2 ( a and b )

Each vertex has properties. So, in your example, the first vertex is named a and has a pointer to a.

The graph algorithms use the integer indices to manipulate the graph, and your code can use the indices to get back to the properties that you are interested in, such as names and pointers.

Here is how I would code the example you posted:

/**

Bundled properties for graph vertices

Simply contains a pointer to the associated MyObject

*/

class cVertex
{
public:
    MyObject * pObject;
};

class cEdge
{

};

class cGraphProps
{

};

....

// The BGL graph
typedef boost::adjacency_list <
    boost::vecS, boost::vecS, boost::directedS,
    cVertex, cEdge, cGraphProps  >
    graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

graph_t myGraph;

// Create objects and associate them with graph vertices
MyObject * a = new MyObject( 'a');
vertex_t va = boost::add_vertex( myGraph );
myGraph[ va ].pObject = a;
MyObject * b = new MyObject( 'b');
vertex_t vb = boost::add_vertex( myGraph );
myGraph[ vb ].pObject = b;
MyObject * c = new MyObject( 'c');
vertex_t vc = boost::add_vertex( myGraph );
myGraph[ vc ].pObject = c;

// specify the 'dependencies' between the myObjects
boost::add_edge( vb, va, myGraph );
boost::add_edge( vc, vb, myGraph );

// sort the vertices into order according to dependencies
std::deque<int> topo_order;
boost::topological_sort( myGraph, std::front_inserter(topo_order));

// Print the results.
for(std::deque<int>::const_iterator i = topo_order.begin();
    i != topo_order.end();
    ++i)
{
    std::cout << myGraph[*i].pObject->x << std::endl;
}

Answer 2

I wrote this implementation but I would prefer a simpler one if it's possible:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>

class MyObject
{
public:
    char x;
    MyObject( const char c): x( c) {}
};

int main()
{
    auto a = new MyObject( 'a');
    auto b = new MyObject( 'b');
    auto c = new MyObject( 'c');

    typedef std::vector<const MyObject*> Objects;
    Objects objects;
    objects.push_back( c); // c = 0
    objects.push_back( a); // a = 1
    objects.push_back( b); // b = 2

    typedef std::vector<size_t> Indexes;
    Indexes indexes;

    {
        typedef std::unordered_map<Objects::value_type, size_t> PtrIntMap;
        PtrIntMap ptrIntMap;
        std::for_each( objects.begin(), objects.end(), [&ptrIntMap]( Objects::reference item) { ptrIntMap.insert( std::make_pair( item, ptrIntMap.size())); });

        using namespace boost;
        adjacency_list<> g( objects.size());
        add_edge( ptrIntMap.at( b), ptrIntMap.at( a), g);
        add_edge( ptrIntMap.at( c), ptrIntMap.at( b), g);

        topological_sort( g, std::back_inserter( indexes)); 
    }

    Objects dependencies( indexes.size());
    std::transform( indexes.begin(), indexes.end(), dependencies.begin(), [&objects]( Indexes::value_type index) { return objects[ index]; });
    std::for_each( dependencies.begin(), dependencies.end(), []( const Objects::value_type item) { std::cout << item->x << ' '; });
}