Using C++ Boost's Graph Library

Question

I am confused about how to actually create a Graph using the boost library, I have looked at the example code and there are no comments explaining what it does.

How do you make a graph, and add vertices and edges as you go?

Answer 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.

Answer 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; }