Difference between revisions of "Boost/BGL/DijkstraComputePath"
From ProgrammingExamples
Daviddoria (Talk | contribs) (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…') |
Daviddoria (Talk | contribs) |
||
Line 4: | Line 4: | ||
<source lang="cpp"> | <source lang="cpp"> | ||
#include <boost/config.hpp> | #include <boost/config.hpp> | ||
− | |||
− | |||
− | |||
#include <boost/graph/adjacency_list.hpp> | #include <boost/graph/adjacency_list.hpp> | ||
+ | #include <boost/graph/dijkstra_shortest_paths.hpp> | ||
+ | #include <boost/graph/graph_traits.hpp> | ||
+ | #include <boost/graph/iteration_macros.hpp> | ||
+ | #include <boost/graph/properties.hpp> | ||
+ | |||
+ | #include <boost/property_map/property_map.hpp> | ||
+ | |||
+ | #include <iostream> | ||
+ | #include <utility> | ||
+ | #include <vector> | ||
− | typedef boost::property<boost::edge_weight_t, | + | typedef int Weight; |
+ | typedef boost::property<boost::edge_weight_t, Weight> WeightProperty; | ||
+ | typedef boost::property<boost::vertex_name_t, std::string> NameProperty; | ||
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, | typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, | ||
− | + | NameProperty, WeightProperty > Graph; | |
− | typedef Graph::vertex_descriptor | + | 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_name_t >::type NameMap; | |
+ | |||
+ | typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap; | ||
+ | typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap; | ||
+ | |||
+ | struct PathType | ||
+ | { | ||
+ | Vertex Source; | ||
+ | Vertex Desintation; | ||
+ | float Distance; | ||
+ | }; | ||
int main(int, char *[]) | int main(int, char *[]) | ||
{ | { | ||
+ | |||
+ | |||
// Create a graph | // Create a graph | ||
Graph g; | Graph g; | ||
− | + | ||
− | + | // Add named vertices | |
− | + | Vertex v0 = boost::add_vertex(std::string("v0"), g); | |
− | + | Vertex v1 = boost::add_vertex(std::string("v1"), g); | |
− | + | Vertex v2 = boost::add_vertex(std::string("v2"), g); | |
+ | Vertex v3 = boost::add_vertex(std::string("v3"), g); | ||
// Add weighted edges | // Add weighted edges | ||
− | + | Weight weight0 = 5; | |
+ | Weight weight1 = 3; | ||
+ | Weight weight2 = 2; | ||
+ | Weight weight3 = 4; | ||
+ | |||
boost::add_edge(v0, v1, weight0, g); | boost::add_edge(v0, v1, weight0, g); | ||
− | |||
− | |||
boost::add_edge(v1, v3, weight1, g); | boost::add_edge(v1, v3, weight1, g); | ||
− | |||
− | |||
boost::add_edge(v0, v2, weight2, g); | boost::add_edge(v0, v2, weight2, g); | ||
− | |||
− | |||
boost::add_edge(v2, v3, weight3, g); | boost::add_edge(v2, v3, weight3, g); | ||
− | + | ||
// At this point the graph is | // At this point the graph is | ||
− | /* | + | /* v0 |
− | + | . | |
− | + | / \ 2 | |
− | + | / \ | |
− | + | / . v2 | |
− | + | 5/ \ | |
− | + | / \ 4 | |
− | + | / \ | |
− | v1---------- v3 | + | v1----------- v3 |
3 | 3 | ||
*/ | */ | ||
// Create things for Dijkstra | // Create things for Dijkstra | ||
− | std::vector< | + | std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents |
− | std::vector< | + | std::vector<Weight> distances(boost::num_vertices(g)); // To store distances |
− | // Compute shortest paths from v0 to all vertices, and store the output in | + | IndexMap indexMap = boost::get(boost::vertex_index, g); |
− | boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map( | + | PredecessorMap predecessorMap(&predecessors[0], indexMap); |
+ | DistanceMap distanceMap(&distances[0], indexMap); | ||
+ | |||
+ | // 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 | // Output results | ||
std::cout << "distances and parents:" << std::endl; | std::cout << "distances and parents:" << std::endl; | ||
− | boost:: | + | NameMap nameMap = boost::get(boost::vertex_name, g); |
− | + | ||
+ | BGL_FORALL_VERTICES(v, g, Graph) | ||
{ | { | ||
− | std::cout << "distance(" << | + | std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", "; |
− | std::cout << " | + | std::cout << "predecessor(" << nameMap[v] << ") = " << nameMap[predecessorMap[v]] << std::endl; |
} | } | ||
+ | |||
+ | // Extract a shortest path | ||
std::cout << std::endl; | std::cout << std::endl; | ||
− | + | std::vector<PathType> path; | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | 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 | |
− | + | u != v; // Keep tracking the path until we get to the source | |
− | + | v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
{ | { | ||
− | + | PathType step; | |
+ | step.Source = u; | ||
+ | step.Desintation = v; | ||
+ | step.Distance = distanceMap[v]; | ||
+ | path.push_back( step ); | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | + | // Write shortest path | |
− | + | std::cout << "Shortest path from v0 to v3:" << std::endl; | |
− | // | + | float totalDistance = 0; |
− | std:: | + | for(std::vector<PathType>::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator) |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
{ | { | ||
− | std::cout << " | + | std::cout << nameMap[pathIterator->Source] << " -> " << nameMap[pathIterator->Desintation] |
− | + | << " = " << pathIterator->Distance << std::endl; | |
− | + | totalDistance += pathIterator->Distance; | |
− | + | ||
} | } | ||
− | + | std::cout << std::endl; | |
− | + | ||
− | + | std::cout << "Total distance: " << totalDistance << std::endl; | |
− | + | ||
− | return | + | return EXIT_SUCCESS; |
} | } | ||
− | + | /* | |
− | + | * Output: | |
− | + | distances and parents: | |
− | + | distance(v0, v0) = 0, predecessor(v0) = v0 | |
− | + | distance(v0, v1) = 5, predecessor(v1) = v0 | |
− | + | distance(v0, v2) = 2, predecessor(v2) = v0 | |
− | + | distance(v0, v3) = 6, predecessor(v3) = v2 | |
− | + | ||
− | + | Shortest path from v0 to v3: | |
− | + | v0 -> v2 = 2 | |
− | + | v2 -> v3 = 6 | |
+ | |||
+ | Total distance: 8 | ||
+ | |||
+ | */ | ||
</source> | </source> | ||
Revision as of 17:32, 8 June 2011
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
#include <boost/config.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/properties.hpp> #include <boost/property_map/property_map.hpp> #include <iostream> #include <utility> #include <vector> typedef int Weight; typedef boost::property<boost::edge_weight_t, Weight> WeightProperty; typedef boost::property<boost::vertex_name_t, std::string> NameProperty; typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, NameProperty, WeightProperty > Graph; 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_name_t >::type NameMap; typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap; typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap; struct PathType { Vertex Source; Vertex Desintation; float Distance; }; int main(int, char *[]) { // Create a graph Graph g; // Add named vertices Vertex v0 = boost::add_vertex(std::string("v0"), g); Vertex v1 = boost::add_vertex(std::string("v1"), g); Vertex v2 = boost::add_vertex(std::string("v2"), g); Vertex v3 = boost::add_vertex(std::string("v3"), g); // Add weighted edges Weight weight0 = 5; Weight weight1 = 3; Weight weight2 = 2; Weight weight3 = 4; boost::add_edge(v0, v1, weight0, g); boost::add_edge(v1, v3, weight1, g); boost::add_edge(v0, v2, weight2, g); 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> predecessors(boost::num_vertices(g)); // To store parents std::vector<Weight> distances(boost::num_vertices(g)); // To store distances IndexMap indexMap = boost::get(boost::vertex_index, g); PredecessorMap predecessorMap(&predecessors[0], indexMap); DistanceMap distanceMap(&distances[0], indexMap); // 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 std::cout << "distances and parents:" << std::endl; NameMap nameMap = boost::get(boost::vertex_name, g); BGL_FORALL_VERTICES(v, g, Graph) { std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", "; std::cout << "predecessor(" << nameMap[v] << ") = " << nameMap[predecessorMap[v]] << std::endl; } // Extract a shortest path std::cout << std::endl; std::vector<PathType> path; 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 u != v; // Keep tracking the path until we get to the source v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up { PathType step; step.Source = u; step.Desintation = v; step.Distance = distanceMap[v]; path.push_back( step ); } // Write shortest path 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) { std::cout << nameMap[pathIterator->Source] << " -> " << nameMap[pathIterator->Desintation] << " = " << pathIterator->Distance << std::endl; totalDistance += pathIterator->Distance; } std::cout << std::endl; std::cout << "Total distance: " << totalDistance << std::endl; return EXIT_SUCCESS; } /* * Output: distances and parents: distance(v0, v0) = 0, predecessor(v0) = v0 distance(v0, v1) = 5, predecessor(v1) = v0 distance(v0, v2) = 2, predecessor(v2) = v0 distance(v0, v3) = 6, predecessor(v3) = v2 Shortest path from v0 to v3: v0 -> v2 = 2 v2 -> v3 = 6 Total distance: 8 */
CMakeLists.txt
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)