Difference between revisions of "Boost/BGL/DijkstraDirected"

From ProgrammingExamples
< Boost‎ | BGL
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
==DijkstraShortestPath.cpp==
+
==DijkstraDirected.cpp==
 
<source lang="cpp">
 
<source lang="cpp">
 +
#include <boost/config.hpp>
 +
#include <iostream>
 +
#include <fstream>
 +
 +
#include <boost/graph/graph_traits.hpp>
 +
#include <boost/graph/dijkstra_shortest_paths.hpp>
 +
#include <boost/graph/adjacency_list.hpp>
 +
 +
int main(int, char *[])
 +
{
 +
  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 boost::graph_traits < Graph >::vertex_descriptor vertex_descriptor;
 +
  typedef boost::graph_traits < Graph >::edge_descriptor edge_descriptor;
 +
  typedef std::pair<int, int> Edge;
 +
 +
  // Create a graph
 +
  Graph g;
 +
 
 +
  Graph::vertex_descriptor v0 = boost::add_vertex(g);
 +
  Graph::vertex_descriptor v1 = boost::add_vertex(g);
 +
  Graph::vertex_descriptor v2 = boost::add_vertex(g);
 +
 +
  // Add weighted edges
 +
  EdgeWeightProperty weight0(5);
 +
  boost::add_edge(v0, v1, weight0, g);
 +
 +
  EdgeWeightProperty weight1 = 3;
 +
  boost::add_edge(v1, v2, weight1, g);
 +
 
 +
  EdgeWeightProperty weight2 = 2;
 +
  boost::add_edge(v2, v0, weight2, g);
 +
 
 +
  // At this point the graph is
 +
  /*  v0
 +
      .
 +
  5  / \ 2
 +
    /___\
 +
    v1 3 v2
 +
  */
 +
 +
  // 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) = 8, parent(2) = 1
 +
 
 +
  which means:
 +
  the distance from v0 to v0 is 0
 +
  the distance from v0 to v1 is 5
 +
  the distance from v0 to v2 is 8
 +
  */
 +
  return EXIT_SUCCESS;
 +
}
  
 
</source>
 
</source>
Line 6: Line 80:
 
==CMakeLists.txt==
 
==CMakeLists.txt==
 
<source lang="cmake">
 
<source lang="cmake">
 +
cmake_minimum_required(VERSION 2.6)
 +
 +
Project(DijkstraDirected)
 +
 +
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(DijkstraDirected DijkstraDirected.cpp)
  
 
</source>
 
</source>

Latest revision as of 08:52, 16 November 2011

DijkstraDirected.cpp

#include <boost/config.hpp>
#include <iostream>
#include <fstream>
 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
 
int main(int, char *[])
{
  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 boost::graph_traits < Graph >::vertex_descriptor vertex_descriptor;
  typedef boost::graph_traits < Graph >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;
 
  // Create a graph
  Graph g;
 
  Graph::vertex_descriptor v0 = boost::add_vertex(g);
  Graph::vertex_descriptor v1 = boost::add_vertex(g);
  Graph::vertex_descriptor v2 = boost::add_vertex(g);
 
  // Add weighted edges
  EdgeWeightProperty weight0(5);
  boost::add_edge(v0, v1, weight0, g);
 
  EdgeWeightProperty weight1 = 3;
  boost::add_edge(v1, v2, weight1, g);
 
  EdgeWeightProperty weight2 = 2;
  boost::add_edge(v2, v0, weight2, g);
 
  // At this point the graph is
  /*   v0
       .
   5  / \ 2
     /___\
    v1 3 v2
  */
 
  // 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) = 8, parent(2) = 1
 
  which means:
  the distance from v0 to v0 is 0
  the distance from v0 to v1 is 5
  the distance from v0 to v2 is 8
  */
  return EXIT_SUCCESS;
}

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
 
Project(DijkstraDirected)
 
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(DijkstraDirected DijkstraDirected.cpp)