The graph route example shows how GGL can be combined with Boost.Graph. The sample does the following things:
Note that this example is useful, but it is only an example. It could be built in many different ways. For example:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <limits>
#include <boost/tuple/tuple.hpp>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/geometry/geometry.hpp>
template <typename Geometry, typename Tuple, typename Box>
void read_wkt(std::string
const& filename, std::vector<Tuple>& tuples, Box& box)
{
std::ifstream cpp_file(filename.c_str());
if (cpp_file.is_open())
{
while (! cpp_file.eof() )
{
std::string line;
std::getline(cpp_file, line);
Geometry geometry;
boost::trim(line);
if (! line.empty() && ! boost::starts_with(line, "#"))
{
std::string name;
std::string::size_type
pos = line.find(
";");
if (pos != std::string::npos)
{
name = line.substr(pos + 1);
line.erase(pos);
boost::trim(line);
boost::trim(name);
}
Geometry geometry;
Tuple tuple(geometry, name);
tuples.push_back(tuple);
}
}
}
}
enum vertex_bg_property_t { vertex_bg_property };
enum edge_bg_property_t { edge_bg_property };
namespace boost
{
BOOST_INSTALL_PROPERTY(vertex, bg_property);
BOOST_INSTALL_PROPERTY(edge, bg_property);
}
template <typename Point>
struct bg_vertex_property
{
bg_vertex_property()
{
}
bg_vertex_property(Point const& loc)
: location(loc)
{
}
Point location;
};
template <typename Linestring>
struct bg_edge_property
{
bg_edge_property(Linestring const& line)
: m_length(boost::geometry::
length(line, haversine))
, m_line(line)
{
}
inline operator double() const
{
return m_length;
}
inline Linestring const& line() const
{
return m_line;
}
private :
double m_length;
Linestring m_line;
};
template <typename M, typename K, typename G>
inline typename boost::graph_traits<G>::vertex_descriptor find_or_insert(M& map, K const& key, G& graph)
{
typename M::const_iterator it = map.find(key);
if (it == map.end())
{
typename boost::graph_traits<G>::vertex_descriptor new_vertex
= boost::add_vertex(graph);
boost::put(
boost::get(vertex_bg_property, graph), new_vertex,
bg_vertex_property<typename M::key_type>(key));
map[key] = new_vertex;
return new_vertex;
}
return it->second;
}
template
<
typename Graph,
typename RoadTupleVector,
typename CityTupleVector
>
void add_roads_and_connect_cities(Graph& graph,
RoadTupleVector const& roads,
CityTupleVector& cities)
{
typedef typename boost::range_value<RoadTupleVector>::type road_type;
typedef typename boost::tuples::element<0, road_type>::type line_type;
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_type;
typedef std::map<point_type, vertex_type, boost::geometry::less<point_type> > map_type;
map_type map;
BOOST_FOREACH(road_type const& road, roads)
{
line_type const& line = road.template get<0>();
vertex_type from = find_or_insert(map, line.front(), graph);
vertex_type to = find_or_insert(map, line.back(), graph);
boost::add_edge(from, to, bg_edge_property<line_type>(line), graph);
}
typedef typename boost::range_value<CityTupleVector>::type city_type;
BOOST_FOREACH(city_type& city, cities)
{
double min_distance = 1e300;
for(typename map_type::const_iterator it = map.begin(); it != map.end(); ++it)
{
if (dist < min_distance)
{
min_distance = dist;
city.template get<2>() = it->second;
}
}
}
}
template <typename Graph, typename Route>
inline void add_edge_to_route(Graph const& graph,
typename boost::graph_traits<Graph>::vertex_descriptor vertex1,
typename boost::graph_traits<Graph>::vertex_descriptor vertex2,
Route& route)
{
std::pair
<
typename boost::graph_traits<Graph>::edge_descriptor,
bool
> opt_edge = boost::edge(vertex1, vertex2, graph);
if (opt_edge.second)
{
bg_edge_property<Route> const& edge_prop =
bg_vertex_property<typename boost::geometry::point_type<Route>::type> const& vertex_prop =
{
std::copy(edge_prop.line().begin(), edge_prop.line().end(),
}
else
{
std::reverse_copy(edge_prop.line().begin(), edge_prop.line().end(),
}
}
}
template <typename Graph, typename Route>
inline void build_route(Graph const& graph,
std::vector<typename boost::graph_traits<Graph>::vertex_descriptor> const& predecessors,
typename boost::graph_traits<Graph>::vertex_descriptor vertex1,
typename boost::graph_traits<Graph>::vertex_descriptor vertex2,
Route& route)
{
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_type;
vertex_type pred = predecessors[vertex2];
add_edge_to_route(graph, vertex2, pred, route);
while (pred != vertex1)
{
add_edge_to_route(graph, predecessors[pred], pred, route);
pred = predecessors[pred];
}
}
int main()
{
<
> point_type;
typedef boost::adjacency_list
<
boost::vecS, boost::vecS, boost::undirectedS
, boost::property<vertex_bg_property_t, bg_vertex_property<point_type> >
, boost::property<edge_bg_property_t, bg_edge_property<line_type> >
> graph_type;
typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_type;
typedef boost::tuple<point_type, std::string, vertex_type> city_type;
std::vector<city_type> cities;
read_wkt<point_type>("data/cities.wkt", cities, box);
typedef boost::tuple<line_type, std::string> road_type;
std::vector<road_type> roads;
read_wkt<line_type>("data/roads.wkt", roads, box);
graph_type graph;
add_roads_and_connect_cities(graph, roads, cities);
double const km = 1000.0;
std::cout << "distances, all in KM" << std::endl
<< std::fixed << std::setprecision(0);
bool first = true;
line_type route;
int const n = boost::num_vertices(graph);
BOOST_FOREACH(city_type const& city1, cities)
{
std::vector<vertex_type> predecessors(n);
std::vector<double> costs(n);
boost::dijkstra_shortest_paths(graph, city1.get<2>(),
&predecessors[0], &costs[0],
std::less<double>(), std::plus<double>(),
(std::numeric_limits<double>::max)(), double(),
boost::dijkstra_visitor<boost::null_visitor>());
BOOST_FOREACH(city_type const& city2, cities)
{
{
double distance = costs[city2.get<2>()] / km;
std::cout
<< std::setiosflags (std::ios_base::left) << std::setw(15)
<< city1.get<1>() << " - "
<< std::setiosflags (std::ios_base::left) << std::setw(15)
<< city2.get<1>()
<< " -> through the air: " << std::setw(4) << acof
<< " , over the road: " << std::setw(4) << distance
<< std::endl;
if (first)
{
build_route(graph, predecessors,
city1.get<2>(), city2.get<2>(),
route);
first = false;
}
}
}
}
#if defined(HAVE_SVG)
std::ofstream stream("routes.svg");
BOOST_FOREACH(road_type const& road, roads)
{
mapper.add(road.get<0>());
}
BOOST_FOREACH(road_type const& road, roads)
{
mapper.map(road.get<0>(),
"stroke:rgb(128,128,128);stroke-width:1");
}
mapper.map(route,
"stroke:rgb(0, 255, 0);stroke-width:6;opacity:0.5");
BOOST_FOREACH(city_type const& city, cities)
{
mapper.map(city.get<0>(),
"fill:rgb(255,255,0);stroke:rgb(0,0,0);stroke-width:1");
mapper.text(city.get<0>(), city.get<1>(),
"fill:rgb(0,0,0);font-family:Arial;font-size:10px", 5, 5);
}
#endif
return 0;
}