Boost/BGL/DijkstraComputePath - Revision history

Daviddoria: moved CPP/Boost/BGL/DijkstraComputePath to Boost/BGL/DijkstraComputePath

2011-11-16T12:52:42Z

moved CPP/Boost/BGL/DijkstraComputePath to Boost/BGL/DijkstraComputePath

Daviddoria at 20:52, 14 June 2011

2011-06-14T20:52:52Z

Daviddoria at 22:13, 11 June 2011

2011-06-11T22:13:48Z

Daviddoria at 21:32, 8 June 2011

2011-06-08T21:32:53Z

Show changes

Daviddoria: Created page with 'The Dijkstra algorithm in Boost computes the shortest path from a specified vertex to ALL other vertices in the graph. Many times we are interested in the path to one specific ve…'

2011-06-08T01:27:36Z

Created page with 'The Dijkstra algorithm in Boost computes the shortest path from a specified vertex to ALL other vertices in the graph. Many times we are interested in the path to one specific ve…'

New page

The Dijkstra algorithm in Boost computes the shortest path from a specified vertex to ALL other vertices in the graph. Many times we are interested in the path to one specific vertex. The custom function GetShortestPath follows the 'parents' in the data returned by the Dijkstra algorithm to get the path of interest.

==DijkstraComputePath.cpp==
<source lang="cpp">
#include <boost/config.hpp>
#include <iostream>
#include <fstream>

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

typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty;

typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
boost::no_property, EdgeWeightProperty > Graph;

typedef Graph::vertex_descriptor vertex_descriptor;

std::vector<unsigned int> GetShortestPath(Graph& g, vertex_descriptor start, vertex_descriptor end);
std::vector<unsigned int> ReverseVector(std::vector<unsigned int> &v);

int main(int, char *[])
{
// Create a graph
Graph g;

vertex_descriptor v0 = boost::add_vertex(g);
vertex_descriptor v1 = boost::add_vertex(g);
vertex_descriptor v2 = boost::add_vertex(g);
vertex_descriptor v3 = boost::add_vertex(g);

// Add weighted edges
EdgeWeightProperty weight0(5);
boost::add_edge(v0, v1, weight0, g);

EdgeWeightProperty weight1(3);
boost::add_edge(v1, v3, weight1, g);

EdgeWeightProperty weight2(2);
boost::add_edge(v0, v2, weight2, g);

EdgeWeightProperty weight3(4);
boost::add_edge(v2, v3, weight3, g);

// At this point the graph is
/* v0
.
/ \ 2
/ \
/ . v2
5/ \
/ \ 4
/ \
v1---------- v3
3
*/

// Create things for Dijkstra
std::vector<vertex_descriptor> parents(boost::num_vertices(g)); // To store parents
std::vector<int> distances(boost::num_vertices(g)); // To store distances

// Compute shortest paths from v0 to all vertices, and store the output in parents and distances
boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(&parents[0]).distance_map(&distances[0]));

// Output results
std::cout << "distances and parents:" << std::endl;
boost::graph_traits < Graph >::vertex_iterator vertexIterator, vend;
for (boost::tie(vertexIterator, vend) = boost::vertices(g); vertexIterator != vend; ++vertexIterator)
{
std::cout << "distance(" << *vertexIterator << ") = " << distances[*vertexIterator] << ", ";
std::cout << "parent(" << *vertexIterator << ") = " << parents[*vertexIterator] << std::endl;
}
std::cout << std::endl;

/*
The output is:
distance(0) = 0, parent(0) = 0
distance(1) = 5, parent(1) = 0
distance(2) = 2, parent(2) = 0
distance(3) = 6, parent(3) = 2

which means:
the distance from v0 to v0 is 0 and it is reached directly
the distance from v0 to v1 is 5 and it is reached directly
the distance from v0 to v2 is 2 and it is reached directly
the distance from v0 to v3 is 6 and it is reached via v2
*/

std::vector<unsigned int> shortestPath = GetShortestPath(g, v0, v3);

for(unsigned int i = 0; i < shortestPath.size(); ++i)
{
std::cout << shortestPath[i] << " ";
}
std::cout << std::endl;

return EXIT_SUCCESS;
}

std::vector<unsigned int> GetShortestPath(Graph& g, Graph::vertex_descriptor start, Graph::vertex_descriptor end)
{
// Create things for Dijkstra
std::vector<vertex_descriptor> parents(boost::num_vertices(g)); // To store parents
std::vector<int> distances(boost::num_vertices(g)); // To store distances

// Compute shortest paths from 'start' to all vertices, and store the output in parents and distances
boost::dijkstra_shortest_paths(g, start, boost::predecessor_map(&parents[0]).distance_map(&distances[0]));

// Create a vector in which to store the path
std::vector<unsigned int> shortestPath;

// Start at the end and work back to the beginning (aka Backtracking algorithm)
vertex_descriptor currentVertex = end;

std::cout << "Starting at " << currentVertex << " and looking for " << start << std::endl;

while(parents[currentVertex] != start)
{
std::cout << "currentVertex: " << currentVertex << std::endl;
std::cout << "current parent: " << parents[currentVertex] << std::endl;
shortestPath.push_back(currentVertex);
currentVertex = parents[currentVertex];
}

// The next to last vertex will not be added (one after 'start'), so add it manually
shortestPath.push_back(currentVertex);

// Add the 'start' vertex to the path
shortestPath.push_back(start);

return ReverseVector(shortestPath);
}

std::vector<unsigned int> ReverseVector(std::vector<unsigned int> &v)
{
std::vector<unsigned int> result;

for(int i = v.size() - 1; i >= 0; --i) // this is not unsigned because I'm not sure about the behavior of the comparison when it gets near zero
{
result.push_back(v[i]);
}

return result;
}
</source>

==CMakeLists.txt==
<source lang="cmake">
cmake_minimum_required(VERSION 2.6)

Project(DijkstraComputePath)

set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS program_options required)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(DijkstraComputePath DijkstraComputePath.cpp)
</source>

@@ Line 77: / Line 77: @@
    // Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances
-   boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap).distance_map(distanceMap));
+   // boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap).distance_map(distanceMap));
+   // This is exactly the same as the above line - it is the idea of "named parameters" - you can pass the
-/*
+   // prdecessor map and the distance map in any order.
-   // This is not the same as the above - all distances are returned 0 ???
+   boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap));
-  IndexMap indexMap = boost::get(boost::vertex_index, g);
-−
-  DistanceMap distanceMap(&distances[0], indexMap);
-−
-  PredecessorMap predecessorMap(&predecessors[0], indexMap);
-  boost::predecessor_map(predecessorMap).distance_map(distanceMap);
-   // Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances
    boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap));
-*/
    // Output results

@@ Line 17: / Line 17: @@
 #include <vector>
-typedef int Weight;
+int main(int, char *[])
 typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
-typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
+  typedef float Weight;
-typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
+  typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
-  NameProperty, WeightProperty > Graph;
+    NameProperty, WeightProperty > Graph;
-typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
+  typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
-typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
+  typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
-typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
+  typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
-typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
+  typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
-typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;
+  typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;
-−
-struct PathType
-−
-  Vertex Source;
-  Vertex Desintation;
-  float Distance;
-};
-−
-int main(int, char *[])
-−
@@ Line 86: / Line 78: @@
    // Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances
    boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap).distance_map(distanceMap));
    // Output results
@@ Line 91: / Line 95: @@
    NameMap nameMap = boost::get(boost::vertex_name, g);
    BGL_FORALL_VERTICES(v, g, Graph)
+   {
      std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", ";
@@ Line 99: / Line 103: @@
    // Extract a shortest path
    std::cout << std::endl;
-−
-   std::vector<PathType> path;
+   typedef std::vector<Graph::edge_descriptor> PathType;
-−
    Vertex v = v3; // We want to start at the destination and work our way back to the source
    for(Vertex u = predecessorMap[v]; // Start by setting 'u' to the destintaion node's predecessor
@@ Line 107: / Line 113: @@
        v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up
+   {
-     PathType step;
+     std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g);
-    step.Source = u;
+     Graph::edge_descriptor edge = edgePair.first;
-     step.Desintation = v;
-    step.Distance = distanceMap[v];
+     path.push_back( edge );
-     path.push_back( step );
+   }
@@ Line 117: / Line 122: @@
    std::cout << "Shortest path from v0 to v3:" << std::endl;
    float totalDistance = 0;
-   for(std::vector<PathType>::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator)
+   for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator)
+   {
-     std::cout << nameMap[pathIterator->Source] << " -> " << nameMap[pathIterator->Desintation]
+     std::cout << nameMap[boost::source(*pathIterator, g)] << " -> " << nameMap[boost::target(*pathIterator, g)]
-	      << " = " << pathIterator->Distance << std::endl;
+              << " = " << boost::get( boost::edge_weight, g, *pathIterator ) << std::endl;
-    totalDistance += pathIterator->Distance;
+   }
-−
    std::cout << std::endl;
-−
-   std::cout << "Total distance: " << totalDistance << std::endl;
+   std::cout << "Distance: " << distanceMap[v3] << std::endl;
-−
    return EXIT_SUCCESS;
+}
@@ Line 141: / Line 146: @@
 Shortest path from v0 to v3:
 v0 -> v2 = 2
-v2 -> v3 = 6
+v2 -> v3 = 4
-Total distance: 8
+Total distance: 6
 */

← Older revision	Revision as of 12:52, 16 November 2011
(No difference)