Using C++ Boost's Graph Library

Solution 1:

Here's a simple example, using an adjacency list and executing a topological sort:

#include <iostream>
#include <deque>
#include <iterator>

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/topological_sort.hpp"

int main()
{
    // Create a n adjacency list, add some vertices.
    boost::adjacency_list<> g(num tasks);
    boost::add_vertex(0, g);
    boost::add_vertex(1, g);
    boost::add_vertex(2, g);
    boost::add_vertex(3, g);
    boost::add_vertex(4, g);
    boost::add_vertex(5, g);
    boost::add_vertex(6, g);

    // Add edges between vertices.
    boost::add_edge(0, 3, g);
    boost::add_edge(1, 3, g);
    boost::add_edge(1, 4, g);
    boost::add_edge(2, 1, g);
    boost::add_edge(3, 5, g);
    boost::add_edge(4, 6, g);
    boost::add_edge(5, 6, g);

    // Perform a topological sort.
    std::deque<int> topo_order;
    boost::topological_sort(g, std::front_inserter(topo_order));

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

    return 0;
}

I agree that the boost::graph documentation can be intimidating, but it's worth having a look.

I can't recall if the contents of the printed book is the same, I suspect it's a bit easier on the eyes. I actually learnt to use boost:graph from the book. The learning curve can feel pretty steep though. The book I refer to and reviews can be found here.

Solution 2:

This is based off the example given on the boost::graph website, with comments added:

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.hpp"

using namespace boost;

int main(int argc, char *argv[])
{
    //create an -undirected- graph type, using vectors as the underlying containers
    //and an adjacency_list as the basic representation
    typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;

    //Our set of edges, which basically are just converted into ints (0-4)
    enum {A, B, C, D, E, N};
    const char *name = "ABCDE";

    //An edge is just a connection between two vertitices. Our verticies above
    //are an enum, and are just used as integers, so our edges just become
    //a std::pair<int, int>
    typedef std::pair<int, int> Edge;

    //Example uses an array, but we can easily use another container type
    //to hold our edges. 
    std::vector<Edge> edgeVec;
    edgeVec.push_back(Edge(A,B));
    edgeVec.push_back(Edge(A,D));
    edgeVec.push_back(Edge(C,A));
    edgeVec.push_back(Edge(D,C));
    edgeVec.push_back(Edge(C,E));
    edgeVec.push_back(Edge(B,D));
    edgeVec.push_back(Edge(D,E));

    //Now we can initialize our graph using iterators from our above vector
    UndirectedGraph g(edgeVec.begin(), edgeVec.end(), N);

    std::cout << num_edges(g) << "\n";

    //Ok, we want to see that all our edges are now contained in the graph
    typedef graph_traits<UndirectedGraph>::edge_iterator edge_iterator;

    //Tried to make this section more clear, instead of using tie, keeping all
    //the original types so it's more clear what is going on
    std::pair<edge_iterator, edge_iterator> ei = edges(g);
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }

    std::cout << "\n";
    //Want to add another edge between (A,E)?
    add_edge(A, E, g);

    //Print out the edge list again to see that it has been added
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }

    //Finally lets add a new vertex - remember the verticies are just of type int
    int F = add_vertex(g);
    std::cout << F << "\n";

    //Connect our new vertex with an edge to A...
    add_edge(A, F, g);

    //...and print out our edge set once more to see that it was added
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }
    return 0;
}

Solution 3:

I think you will find the following resources very helpful.

Graph Theory Primer

If you are unfamiliar with graph theory or need a refresher, then take a look at boost's Review of Elementary Graph Theory: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

This primer is helpful in understanding the terminology, how data structures represent graphs (adjacency matrix, adjacency list, etc…), and algorithms (breadth-first search, depth-first search, shortest-path, etc…).

Sample Code Described in Detail

For sample code for creating graphs that is described in detail, then take a look at the following section of Boris Schäling's online book - The Boost C++ Libraries: http://theboostcpplibraries.com/boost.graph-vertices-and-edges

Boris explains how to work with vertices and edges using the adjacenty_list. The code is thoroughly explained so you can understand each example.

Understanding adjacency_list Template Parameters

It is important to understand the template parameters for the adjacency_list. For example, do you want a directed or undirected graph? Do you want your graph to contain multiple edges with the same end nodes (i.e. multigraphs)? Performance also comes into play. Boris' book explains some of these, but you will find additional information on using the adjacenty_list here: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

Using Custom Objects for Vertices, Edges, or Graphs

If you want to use custom objects for the vertices, edges, or even the graph itself, then you will want to use bundled properties. The following links will be helpful for using bundled properties: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html

And perhaps this one too for an example: adding custom vertices to a boost graph

Detecting Circular Dependencies (Cycles)

There are multiple ways to detect circular dependencies including:

Depth-First Search: One simple way is by performing a depth-first search and detecting if the search runs into an already discovered vertex in the current search tree. Here is an example of detecting cyclic dependencies using boost's depth-first search: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles

Topological Sort: One can also detect cycles using a topological sort. boost provides a topological_sort algorithm: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html

A topological sort works on a directed acyclic graph (DAG). If a cyclic graph is passed in, then an exception is thrown, thus indicating that the graph has a circular dependency. topological_sort includes a depth-first search, but also provides a linear ordering of the vertices. Here is an example: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles

Strongly Connected Components: Additionally, finding strongly connected components can indicate whether or not a graph has cycles: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm

boost's strong_components function computes the strongly connected components of a directed graph using Tarjan's algorithm. http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html

File Dependency Example

Another helpful link is one that was already provided - boost's File Dependency Example that shows how to setup a graph of source code files, order them based on their compilation order (topological sort), determine what files can be compiled simultaneously, and determine cyclic dependencies: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html

Solution 4:

Boost's adjacency_list is a good way to go, this example creates a directed graph and outputs an image of the graph using AT&T's GraphViz:

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
    using namespace std;
    using namespace boost;

    /* define the graph type
          listS: selects the STL list container to store 
                 the OutEdge list
          vecS: selects the STL vector container to store 
                the vertices
          directedS: selects directed edges
    */
   typedef adjacency_list< listS, vecS, directedS > digraph;

   // instantiate a digraph object with 8 vertices
   digraph g(8);

   // add some edges
   add_edge(0, 1, g);
   add_edge(1, 5, g);
   add_edge(5, 6, g);
   add_edge(2, 3, g);
   add_edge(2, 4, g);
   add_edge(3, 5, g);
   add_edge(4, 5, g);
   add_edge(5, 7, g);

   // represent graph in DOT format and send to cout
   write_graphviz(cout, g);

   return 0;
}

The output is a DOT file that you can quickly feed into the dot utility that comes with GraphViz.