BGL Dijkstra Shortest Paths with Associated Properties
I am trying to use the dijkstra shortest path algorithm in BGL to compute a simple ST path on an unweighted undirected graph. I may take care of the weights in the future, but for now I just want to treat edge traversal as a single cost.
I also keep track of several edge and vertex properties, so I based what I have done so far on a nested property example that seemed to be the closest thing to what I am trying to do.
Now I'm trying to figure out how to get dijkstra to work so that I can search in ST, but I'm stuck on getting the correct parameters configured for it.
Here's a simplified example of the code I have so far:
#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
// Create a struct to hold properties for each vertex
typedef struct VertexProperties
{
int p1;
} VertexProperties;
// Create a struct to hold properties for each edge
typedef struct EdgeProperties
{
int p1;
} EdgeProperties;
// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;
int main(int,char*[])
{
// Create a graph object
Graph g;
// Add vertices
Graph::vertex_descriptor v0 = boost::add_vertex(g);
Graph::vertex_descriptor v1 = boost::add_vertex(g);
Graph::vertex_descriptor v2 = boost::add_vertex(g);
// Set vertex properties
g[v0].p1 = 1;
g[v1].p1 = 2;
g[v2].p1 = 3;
// Add edges
std::pair<Graph::edge_descriptor, bool> e01 = boost::add_edge(v0, v1, g);
std::pair<Graph::edge_descriptor, bool> e02 = boost::add_edge(v1, v2, g);
// Set edge properties
g[e01.first].p1 = 1;
g[e02.first].p1 = 2;
std::cout << "num_verts: " << boost::num_vertices(g) << std::endl;
std::cout << "num_edges: " << boost::num_edges(g) << std::endl;
// compute ST shortest paths here...
return 0;
}
I am trying to set up the correct parameters for calling dijkstra algorithm. They take a graph, an initial vertex, and then a predecessor map and a distance map. The examples I've seen so far, such as this one , have created their graph with only edge weights, with no associated edge properties, making it easier to work with.
Ultimately, I'm after the shortest path ST, so I need to reconstruct the path from S to T. From the appearance, we need to create a predecessor map, and then can we use it to retrieve the path from a specific T back to S?
It should also be noted that the environment in which I work does not allow using the capabilities of the C ++ 11 language .:(
Any help here would be greatly appreciated!
source to share
So the question was how to use the bound property as a weightmap with the Boost Graph library? ".
Good. You are using property cards. The compiled property can be accessed with a little funky syntax document right on the Related Properties page: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html , see Property Header maps from connected properties ".
Now for a quick demonstration:
// set up a weight map:
auto weights = boost::get(&EdgeProperties::p1, g);
Passing the minimum number of arguments to dijkstra:
// you can pass it to dijkstra using direct or named params. Let do the simplest
boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));
You need to add additional parameters, but hey, this is your start :)
#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
// Create a struct to hold properties for each vertex
struct VertexProperties { int p1; };
// Create a struct to hold properties for each edge
struct EdgeProperties { int p1; };
// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;
int main() {
// Create a graph object
Graph g;
// Add vertices
auto v0 = boost::add_vertex({1}, g),
v1 = boost::add_vertex({2}, g),
v2 = boost::add_vertex({3}, g);
// Add edges
boost::add_edge(v0, v1, EdgeProperties{1}, g);
boost::add_edge(v1, v2, EdgeProperties{2}, g);
boost::print_graph(g, boost::get(&VertexProperties::p1, g));
// set up a weight map:
auto weights = boost::get(&EdgeProperties::p1, g);
// you can pass itprint_graph`enter code here` to dijkstra using direct or named params. Let do the simplest
boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));
}
You will notice that I have simplified the initialization of the vertex / edge properties. The print_graph utility is neat if you want to have an idea of what a graph looks like (not using Graphviz).
Conclusion on Coliru:
1 <--> 2
2 <--> 1 3
3 <--> 2
source to share
I am adding a "complete" version of dijkstra's shortest path search, which calculates the shortest path from S to T for archival purposes.
I'm sure there are better ways to do this, but it works on my end.
http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html was a really helpful link.
///
/// @file bgl_st_example.cpp
///
/// @brief bundled property example
///
/// @ref http://programmingexamples.net/wiki/CPP/Boost/BGL/BundledProperties
///
#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
// Create a struct to hold properties for each vertex
typedef struct vertex_properties
{
std::string label;
int p1;
} vertex_properties_t;
// Create a struct to hold properties for each edge
typedef struct edge_properties
{
std::string label;
int p1;
int weight;
} edge_properties_t;
// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_properties_t, edge_properties_t> graph_t;
typedef graph_t::vertex_descriptor vertex_descriptor_t;
typedef graph_t::edge_descriptor edge_descriptor_t;
typedef boost::property_map<graph_t, boost::vertex_index_t>::type index_map_t;
typedef boost::iterator_property_map<vertex_descriptor_t*, index_map_t*, vertex_descriptor_t, vertex_descriptor_t&> predecessor_map_t;
// The graph, with edge weights labeled.
//
// v1 --(1)-- v2
// | \_ |
// | \ |
// (1) (3) (2)
// | \_ |
// | \ |
// v4 --(1)-- v3
//
//
int main(int,char*[])
{
// Create a graph object
graph_t g;
// Add vertices
vertex_descriptor_t v1 = boost::add_vertex(g);
vertex_descriptor_t v2 = boost::add_vertex(g);
vertex_descriptor_t v3 = boost::add_vertex(g);
vertex_descriptor_t v4 = boost::add_vertex(g);
// Set vertex properties
g[v1].p1 = 1; g[v1].label = "v1";
g[v2].p1 = 2; g[v2].label = "v2";
g[v3].p1 = 3; g[v3].label = "v3";
g[v4].p1 = 4; g[v4].label = "v4";
// Add edges
std::pair<edge_descriptor_t, bool> e01 = boost::add_edge(v1, v2, g);
std::pair<edge_descriptor_t, bool> e02 = boost::add_edge(v2, v3, g);
std::pair<edge_descriptor_t, bool> e03 = boost::add_edge(v3, v4, g);
std::pair<edge_descriptor_t, bool> e04 = boost::add_edge(v4, v1, g);
std::pair<edge_descriptor_t, bool> e05 = boost::add_edge(v1, v3, g);
// Set edge properties
g[e01.first].p1 = 1; g[e01.first].weight = 1; g[e01.first].label = "v1-v2";
g[e02.first].p1 = 2; g[e02.first].weight = 2; g[e02.first].label = "v2-v3";
g[e03.first].p1 = 3; g[e03.first].weight = 1; g[e03.first].label = "v3-v4";
g[e04.first].p1 = 4; g[e04.first].weight = 1; g[e04.first].label = "v4-v1";
g[e05.first].p1 = 5; g[e05.first].weight = 3; g[e05.first].label = "v1-v3";
// Print out some useful information
std::cout << "Graph:" << std::endl;
boost::print_graph(g, boost::get(&vertex_properties_t::label,g));
std::cout << "num_verts: " << boost::num_vertices(g) << std::endl;
std::cout << "num_edges: " << boost::num_edges(g) << std::endl;
// BGL Dijkstra Shortest Paths here...
std::vector<int> distances( boost::num_vertices(g));
std::vector<vertex_descriptor_t> predecessors(boost::num_vertices(g));
boost::dijkstra_shortest_paths(g, v1,
boost::weight_map(boost::get(&edge_properties_t::weight,g))
.distance_map(boost::make_iterator_property_map(distances.begin(), boost::get(boost::vertex_index,g)))
.predecessor_map(boost::make_iterator_property_map(predecessors.begin(), boost::get(boost::vertex_index,g)))
);
// Extract the shortest path from v1 to v3.
typedef std::vector<edge_descriptor_t> path_t;
path_t path;
vertex_descriptor_t v = v3;
for(vertex_descriptor_t u = predecessors[v]; u != v; v=u, u=predecessors[v])
{
std::pair<edge_descriptor_t,bool> edge_pair = boost::edge(u,v,g);
path.push_back( edge_pair.first );
}
std::cout << std::endl;
std::cout << "Shortest Path from v1 to v3:" << std::endl;
for(path_t::reverse_iterator riter = path.rbegin(); riter != path.rend(); ++riter)
{
vertex_descriptor_t u_tmp = boost::source(*riter, g);
vertex_descriptor_t v_tmp = boost::target(*riter, g);
edge_descriptor_t e_tmp = boost::edge(u_tmp, v_tmp, g).first;
std::cout << " " << g[u_tmp].label << " -> " << g[v_tmp].label << " (weight: " << g[e_tmp].weight << ")" << std::endl;
}
return 0;
}
Here is the CMakeLists.txt file that works for me:
cmake_minimum_required(VERSION 2.8)
project ( bgl_example )
find_package( Boost REQUIRED COMPONENTS )
include_directories( ${Boost_INCLUDE_DIR} )
add_executable( bgl_st_example bgl_st_example.cpp)
target_link_libraries( bgl_st_example ${Boost_LIBRARIES} )
The result I see is:
Graph:
v1 <--> v2 v4 v3
v2 <--> v1 v3
v3 <--> v2 v4 v1
v4 <--> v3 v1
num_verts: 4
num_edges: 5
Shortest Path from v1 to v3:
v1 -> v4 (weight: 1)
v4 -> v3 (weight: 1)
source to share