Using the C ++ Accelerator Library

Question

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

How do you create a graph and add vertices and edges along the way?

Answer 1

Here is a simple example: using an adjacency list and performing topological sorting:

#include <iostream> #include <deque> #include <iterator> #include "boost/graph/adjacency_list.hpp" #include "boost/graph/topological_sort.hpp" int main() { // Create an 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. I suggest you look at the link below:

http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/table_of_contents.html

I can’t remember if the contents of the printed book match, I suspect it is a little easier on the eyes. I really learned how to use boost: graph from a book. However, the learning curve may seem pretty steep. The book to which I refer and reviews can be found here:

http://www.amazon.com/Boost-Graph-Library-Reference-Manual/dp/0201729148/ref=sr_1_1?ie=UTF8& QID = 1326242972 & cf = 8-1

Answer 2

This is based on the example provided on the boost :: graph site, with added comments:

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

Answer 3

Boost adjacency_list is a good way, this example creates a directed graph and displays a graph image using AT & T 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 can be quickly transferred to the dot utility that ships with GraphViz.

Answer 4

I think you will find the following resources very useful.

Primer Scheme

If you are not familiar with graph theory or need retraining, then look at the promotion. Overview of elementary graph theory: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

This primer is useful for understanding the terminology of how data structures represent graphs (adjacency matrix, adjacency list, etc.) and algorithms (width search, depth search, shortest path, etc.).

Sample code is described in detail

For an example graphing code that is described in detail, check out the next section of Boris Shaling'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 adjacenty_list. The code is fully explained so you can understand each example.

Adjacency_list template parameter overview

It is important to understand the template options for adjacency_list. For example, do you need 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's book explains some of them, but you will find more information about using adjacenty_list here: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

Using custom objects for vertices, faces, or graphs

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

And perhaps this is also an example: adding custom vertices to the force graph

Detection of circular dependencies (loops)

There are many ways to detect circular dependencies, including:

Depth search : One simple way is to perform a depth search and determine if the search is already performed at a vertex already detected in the current search tree. The following is an example of detecting cyclic dependencies using depth depth searches: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles

Topological sorting : You can also detect loops using topological sorting . boost provides a topological algorithm: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html

Topological sorting works on a directed acyclic graph (DAG). If the cyclic graph is passed, an exception is thrown, which indicates that the graph has a cyclic dependency. topological_sort includes a depth search, but also provides a linear order of 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 : In addition, a search for strongly connected components may indicate whether the graph has cycles: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm

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

File Dependency Example

Another useful link is one that has already been provided. - Enlarge the example of file dependencies, which shows how to set up the schedule of source code files, order them based on their compilation order (topological sorting), determine which files can be compiled at the same time, and determine the cyclic dependencies: http: //www.boost. org / doc / libs / 1_58_0 / libs / graph / doc / file_dependency_example.html

Answer 5

Some concise and accurate recipes at the beginning of working with Boost C ++ libraries can be found here:

Using the Boost Graph Library

These code examples listed here look reasonably relevant and seem to compile and work just fine. I believe that some online docs regarding the use of the Boost Graph library seem to be outdated or cause compilation errors.

There are several working examples here, including creating directional and undirected graphs, printing edge weights, finding minimal spanning trees using the Kruskal algorithm, and problems with maximum flow.