Difference between revisions of "Boost/BGL/DijkstraComputePath"
From ProgrammingExamples
Daviddoria (Talk | contribs) |
Daviddoria (Talk | contribs) |
||
Line 17: | Line 17: | ||
#include <vector> | #include <vector> | ||
− | + | 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::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 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; |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
Line 86: | Line 78: | ||
// Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances | // 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 not the same as the above - all distances are returned 0 ??? | ||
+ | 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 | // Output results | ||
Line 91: | Line 95: | ||
NameMap nameMap = boost::get(boost::vertex_name, g); | NameMap nameMap = boost::get(boost::vertex_name, g); | ||
− | BGL_FORALL_VERTICES(v, g, Graph) | + | BGL_FORALL_VERTICES(v, g, Graph) |
{ | { | ||
std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", "; | std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", "; | ||
Line 99: | Line 103: | ||
// Extract a shortest path | // Extract a shortest path | ||
std::cout << std::endl; | std::cout << std::endl; | ||
− | + | ||
− | std::vector< | + | typedef std::vector<Graph::edge_descriptor> PathType; |
− | + | ||
+ | PathType path; | ||
+ | |||
Vertex v = v3; // We want to start at the destination and work our way back to the source | 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 | 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 | v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up | ||
{ | { | ||
− | + | std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g); | |
− | + | Graph::edge_descriptor edge = edgePair.first; | |
− | + | ||
− | + | path.push_back( edge ); | |
− | path.push_back( | + | |
} | } | ||
Line 117: | Line 122: | ||
std::cout << "Shortest path from v0 to v3:" << std::endl; | std::cout << "Shortest path from v0 to v3:" << std::endl; | ||
float totalDistance = 0; | float totalDistance = 0; | ||
− | for( | + | for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator) |
{ | { | ||
− | std::cout << nameMap[pathIterator | + | std::cout << nameMap[boost::source(*pathIterator, g)] << " -> " << nameMap[boost::target(*pathIterator, g)] |
− | + | << " = " << boost::get( boost::edge_weight, g, *pathIterator ) << std::endl; | |
− | + | ||
} | } | ||
− | + | ||
std::cout << std::endl; | std::cout << std::endl; | ||
− | + | ||
− | std::cout << " | + | std::cout << "Distance: " << distanceMap[v3] << std::endl; |
− | + | ||
return EXIT_SUCCESS; | return EXIT_SUCCESS; | ||
} | } | ||
Line 141: | Line 146: | ||
Shortest path from v0 to v3: | Shortest path from v0 to v3: | ||
v0 -> v2 = 2 | v0 -> v2 = 2 | ||
− | v2 -> v3 = | + | v2 -> v3 = 4 |
− | Total distance: | + | Total distance: 6 |
*/ | */ |
Revision as of 18:13, 11 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> int main(int, char *[]) { typedef float 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; // 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)); /* // This is not the same as the above - all distances are returned 0 ??? 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 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; typedef std::vector<Graph::edge_descriptor> PathType; 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 { std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g); Graph::edge_descriptor edge = edgePair.first; path.push_back( edge ); } // Write shortest path std::cout << "Shortest path from v0 to v3:" << std::endl; float totalDistance = 0; for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator) { std::cout << nameMap[boost::source(*pathIterator, g)] << " -> " << nameMap[boost::target(*pathIterator, g)] << " = " << boost::get( boost::edge_weight, g, *pathIterator ) << std::endl; } std::cout << std::endl; std::cout << "Distance: " << distanceMap[v3] << 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 = 4 Total distance: 6 */
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)