http://www.informit.com/articles/printerfriendly.aspx?p=673259
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html

Manipulating C++ Graph Data Structures with the Boost Graph Library

By Jeff Cogswell

Date: Dec 1, 2006

Return to the article

Quickly becoming a de facto standard C++ library, the Boost library includes a powerful graph data structure that's also easy to use. Jeff Cogswell discusses some interesting theory behind graphs, and explains the Boost library's graph structures.

In advanced mathematics, a graph is a special data structure made up of lines (called edges) connected together at endpoints (called vertices or nodes). This definition of the term graph is in contrast to a popular definition used in early math classes, where a graph is simply a plot of a function.

Many computer science and mathematical algorithms make use of graphs. Because graphs are so important in many algorithms, a data structure for a graph is equally important. Most languages don't have graph data structures built in; indeed, C++ doesn't. Therefore, when you need a graph data structure, you either have to code one yourself or make use of a third-party library offering a graph data structure.

The Boost library is quickly becoming a de facto standard C++ library, and it includes a graph data structure that's easy to use yet powerful. In this article, I discuss the theory behind graphs, and then we explore the Boost library's graph structures.

Grasping Graph Theory

As I already mentioned, a graph is simply a set of vertices (the points) connected by edges (the lines). When two vertices are connected by an edge, those two vertices are said to be adjacent. If you enjoy mathematics, you might like to know that this definition can be described a bit more technically by stating that a graph consists of a finite set of vertices along with a finite set of unordered pairs of distinct vertices; you can see that the pairs of vertices represent the edges of the graph.

Graphs provide a visual way of displaying underlying information. For example, a large airline serves many cities. The airline's web site might provide a map showing cities as dots, and lines connecting the cities representing flights between those cities. This map could be considered a graph. Similar graphs might include those showing a trucking company's delivery routes between cities, or bus routes between cities.

Although, technically speaking, a graph consists simply of vertices connected by edges, this limited definition isn't particularly useful. Often, graphs are more useful when they have more associated information. For example, a flight map might also show the flight numbers associated with each flight. In this representation, a graph consists of vertices, edges, and numbers associated with the edges. When numbers are associated with edges, such graphs are called weighted graphs.

Certainly, some graphs might need more than one piece of data associated with each edge. For example, in addition to the flight numbers, the airline map might show the length of each flight. In terms of computer science, however, such information would still be considered individual pieces of data in the form of individual structures or objects associated with each edge, with each structure containing a flight number and a flight time

Similarly, a graph might need to have information attached to the vertices, such as city names in the case of the airline map. In mathematics, you can attach numbers to vertices and use such numbers in calculations.

Another somewhat limiting aspect of a traditional definition of a graph is that the edges connecting the vertices don't have directions. In real life, a system that can be modeled by a graph will likely have directions. For example, if you travel by train somewhere, you definitely want to feel comfortable that the tracks you're riding on from one city to the next are carrying the train in a single direction! When you add directions to graphs, you have what mathematicians call a directed graph, or digraph for short.

Important to graph theory is another type of graph, limited by the restriction that the graph can be drawn on a sheet of paper without any edges crossing. Such a graph is called a planar graph. The term planar is used because the graph can be drawn on a single plane. Of course, this plane might not always be flat in the geometrical sense; the plane could exist on a curved surface such as the surface of the Earth, in which case it still maps to two dimensions. That's getting into another interesting area of mathematics called topology, however, which we won't cover here.

Old and Famous Problems

Graphs aren't just for representing data. They're often used in problem solving, and, as such, play a central role in many algorithms. Over the years, mathematicians have used graphs to solve many famous problems. One of the most famous is calculating how many colors are needed to color each country on a world map, such that no two adjacent countries share the same color. (If two countries touch at a single point, that point isn't considered a boundary.) People have long suspected that the answer is four, and thus the problem can be to prove that any map can be colored with only four colors.

This assertion has been proven in various ways. One way employs graph theory—in particular, planar graphs. Remember that a planar graph is simply a graph that can be drawn on paper (that is, in two dimensions) without any edges crossing. The vertices in the graph represent countries, and the edges represent adjacencies. Thus, if a line connects two countries in a graph, the two countries share a common border. By this representation, the assertion becomes the following: Given any planar graph, a number can be associated with each vertex, and only four numbers are needed such that no two adjacent vertices share a single number. That hypothesis can then be proven using graph theory. (I won't go into the details here, but you can find information on the web if you're curious. It's called the "Four Color Theorem.")

Another famous problem that can be proven using graph theory is the "Seven Bridges" problem. The problem is based on the bridges of Konigsberg, Prussia. The problem is whether it's possible to walk across each bridge in that city once and only once (without cheating by swimming across a river), and ultimately return to the starting point. The famous mathematician Leonhard Euler solved the problem by using graph theory. (Unfortunately, his proof shows that it's impossible to perform the feat without jumping into one of the rivers.)

In Euler's proof of the Seven Bridges problem, he let the vertices of a graph represent the land masses, and the edges of the graph represented the bridges. To solve the problem, Euler associated a degree with each vertex; the degree is the number of edges touching the vertex. Euler proved that in order to complete a single circuit (that is, to cross each bridge once and only once and to return to your starting point), all the nodes must have a degree that's positive. If any nodes have an odd number of edges touching them, then the task is impossible. The seven bridges in Konigsberg were constructed such that four of the nodes have odd degrees.

Graphs, Computers, and Popular Culture

Graphs show up all over the place in the world of computers. The Web itself is one massive graph, with each page being a vertex, and each link to another page an edge. Another place you see a graph concept is in social sites such as MySpace. In that sense, each profile is a vertex, and each friendship connection is an edge. That is, profiles are linked to other profiles via friend connections, just as vertices are linked to other vertices via edges.

In fact, the friendship link concept is used in a game people play, often called "Six Degrees of Kevin Bacon." The idea is that every Hollywood movie star is linked to Kevin Bacon by at most six links, and your job is to find the links. For example, take Jamie Foxx, who is two degrees from Kevin Bacon. One link goes like this: Jamie Foxx was in Booty Call with David Hemblen, who was in Where the Truth Lies with Kevin Bacon. (How did I know? I checked it out at The Oracle of Bacon.)

One popular social networking site, Facebook, uses graph theory to tell how members are connected to other members. If you're signed in, you visit a member's page, and that member is only a couple of links away, Facebook shows the connection. It says that person A is on your friend list, who has person B on his or her friend list, who in turn is friends with the person whose profile you're looking at. The FAQ even mentions using graph theory algorithms to make those connections visible.

Constructing a Simple Graph with Boost

If you have to code a graph theory algorithm, you can either build the graph data structures yourself, or use a library. The one I'm using for this article is found in the Boost library. Let's take a look at a first sample to show you how to use the Boost library's support for graph theory.

In general, a graph can be represented in a computer as a set of vertices and a set of edges connecting the vertices; the edges are simply pairs of vertices. Further, each vertex and each edge can have additional data attached to it, such as a number representing a weight, in the case of edges. This is essentially how Boost's Graph library works.

The Boost Graph library exists as templates, which means that you create your own classes and types based on the templates. However, the parameters for the templates all have defaults, so you can create a graph easily without having to do any customization.

Here's a short piece of code that demonstrates creating a graph and inserting vertices and edges into the graph. This code compiles completely, but it doesn't really do much other than create the graph:

#include <iostream>
#include <stdlib.h>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main(int argc, char *argv[])
{
  adjacency_list<> mygraph; 
  add_edge(1, 2, mygraph);
  add_edge(1, 3, mygraph);
  add_edge(1, 4, mygraph);
  add_edge(2, 4, mygraph);
  return 0;
}

The mygraph variable is the graph itself. The type is adjacency_list, which is the fundamental graph template type in the Boost Graph library. I used the defaults for the parameters; thus, the parameters are an empty set with angle brackets (<>).

The add_edge function is a template helper function for adding items to the graph. To use it, you pass the values for two vertices. If the vertices don't already exist in the graph, they'll be added; then the edge connecting the two vertices will be added. Thus, the preceding code creates a graph with four vertices, numbered 1, 2, 3, and 4, with edges connecting 1 and 2, 1 and 3, 1 and 4, and finally 2 and 4.

This is just a basic example. To create more complex graphs, you'll need to define more data to associate with your edges and vertices. I take up that task in the next section.

Adding Values to Vertices and Edges

When you use a graph, normally you'll want to associate information with the vertices and edges. The Graph library uses an interesting approach for this goal. Items such as names or colors are stored in properties, which consist of a name (or tag) such as distance or name, and a type such as float or string. You can add properties to both vertices and edges.

BOOST_DEF_PROPERTY(edge, name);

When you define a graph, you can specify the types of properties associated with the graph. You can add as many properties as you want to vertices and edges. To define properties, first you create a template type for each property type, and then you define the graph type before you instantiate the graph. For example, suppose you want to attach a distance to each edge, and a city name to each vertex. Here's the code to define the two property types:

typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef property<vertex_name_t, std::string> VertexNameProperty;

The first line defines the EdgeWeightProperty type. The first parameter to the template is the tag for the property. I'm using one of the predefined tags, edge_weight_t, which means edge weight. The second parameter is int, meaning this property will hold an integer. The second line defines the second property; the tag is vertex_name_t, and the type is string.

Now that you have the property types defined, you can define a graph type:

typedef adjacency_list<vecS, vecS, undirectedS,
  VertexNameProperty, EdgeWeightProperty> Graph;

I'm using three predefined values for the first three parameters. The first and second parameters (vecS in both cases) indicate that I want the graph to use vectors for its internal storage, and the third parameter (undirectedS) says that I want an undirected graph. The fourth and fifth parameters (VertexNameProperty, EdgeWeightProperty, respectively) are the property types that I just defined, with the vertex type first, followed by the edge type.

At this point, you might wonder how you can specify more than one type of property for the edges and vertices. Here's how: Chain the properties together. The basic property template includes a parameter that can contain a property you already defined. Here's the vertex property definition again, but this time I'm defining two properties for vertex, a name and an index (using the predefined tag vertex_index2_t):

typedef property<vertex_index2_t, int>
  VertexIndexProperty;
typedef property<vertex_name_t, std::string,
  VertexIndexProperty> VertexNameProperty;

I've defined the index first, but the order really doesn't matter. The VertexNameProperty contains the VertexIndexProperty as its third parameter, thus creating a chain. You then pass the VertexNameProperty type to the fourth parameter of the graph definition, as before.

You also can condense your code a bit. This code is a bit less readable to somebody who is new to the Graph library, although once you understand the property mechanism it's pretty straightforward:

typedef property<vertex_name_t, std::string,
  property<vertex_index2_t, int> > VertexProperties;

I renamed the type VertexProperties, since it now contains two different properties. Also, notice the standard required space between the closing angle brackets, which is always needed in C++ so the parser doesn't think it's an insertion operator (>>). Don't forget that space, or you'll end up with compilation errors.

Manipulating Property Values

In order to access the properties of your graph, you need to obtain a helper object from the Graph library. You obtain one object for each property type. The objects are template objects, and you can obtain them after you've created an instance of your Graph type. Here are the lines that obtain objects for the three properties I declared in the preceding section:

property_map<Graph, vertex_name_t>::type
  city_name = get(vertex_name, g);
property_map<Graph, vertex_index2_t>::type
  city_index2 = get(vertex_index2, g);
property_map<Graph, edge_weight_t>::type 
  edge_distance = get(edge_weight, g);

Don't worry that the function name is the somewhat generic word get. The function is well-defined as a typed template, so it will compile just fine.

The first statement creates an object for obtaining the vertex_name property. Look closely at the parameters. On the left, the parameters to the template are the Graph type defined earlier, along with the tag for the property, vertex_name_t. On the right, inside the call to get, is not the tag name, but rather an enumeration type associated with the property, vertex_name. Each predefined tag name also includes an enumeration for each type. The Graph object itself, g, is the second parameter to the get function.

Remember, these three calls each obtain an object that you can use for getting properties for a vertex or edge. Although the sample code pieces I've been giving you so far haven't created any vertices, here's a sample line I'll use later on to obtain a property:

std::cout << city_name[*vp.first];

where vp.first is a pointer to a vertex. The object, city_name, works like a map, and it takes a vertex object as a parameter. It then returns the appropriate property—in this case, the city name.

Adding Vertices and Edges

After you've specified your property types and defined the graph type, you're ready to create an instance of the graph and add vertices and edges to the graph, along with values for the properties associated with the vertices and edges.

Let's start with a fresh graph, define some properties, and then add the edges and vertices along with their properties. I'll list all the code here so you don't have to piece together the fragments I've given you so far.

// Property types
typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef property<vertex_name_t, std::string,
  property<vertex_index2_t, int> > VertexProperties;

// Graph type 
typedef adjacency_list<vecS, vecS, undirectedS,
  VertexProperties, EdgeWeightProperty> Graph;

// Graph instance
Graph g;

// Property accessors
property_map<Graph, vertex_name_t>::type 
  city_name = get(vertex_name, g);
property_map<Graph, vertex_index2_t>::type
  city_index2 = get(vertex_index2, g);
property_map<Graph, edge_weight_t>::type
  edge_distance = get(edge_weight, g); 

// Create the vertices
typedef graph_traits<Graph>::vertex_descriptor Vertex;
Vertex u1;
u1 = add_vertex(g);
city_name[u1] = "Los Angeles";
city_index2[u1] = 3;

  Vertex u2;
   u2 = add_vertex(g);
  city_name[u2] = "Bakersfield";
  city_index2[u2] = 2;

Vertex u3;
u3 = add_vertex(g);
city_name[u3] = "New York";
city_index2[u3] = 1;

// Create the edges 
typedef graph_traits<Graph>::edge_descriptor Edge;
Edge e1;
e1 = (add_edge(u1, u2, g)).first;
edge_distance[e1] = 100;

Edge e2;
e2 = add_edge(u1, u3, g).first;
edge_distance[e2] = 2500;

In the first section I define the property types, followed by the graph type. Then I create the instance, g, of the graph. Next, I obtain the property access objects that I talked about.

Then I start adding the vertices and edges. To add the vertices, I create my own type called Vertex from the vertex_descriptor, just to simplify the code a bit. I add the vertex by calling the helper function add_vertex, passing in g.

The graph adds the vertex and returns a vertex descriptor. Then I use the property access objects to assign the two properties for the vertex: city_name and city_index2. Setting the properties is easy; I just use the vertex as an index into the map by putting the vertex name in brackets ([]).

Creating the edges is similar, except that the add_edge function returns a pair type rather than an edge type. So I just grab the .first member of the pair to get the edge itself. I save that in a variable; then I use that variable as an index to set the properties. Since mathematically an edge is really nothing more than a set of two vertices, that's all I have to pass to add_edge, along with the graph.

Iterating Through the Edges and Vertices

To iterate through the edges and vertices, you can obtain iterators by calling edges(g) and vertices(g), respectively. These functions return pairs that you can use in your iterations. Here are two blocks of code that iterate through the edges and vertices I created in the preceding section:

// Iterate through the vertices and print them out
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) 
  std::cout << city_name[*vp.first] << " " << city_index2[*vp.first] << std::endl;
std::cout << std::endl;

// Iterate through the edges and print them out
Vertex v1, v2; 
typedef graph_traits<Graph>::edge_iterator edge_iter;
std::pair<edge_iter, edge_iter> ep;
edge_iter ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
  std::cout << edge_distance[*ei] << endl;

I purposely used two approaches in these two blocks of code to demonstrate a certain feature about the pairs that are returned. When I iterated through the vertices, I got back a pair, for which I created a typedef. Then, to access the vertex, I called vp.first. That's an iterator; like most iterators in C++, to get to the instance itself, I dereferenced it. Thus, I could write out the city name and index using this:

city_name[*vp.first]

and this:

city_index2[*vp.first]

If you don't want to work with pairs, however, the library includes a handy helper function called tie, which assigns the individual parts of the pair to the variables passed into the tie function. Since edges(g) returns a pair, calling this:

tie(ei, ei_end) = edges(g)

will save the first item in the pair into ei and the second into ei_end. Then, in the loop, you can access the edge simply with *ei, like so:

edge_distance[*ei]

Solving Problems with Graphs and Boost

Although the Six Degrees of Kevin Bacon game is for fun, the technique used to solve it, called the "Shortest Path" problem, has some practical uses beyond ruminating over movie stars. For example, if you use one of the popular shipping companies to ship a product from Bakersfield, California to Lake Mary, Florida, the shipper needs to find the shortest (that is, the least expensive) path to get the package to the destination. Most likely the package will travel through at least a few cities that the shipper considers hubs. Each city, then, is a vertex on the graph, and cities are connected by edges. The graph is weighted, since the distances between cities vary, as do the time and method to move a package from one city to the next. This is where the problem differs from the Six Degrees problem, since the Six Degrees problem doesn't have weights to the edges.

Mathematicians and computer scientists have developed various algorithms to solve graph theory problems, including the Shortest Path problem. Entire books have been written on the subject of solving problems with graph theory. Certainly, many of the big problems such as those dealing with product shipping involve large numbers of vertices and edges. (Think of the number of cities in the United States, pretty much all served by the United States Post Office.) Thus, these problems are best suited for computers.

The Boost library includes several well-known graph theory algorithms so you don't have to code them yourself. It includes several different Shortest Path algorithms, for example. The thing about the fun Kevin Bacon problem is that it's actually not all that interesting from a graph theory perspective, because all the edge weights are 1; by that I mean that when two actors are connected by having been in a movie together, there isn't a physical distance associated with the connection.

When the edge weight is 1, as with the Kevin Bacon problem, the algorithm becomes identical to an algorithm called "Breadth First Search" (BFS). BFS is used for iterating over vertices, starting at a beginning vertex called the root. The idea is that you start at the root vertex, and spread out to each vertex touching the root, marking each as visited. Then you continue for each of these vertices, visiting each unvisited vertex until you've covered the graph. Or you can stop when you find a particular vertex you want, in which case you've found the shortest path to the vertex you wanted.

The documentation for the Boost library includes a good demonstration of the Kevin Bacon game. Rather than write up similar code here, I suggest just checking out the documentation.

Of more interest to a lot of programmers than the Kevin Bacon game is another interesting problem of file dependencies. Programs such as make and ant as well as spreadsheets need this algorithm. For example, if you're writing spreadsheet software, and the spreadsheet contains cells with formulas referencing other cells, you need to figure out the order in which to evaluate the formulas. If cell A1 has a formula that makes use of cell A2, and A2 has a formula, then you have to evaluate the formula in A2 before you can evaluate the one in A1. That's a dependency algorithm. The same applies to compilation order in programs such as make and ant. If file 1 depends on file 2, then you have to know to compile file 2 before file 1. The documentation for the Boost Graph library includes a sample that solves the file dependency problem.

Conclusion

The Boost library definitely has a sharp learning curve. The documentation doesn't flow nicely, and it takes awhile to wade through it to flesh out the vital topics. However, once you've passed the learning curve, the library is incredibly powerful, and really does make sense. The designers have done a fine job of implementing a library using templates.

Be sure to check out the online documentation; even though I've criticized it a bit here, it contains a lot of useful information. But also look at the samples, as they provide some good starting points. The entire library can be found at the Boost web site.

`dijkstra_shortest_paths`

// named parameter version
template <typename Graph, typename P, typename T, typename R>
void
dijkstra_shortest_paths(Graph& g,
  typename graph_traits<Graph>::vertex_descriptor s, 
  const bgl_named_params<P, T, R>& params);

// non-named parameter version
template <typename Graph, typename DijkstraVisitor , 
	  typename PredecessorMap, typename DistanceMap,
	  typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename  CombineFunction, 
	  typename DistInf, typename DistZero, typename ColorMap = default>
void dijkstra_shortest_paths
  (const Graph& g,
   typename graph_traits<Graph>::vertex_descriptor s,  
   PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
   VertexIndexMap index_map,
   CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
   DijkstraVisitor vis, ColorMap color =  default)

This algorithm [10,8] solves the single-source shortest-paths problem on a weighted, directed or undirected graph for the case where all edge weights are nonnegative. Use the Bellman-Ford algorithm for the case when some edge weights are negative. Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one. For the definition of the shortest-path problem see Section Shortest-Paths Algorithms for some background to the shortest-path problem.

There are two main options for obtaining output from the dijkstra_shortest_paths() function. If you provide a distance property map through the distance_map() parameter then the shortest distance from the source vertex to every other vertex in the graph will be recorded in the distance map. Also you can record the shortest paths tree in a predecessor map: for each vertex u in V, p[u] will be the predecessor of u in the shortest paths tree (unless p[u] = u, in which case u is either the source or a vertex unreachable from the source). In addition to these two options, the user can provide there own custom-made visitor that can takes actions during any of the algorithm's event points.

Dijkstra's algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively ``growing'' the set of vertices S to which it knows the shortest path. At each step of the algorithm, the next vertex added to S is determined by a priority queue. The queue contains the vertices in V - S[1] prioritized by their distance label, which is the length of the shortest path seen so far for each vertex. The vertex u at the top of the priority queue is then added to S, and each of its out-edges is relaxed: if the distance to u plus the weight of the out-edge (u,v) is less than the distance label for v then the estimated distance for vertex v is reduced. The algorithm then loops back, processing the next vertex at the top of the priority queue. The algorithm finishes when the priority queue is empty.

The algorithm uses color markers (white, gray, and black) to keep track of which set each vertex is in. Vertices colored black are in S. Vertices colored white or gray are in V-S. White vertices have not yet been discovered and gray vertices are in the priority queue. By default, the algorithm will allocate an array to store a color marker for each vertex in the graph. You can provide you own storage and access for colors with the color_map() parameter.

The following is the pseudo-code for Dijkstra's single-source shortest paths algorithm. w is the edge weight, d is the distance label, and p is the predecessor of each vertex which is used to encode the shortest paths tree. Q is a priority queue that supports the DECREASE-KEY operation. The visitor event points for the algorithm are indicated by the labels on the right.

DIJKSTRA(G, s, w)
  for each vertex u in V
    d[u] := infinity 
    p[u] := u 
    color[u] := WHITE
  end for
  color[s] := GRAY  
  d[s] := 0 
  INSERT(Q, s)
  while (Q != Ø)
    u := EXTRACT-MIN(Q)
    S := S U { u }
    for each vertex v in Adj[u]
       if (w(u,v) + d[u] < d[v])
        d[v] := w(u,v) + d[u]
        p[v] := u 
        if (color[v] = WHITE) 
          color[v] := GRAY
          INSERT(Q , v) 
        else if (color[v] = GRAY)
          DECREASE-KEY(Q, v)
      else
        ...
    end for
    color[u] := BLACK
  end while 
  return (d, p)

initialize vertex u






discover vertex s

examine vertex u

examine edge (u,v)

edge (u,v) relaxed



discover vertex v 



edge (u,v) not relaxed

finish vertex u

Where Defined

boost/graph/dijkstra_shortest_paths.hpp

Parameters

IN: const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.
Python: The parameter is named graph.

IN: vertex_descriptor s

The source vertex. All distance will be calculated from this vertex, and the shortest paths tree will be rooted at this vertex.
Python: The parameter is named root_vertex.

Named Parameters

IN: weight_map(WeightMap w_map)

The weight or ``length'' of each edge in the graph. The weights must all be non-negative, and the algorithm will throw a negative_edge exception is one of the edges is negative. The type WeightMap must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. The value type for this map must be the same as the value type of the distance map.
Default: get(edge_weight, g)
Python: Must be an edge_double_map for the graph.
Python default: graph.get_edge_double_map("weight")

IN: vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This is necessary for efficient updates of the heap data structure [61] when an edge is relaxed. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacenty_list with VertexList=listS does not have an internal vertex_index property.
Python: Unsupported parameter.

OUT: predecessor_map(PredecessorMap p_map)

The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source. The PredecessorMap type must be a Read/Write Property Map whose key and value types are the same as the vertex descriptor type of the graph.
Default: dummy_property_map
Python: Must be a vertex_vertex_map for the graph.

UTIL/OUT: distance_map(DistanceMap d_map)

The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The type DistanceMap must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map. The value type of the distance map is the element type of a Monoid formed with the combine function object and the zero object for the identity element. Also the distance value type must have a StrictWeakOrdering provided by the compare function object.
Default: iterator_property_map created from a std::vector of the WeightMap's value type of size num_vertices(g) and using the i_map for the index map.
Python: Must be a vertex_double_map for the graph.

IN: distance_compare(CompareFunction cmp)

This function is use to compare distances to determine which vertex is closer to the source vertex. The CompareFunction type must be a model of Binary Predicate and have argument types that match the value type of the DistanceMap property map.
Default: std::less<D> with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

IN: distance_combine(CombineFunction cmb)

This function is used to combine distances to compute the distance of a path. The CombineFunction type must be a model of Binary Function. The first argument type of the binary function must match the value type of the DistanceMap property map and the second argument type must match the value type of the WeightMap property map. The result type must be the same type as the distance value type.
Default: std::plus<D> with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

IN: distance_inf(D inf)

The inf object must be the greatest value of any D object. That is, compare(d, inf) == true for any d != inf. The type D is the value type of the DistanceMap.
Default: std::numeric_limits<D>::max()
Python: Unsupported parameter.

IN: distance_zero(D zero)

The zero value must be the identity element for the Monoid formed by the distance values and the combine function object. The type D is the value type of the DistanceMap.
Default: D()with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

UTIL/OUT: color_map(ColorMap c_map)

This is used during the execution of the algorithm to mark the vertices. The vertices start out white and become gray when they are inserted in the queue. They then turn black when they are removed from the queue. At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white. The type ColorMap must be a model of Read/Write Property Map. A vertex descriptor must be usable as the key type of the map, and the value type of the map must be a model of Color Value.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.
Python: The color map must be a vertex_color_map for the graph.

OUT: visitor(DijkstraVisitor v)

Use this to specify actions that you would like to happen during certain event points within the algorithm. The type DijkstraVisitor must be a model of the Dijkstra Visitor concept. The visitor object is passed by value [2].
Default: dijkstra_visitor<null_visitor>
Python: The parameter should be an object that derives from the DijkstraVisitor type of the graph.

Complexity

The time complexity is O(V log V).

Visitor Event Points

vis.initialize_vertex(u, g) is invoked on each vertex in the graph before the start of the algorithm.
vis.examine_vertex(u, g) is invoked on a vertex as it is removed from the priority queue and added to set S. At this point we know that (p[u],u) is a shortest-paths tree edge so d[u] = delta(s,u) = d[p[u]] + w(p[u],u). Also, the distances of the examined vertices is monotonically increasing d[u₁] <= d[u₂] <= d[u_n].
vis.examine_edge(e, g) is invoked on each out-edge of a vertex immediately after it has been added to set S.
vis.edge_relaxed(e, g) is invoked on edge (u,v) if d[u] + w(u,v) < d[v]. The edge (u,v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree.
vis.discover_vertex(v, g) is invoked on vertex v when the edge (u,v) is examined and v is WHITE. Since a vertex is colored GRAY when it is discovered, each reacable vertex is discovered exactly once. This is also when the vertex is inserted into the priority queue.
vis.edge_not_relaxed(e, g) is invoked if the edge is not relaxed (see above).
vis.finish_vertex(u, g) is invoked on a vertex after all of its out edges have been examined.

Example

See example/dijkstra-example.cpp for an example of using Dijkstra's algorithm.

Notes

[1] The algorithm used here saves a little space by not putting all V - S vertices in the priority queue at once, but instead only those vertices in V - S that are discovered and therefore have a distance less than infinity.

[2] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under the Boost Software License, Version  1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//======================================================================= 
#include <boost/config.hpp>
#include <iostream>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp> 

using namespace boost;

int
main(int, char *[])
{
  typedef adjacency_list < listS, vecS, directedS,
    no_property, property < edge_weight_t, int > > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 
  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;

  const int num_nodes = 5;
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE"; 
  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge); 
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  graph_t g(num_nodes);
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
  for (std::size_t j = 0; j < num_arcs; ++j) { 
    edge_descriptor e; bool inserted;
    tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
    weightmap[e] = weights[j];
  }
#else
  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); 
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

Infinite Lifetimes

Thursday 17 January 2008

Boost Graph Library