[Boost-commit] svn:boost r63338 - sandbox/geometry/libs/geometry/example

Subject: [Boost-commit] svn:boost r63338 - sandbox/geometry/libs/geometry/example
From: barend.gehrels_at_[hidden]
Date: 2010-06-26 06:09:02

Author: barendgehrels
Date: 2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
New Revision: 63338
URL: http://svn.boost.org/trac/boost/changeset/63338

Log:
Split graph example into one with traditional properties (the original one), and one using bundled properties
Added:
   sandbox/geometry/libs/geometry/example/07_a_graph_route_example.cpp
      - copied unchanged from r62192, /sandbox/geometry/libs/geometry/example/07_graph_route_example.cpp
   sandbox/geometry/libs/geometry/example/07_a_graph_route_example.vcproj
      - copied, changed from r62192, /sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj
   sandbox/geometry/libs/geometry/example/07_b_graph_route_example.cpp   (contents, props changed)
   sandbox/geometry/libs/geometry/example/07_b_graph_route_example.vcproj   (contents, props changed)
Removed:
   sandbox/geometry/libs/geometry/example/07_graph_route_example.cpp
   sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj
Text files modified: 
   sandbox/geometry/libs/geometry/example/07_a_graph_route_example.vcproj |    10 +++++-----                              
   sandbox/geometry/libs/geometry/example/Jamfile.v2                      |     3 ++-                                     
   sandbox/geometry/libs/geometry/example/basic_examples.sln              |    18 ++++++++++++------                      
   3 files changed, 19 insertions(+), 12 deletions(-)

Copied: sandbox/geometry/libs/geometry/example/07_a_graph_route_example.vcproj (from r62192, /sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj)
==============================================================================
--- /sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj	(original)
+++ sandbox/geometry/libs/geometry/example/07_a_graph_route_example.vcproj	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
@@ -2,9 +2,9 @@
 <VisualStudioProject
         ProjectType="Visual C++"
         Version="8.00"
-	Name="07_graph_route_example"
+	Name="07_a_graph_route_example"
         ProjectGUID="{47D30DD8-CBB1-4527-811F-F0193E22B317}"
-	RootNamespace="07_graph_route_example"
+	RootNamespace="07_a_graph_route_example"
         Keyword="Win32Proj"
 	>
         <Platforms>
@@ -18,7 +18,7 @@
                 <Configuration
                         Name="Debug|Win32"
                         OutputDirectory="$(SolutionDir)$(ConfigurationName)"
-			IntermediateDirectory="$(ConfigurationName)\07_graph_route_example"
+			IntermediateDirectory="$(ConfigurationName)\07_a_graph_route_example"
                         ConfigurationType="1"
                         InheritedPropertySheets=".\boost.vsprops"
                         CharacterSet="1"
@@ -90,7 +90,7 @@
                 <Configuration
                         Name="Release|Win32"
                         OutputDirectory="$(SolutionDir)$(ConfigurationName)"
-			IntermediateDirectory="$(ConfigurationName)\07_graph_route_example"
+			IntermediateDirectory="$(ConfigurationName)\07_a_graph_route_example"
                         ConfigurationType="1"
                         InheritedPropertySheets=".\boost.vsprops"
                         CharacterSet="1"
@@ -162,7 +162,7 @@
         </References>
         <Files>
                 <File
-			RelativePath=".\07_graph_route_example.cpp"
+			RelativePath=".\07_a_graph_route_example.cpp"
 			>
                 </File>
         </Files>

Added: sandbox/geometry/libs/geometry/example/07_b_graph_route_example.cpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/libs/geometry/example/07_b_graph_route_example.cpp	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
@@ -0,0 +1,372 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands
+// Copyright Bruno Lalande 2008, 2009
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Example showing GGL combined with Boost.Graph, calculating shortest routes
+// input: two WKT's, provided in subfolder data
+// output: text, + an SVG, displayable in e.g. Firefox)
+
+
+// Second variant, with bundled properties
+
+
+#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>
+#include <boost/geometry/geometries/cartesian2d.hpp>
+
+
+// Yes, this example currently uses some extensions:
+
+    // For input:
+    #include <boost/geometry/extensions/gis/io/wkt/read_wkt.hpp>
+
+    // For output:
+    #include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
+
+    // For distance-calculations over the Earth:
+    #include <boost/geometry/extensions/gis/geographic/strategies/andoyer.hpp>
+
+
+
+// Read an ASCII file containing WKT's, fill a vector of tuples
+// The tuples consist of at least <0> a geometry and <1> an identifying string
+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;
+
+                // Split at ';', if any
+                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;
+                boost::geometry::read_wkt(line, geometry);
+
+                Tuple tuple(geometry, name);
+
+                tuples.push_back(tuple);
+                boost::geometry::combine(box, boost::geometry::make_envelope<Box>(geometry));
+            }
+        }
+    }
+}
+
+
+
+// Define properties for vertex
+template <typename Point>
+struct bg_vertex_property
+{
+    bg_vertex_property()
+    {
+        boost::geometry::assign_zero(location);
+    }
+    bg_vertex_property(Point const& loc)
+    {
+        location = loc;
+    }
+
+    Point location;
+};
+
+// Define properties for edge
+template <typename Linestring>
+struct bg_edge_property
+{
+    bg_edge_property(Linestring const& line)
+        : m_line(line)
+    {
+        length = boost::geometry::length(line);
+    }
+
+    inline Linestring const& line() const
+    {
+        return m_line;
+    }
+
+    double length;
+private :
+    Linestring m_line;
+};
+
+// Utility function to add a vertex to a graph. It might exist already. Then do not insert,
+// but return vertex descriptor back. It might not exist. Then add it (and return).
+// To efficiently handle this, a std::map is used.
+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())
+    {
+        // Add a vertex to the graph
+        typename boost::graph_traits<G>::vertex_descriptor new_vertex
+            = boost::add_vertex(bg_vertex_property<typename M::key_type>(key), graph);
+
+        // Add to the map, using POINT as 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::geometry::point_type<line_type>::type point_type;
+
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_type;
+
+    // Define a map to be used during graph filling
+    // Maps from point to vertex-id's
+    typedef std::map<point_type, vertex_type, boost::geometry::less<point_type> > map_type;
+    map_type map;
+
+
+    // Fill the graph
+    BOOST_FOREACH(road_type const& road, roads)
+    {
+        line_type const& line = road.template get<0>();
+        // Find or add begin/end point of these line
+        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);
+    }
+
+    // Find nearest graph vertex for each city, using the map
+    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)
+        {
+            double dist = boost::geometry::distance(it->first, city.template get<0>());
+            if (dist < min_distance)
+            {
+                min_distance = dist;
+                // Set the vertex
+                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)
+    {
+        // Get properties of edge and of vertex
+        bg_edge_property<Route> const& edge_prop = graph[opt_edge.first];
+        bg_vertex_property
+            <
+                typename boost::geometry::point_type<Route>::type
+            > const& vertex_prop = graph[vertex2];
+
+        // Depending on how edge connects to vertex, copy it forward or backward
+        if (boost::geometry::equals(edge_prop.line().front(), vertex_prop.location))
+        {
+            std::copy(edge_prop.line().begin(), edge_prop.line().end(),
+                std::back_inserter(route));
+        }
+        else
+        {
+            std::reverse_copy(edge_prop.line().begin(), edge_prop.line().end(),
+                std::back_inserter(route));
+        }
+    }
+}
+
+
+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()
+{
+    // Define a point in the Geographic coordinate system
+    typedef boost::geometry::point
+        <
+            double, 2, boost::geometry::cs::geographic<boost::geometry::degree> 
+        > point_type;
+
+    typedef boost::geometry::linestring<point_type> line_type;
+
+    // Define the graph, lateron containing the road network
+    // With this, specify bundled properties for vertex and edge,
+    // as in http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/bundles.html
+    typedef boost::adjacency_list
+        <
+            boost::vecS, boost::vecS, boost::undirectedS
+            , bg_vertex_property<point_type> // bundled
+            , bg_edge_property<line_type>
+        > graph_type;
+
+    typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_type;
+
+
+    // Init a bounding box, lateron used to define SVG map
+    boost::geometry::box_2d box;
+    boost::geometry::assign_inverse(box);
+
+    graph_type graph;
+
+    // Read the cities
+    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);
+
+    // Read the road network
+    typedef boost::tuple<line_type, std::string> road_type;
+    std::vector<road_type> roads;
+    read_wkt<line_type>("data/roads.wkt", roads, box);
+
+
+    // Add roads and connect cities
+    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);
+
+    // Main functionality: calculate shortest routes from/to all cities
+
+    // For the first one, the complete route is stored as a linestring
+    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);
+
+        // Call Dijkstra (without named-parameter to be compatible with all VC)
+        boost::dijkstra_shortest_paths(graph, city1.get<2>(),
+                &predecessors[0], &costs[0],
+                boost::get(&bg_edge_property<line_type>::length, graph),
+                boost::get(boost::vertex_index, graph),
+                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)
+        {
+            if (! boost::equals(city1.get<1>(), city2.get<1>()))
+            {
+                double distance = costs[city2.get<2>()] / km;
+                double acof = boost::geometry::distance(city1.get<0>(), city2.get<0>()) / 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;
+                }
+            }
+        }
+    }
+
+    // Create the SVG
+    std::ofstream stream("routes.svg");
+    boost::geometry::svg_mapper<point_type> mapper(stream, 600, 600);
+
+    // Map roads
+    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");
+
+    // Map cities
+    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);
+    }
+
+    return 0;
+}

Added: sandbox/geometry/libs/geometry/example/07_b_graph_route_example.vcproj
==============================================================================
--- (empty file)
+++ sandbox/geometry/libs/geometry/example/07_b_graph_route_example.vcproj	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
@@ -0,0 +1,171 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+	ProjectType="Visual C++"
+	Version="8.00"
+	Name="07_b_graph_route_example"
+	ProjectGUID="{940B049A-51AF-48DE-B366-11B42B98E3B3}"
+	RootNamespace="07_b_graph_route_example"
+	Keyword="Win32Proj"
+	>
+	<Platforms>
+		<Platform
+			Name="Win32"
+		/>
+	</Platforms>
+	<ToolFiles>
+	</ToolFiles>
+	<Configurations>
+		<Configuration
+			Name="Debug|Win32"
+			OutputDirectory="$(SolutionDir)$(ConfigurationName)"
+			IntermediateDirectory="$(ConfigurationName)\07_b_graph_route_example"
+			ConfigurationType="1"
+			InheritedPropertySheets=".\boost.vsprops"
+			CharacterSet="1"
+			>
+			<Tool
+				Name="VCPreBuildEventTool"
+			/>
+			<Tool
+				Name="VCCustomBuildTool"
+			/>
+			<Tool
+				Name="VCXMLDataGeneratorTool"
+			/>
+			<Tool
+				Name="VCWebServiceProxyGeneratorTool"
+			/>
+			<Tool
+				Name="VCMIDLTool"
+			/>
+			<Tool
+				Name="VCCLCompilerTool"
+				Optimization="0"
+				PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+				RuntimeLibrary="1"
+				DisableLanguageExtensions="false"
+				UsePrecompiledHeader="0"
+				DebugInformationFormat="1"
+			/>
+			<Tool
+				Name="VCManagedResourceCompilerTool"
+			/>
+			<Tool
+				Name="VCResourceCompilerTool"
+			/>
+			<Tool
+				Name="VCPreLinkEventTool"
+			/>
+			<Tool
+				Name="VCLinkerTool"
+				GenerateDebugInformation="true"
+				SubSystem="1"
+				TargetMachine="1"
+			/>
+			<Tool
+				Name="VCALinkTool"
+			/>
+			<Tool
+				Name="VCManifestTool"
+			/>
+			<Tool
+				Name="VCXDCMakeTool"
+			/>
+			<Tool
+				Name="VCBscMakeTool"
+			/>
+			<Tool
+				Name="VCFxCopTool"
+			/>
+			<Tool
+				Name="VCAppVerifierTool"
+			/>
+			<Tool
+				Name="VCWebDeploymentTool"
+			/>
+			<Tool
+				Name="VCPostBuildEventTool"
+			/>
+		</Configuration>
+		<Configuration
+			Name="Release|Win32"
+			OutputDirectory="$(SolutionDir)$(ConfigurationName)"
+			IntermediateDirectory="$(ConfigurationName)\07_b_graph_route_example"
+			ConfigurationType="1"
+			InheritedPropertySheets=".\boost.vsprops"
+			CharacterSet="1"
+			WholeProgramOptimization="1"
+			>
+			<Tool
+				Name="VCPreBuildEventTool"
+			/>
+			<Tool
+				Name="VCCustomBuildTool"
+			/>
+			<Tool
+				Name="VCXMLDataGeneratorTool"
+			/>
+			<Tool
+				Name="VCWebServiceProxyGeneratorTool"
+			/>
+			<Tool
+				Name="VCMIDLTool"
+			/>
+			<Tool
+				Name="VCCLCompilerTool"
+				PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+				UsePrecompiledHeader="0"
+			/>
+			<Tool
+				Name="VCManagedResourceCompilerTool"
+			/>
+			<Tool
+				Name="VCResourceCompilerTool"
+			/>
+			<Tool
+				Name="VCPreLinkEventTool"
+			/>
+			<Tool
+				Name="VCLinkerTool"
+				SubSystem="1"
+				OptimizeReferences="2"
+				EnableCOMDATFolding="2"
+				TargetMachine="1"
+			/>
+			<Tool
+				Name="VCALinkTool"
+			/>
+			<Tool
+				Name="VCManifestTool"
+			/>
+			<Tool
+				Name="VCXDCMakeTool"
+			/>
+			<Tool
+				Name="VCBscMakeTool"
+			/>
+			<Tool
+				Name="VCFxCopTool"
+			/>
+			<Tool
+				Name="VCAppVerifierTool"
+			/>
+			<Tool
+				Name="VCWebDeploymentTool"
+			/>
+			<Tool
+				Name="VCPostBuildEventTool"
+			/>
+		</Configuration>
+	</Configurations>
+	<References>
+	</References>
+	<Files>
+		<File
+			RelativePath=".\07_b_graph_route_example.cpp"
+			>
+		</File>
+	</Files>
+	<Globals>
+	</Globals>
+</VisualStudioProject>

Deleted: sandbox/geometry/libs/geometry/example/07_graph_route_example.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/example/07_graph_route_example.cpp	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
+++ (empty file)
@@ -1,384 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands
-// Copyright Bruno Lalande 2008, 2009
-// Use, modification and distribution is subject to the Boost Software License,
-// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-//
-// Example showing GGL combined with Boost.Graph, calculating shortest routes
-// input: two WKT's, provided in subfolder data
-// output: text, + an SVG, displayable in e.g. Firefox)
-
-#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>
-#include <boost/geometry/geometries/cartesian2d.hpp>
-
-
-// Yes, this example currently uses some extensions:
-
-    // For input:
-    #include <boost/geometry/extensions/gis/io/wkt/read_wkt.hpp>
-
-    // For output:
-    #include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
-
-    // For distance-calculations over the Earth:
-    #include <boost/geometry/extensions/gis/geographic/strategies/andoyer.hpp>
-
-
-
-// Read an ASCII file containing WKT's, fill a vector of tuples
-// The tuples consist of at least <0> a geometry and <1> an identifying string
-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;
-
-                // Split at ';', if any
-                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;
-                boost::geometry::read_wkt(line, geometry);
-
-                Tuple tuple(geometry, name);
-
-                tuples.push_back(tuple);
-                boost::geometry::combine(box, boost::geometry::make_envelope<Box>(geometry));
-            }
-        }
-    }
-}
-
-
-
-// Code to define properties for Boost Graph's
-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);
-}
-
-// Define properties for vertex
-template <typename Point>
-struct bg_vertex_property
-{
-    bg_vertex_property()
-    {
-        boost::geometry::assign_zero(location);
-    }
-    bg_vertex_property(Point const& loc)
-    {
-        location = loc;
-    }
-
-    Point location;
-};
-
-// Define properties for edge
-template <typename Linestring>
-struct bg_edge_property
-{
-    bg_edge_property(Linestring const& line)
-        : m_line(line)
-    {
-        m_length = boost::geometry::length(line);
-    }
-
-    inline operator double() const
-    {
-        return m_length;
-    }
-
-    inline Linestring const& line() const
-    {
-        return m_line;
-    }
-
-private :
-    double m_length;
-    Linestring m_line;
-};
-
-// Utility function to add a vertex to a graph. It might exist already. Then do not insert,
-// but return vertex descriptor back. It might not exist. Then add it (and return).
-// To efficiently handle this, a std::map is used.
-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())
-    {
-        // Add a vertex to the graph
-        typename boost::graph_traits<G>::vertex_descriptor new_vertex
-            = boost::add_vertex(graph);
-
-        // Set the property (= location)
-        boost::put(boost::get(vertex_bg_property, graph), new_vertex,
-            bg_vertex_property<typename M::key_type>(key));
-
-        // Add to the map, using POINT as 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::geometry::point_type<line_type>::type point_type;
-
-    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_type;
-
-    // Define a map to be used during graph filling
-    // Maps from point to vertex-id's
-    typedef std::map<point_type, vertex_type, boost::geometry::less<point_type> > map_type;
-    map_type map;
-
-
-    // Fill the graph
-    BOOST_FOREACH(road_type const& road, roads)
-    {
-        line_type const& line = road.template get<0>();
-        // Find or add begin/end point of these line
-        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);
-    }
-
-    // Find nearest graph vertex for each city, using the map
-    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)
-        {
-            double dist = boost::geometry::distance(it->first, city.template get<0>());
-            if (dist < min_distance)
-            {
-                min_distance = dist;
-                // Set the vertex
-                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)
-    {
-        // Get properties of edge and of vertex
-        bg_edge_property<Route> const& edge_prop =
-            boost::get(boost::get(edge_bg_property, graph), opt_edge.first);
-
-        bg_vertex_property<typename boost::geometry::point_type<Route>::type> const& vertex_prop =
-            boost::get(boost::get(vertex_bg_property, graph), vertex2);
-
-        // Depending on how edge connects to vertex, copy it forward or backward
-        if (boost::geometry::equals(edge_prop.line().front(), vertex_prop.location))
-        {
-            std::copy(edge_prop.line().begin(), edge_prop.line().end(),
-                std::back_inserter(route));
-        }
-        else
-        {
-            std::reverse_copy(edge_prop.line().begin(), edge_prop.line().end(),
-                std::back_inserter(route));
-        }
-    }
-}
-
-
-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()
-{
-    // Define a point in the Geographic coordinate system
-    typedef boost::geometry::point
-        <
-            double, 2, boost::geometry::cs::geographic<boost::geometry::degree> 
-        > point_type;
-
-    typedef boost::geometry::linestring<point_type> line_type;
-
-    // Define the graph, lateron containing the road network
-    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;
-
-
-    // Init a bounding box, lateron used to define SVG map
-    boost::geometry::box_2d box;
-    boost::geometry::assign_inverse(box);
-
-    // Read the cities
-    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);
-
-    // Read the road network
-    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
-    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);
-
-    // Main functionality: calculate shortest routes from/to all cities
-
-    // For the first one, the complete route is stored as a linestring
-    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);
-
-        // Call Dijkstra (without named-parameter to be compatible with all VC)
-        boost::dijkstra_shortest_paths(graph, city1.get<2>(),
-                &predecessors[0], &costs[0],
-                boost::get(edge_bg_property, graph),
-                boost::get(boost::vertex_index, graph),
-                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)
-        {
-            if (! boost::equals(city1.get<1>(), city2.get<1>()))
-            {
-                double distance = costs[city2.get<2>()] / km;
-                double acof = boost::geometry::distance(city1.get<0>(), city2.get<0>()) / 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;
-                }
-            }
-        }
-    }
-
-    // Create the SVG
-    std::ofstream stream("routes.svg");
-    boost::geometry::svg_mapper<point_type> mapper(stream, 600, 600);
-
-    // Map roads
-    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");
-
-    // Map cities
-    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);
-    }
-
-    return 0;
-}

Deleted: sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj
==============================================================================
--- sandbox/geometry/libs/geometry/example/07_graph_route_example.vcproj	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
+++ (empty file)
@@ -1,171 +0,0 @@
-<?xml version="1.0" encoding="Windows-1252"?>
-<VisualStudioProject
-	ProjectType="Visual C++"
-	Version="8.00"
-	Name="07_graph_route_example"
-	ProjectGUID="{47D30DD8-CBB1-4527-811F-F0193E22B317}"
-	RootNamespace="07_graph_route_example"
-	Keyword="Win32Proj"
-	>
-	<Platforms>
-		<Platform
-			Name="Win32"
-		/>
-	</Platforms>
-	<ToolFiles>
-	</ToolFiles>
-	<Configurations>
-		<Configuration
-			Name="Debug|Win32"
-			OutputDirectory="$(SolutionDir)$(ConfigurationName)"
-			IntermediateDirectory="$(ConfigurationName)\07_graph_route_example"
-			ConfigurationType="1"
-			InheritedPropertySheets=".\boost.vsprops"
-			CharacterSet="1"
-			>
-			<Tool
-				Name="VCPreBuildEventTool"
-			/>
-			<Tool
-				Name="VCCustomBuildTool"
-			/>
-			<Tool
-				Name="VCXMLDataGeneratorTool"
-			/>
-			<Tool
-				Name="VCWebServiceProxyGeneratorTool"
-			/>
-			<Tool
-				Name="VCMIDLTool"
-			/>
-			<Tool
-				Name="VCCLCompilerTool"
-				Optimization="0"
-				PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
-				RuntimeLibrary="1"
-				DisableLanguageExtensions="false"
-				UsePrecompiledHeader="0"
-				DebugInformationFormat="1"
-			/>
-			<Tool
-				Name="VCManagedResourceCompilerTool"
-			/>
-			<Tool
-				Name="VCResourceCompilerTool"
-			/>
-			<Tool
-				Name="VCPreLinkEventTool"
-			/>
-			<Tool
-				Name="VCLinkerTool"
-				GenerateDebugInformation="true"
-				SubSystem="1"
-				TargetMachine="1"
-			/>
-			<Tool
-				Name="VCALinkTool"
-			/>
-			<Tool
-				Name="VCManifestTool"
-			/>
-			<Tool
-				Name="VCXDCMakeTool"
-			/>
-			<Tool
-				Name="VCBscMakeTool"
-			/>
-			<Tool
-				Name="VCFxCopTool"
-			/>
-			<Tool
-				Name="VCAppVerifierTool"
-			/>
-			<Tool
-				Name="VCWebDeploymentTool"
-			/>
-			<Tool
-				Name="VCPostBuildEventTool"
-			/>
-		</Configuration>
-		<Configuration
-			Name="Release|Win32"
-			OutputDirectory="$(SolutionDir)$(ConfigurationName)"
-			IntermediateDirectory="$(ConfigurationName)\07_graph_route_example"
-			ConfigurationType="1"
-			InheritedPropertySheets=".\boost.vsprops"
-			CharacterSet="1"
-			WholeProgramOptimization="1"
-			>
-			<Tool
-				Name="VCPreBuildEventTool"
-			/>
-			<Tool
-				Name="VCCustomBuildTool"
-			/>
-			<Tool
-				Name="VCXMLDataGeneratorTool"
-			/>
-			<Tool
-				Name="VCWebServiceProxyGeneratorTool"
-			/>
-			<Tool
-				Name="VCMIDLTool"
-			/>
-			<Tool
-				Name="VCCLCompilerTool"
-				PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
-				UsePrecompiledHeader="0"
-			/>
-			<Tool
-				Name="VCManagedResourceCompilerTool"
-			/>
-			<Tool
-				Name="VCResourceCompilerTool"
-			/>
-			<Tool
-				Name="VCPreLinkEventTool"
-			/>
-			<Tool
-				Name="VCLinkerTool"
-				SubSystem="1"
-				OptimizeReferences="2"
-				EnableCOMDATFolding="2"
-				TargetMachine="1"
-			/>
-			<Tool
-				Name="VCALinkTool"
-			/>
-			<Tool
-				Name="VCManifestTool"
-			/>
-			<Tool
-				Name="VCXDCMakeTool"
-			/>
-			<Tool
-				Name="VCBscMakeTool"
-			/>
-			<Tool
-				Name="VCFxCopTool"
-			/>
-			<Tool
-				Name="VCAppVerifierTool"
-			/>
-			<Tool
-				Name="VCWebDeploymentTool"
-			/>
-			<Tool
-				Name="VCPostBuildEventTool"
-			/>
-		</Configuration>
-	</Configurations>
-	<References>
-	</References>
-	<Files>
-		<File
-			RelativePath=".\07_graph_route_example.cpp"
-			>
-		</File>
-	</Files>
-	<Globals>
-	</Globals>
-</VisualStudioProject>

Modified: sandbox/geometry/libs/geometry/example/Jamfile.v2
==============================================================================
--- sandbox/geometry/libs/geometry/example/Jamfile.v2	(original)
+++ sandbox/geometry/libs/geometry/example/Jamfile.v2	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
@@ -18,7 +18,8 @@
 exe 05_b_overlay_linestring_polygon_example : 05_b_overlay_linestring_polygon_example.cpp ;
 exe 06_a_transformation_example : 06_a_transformation_example.cpp ;
 exe 06_b_transformation_example : 06_b_transformation_example.cpp ;
-exe 07_graph_route_example : 07_graph_route_example.cpp ;
+exe 07_a_graph_route_example : 07_a_graph_route_example.cpp ;
+exe 07_b_graph_route_example : 07_b_graph_route_example.cpp ;
 
 exe c01_custom_point_example : c01_custom_point_example.cpp ;
 exe c02_custom_box_example : c02_custom_box_example.cpp ;

Modified: sandbox/geometry/libs/geometry/example/basic_examples.sln
==============================================================================
--- sandbox/geometry/libs/geometry/example/basic_examples.sln	(original)
+++ sandbox/geometry/libs/geometry/example/basic_examples.sln	2010-06-26 06:09:00 EDT (Sat, 26 Jun 2010)
@@ -8,14 +8,16 @@
 EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "06_a_transformation_example", "06_a_transformation_example.vcproj", "{34346EC5-1EE8-49D5-AF24-D915B4D7D144}"
 EndProject
-Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "07_graph_route_example", "07_graph_route_example.vcproj", "{47D30DD8-CBB1-4527-811F-F0193E22B317}"
-EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "06_b_transformation_example", "06_b_transformation_example.vcproj", "{34346EC5-1EE8-49D5-AC21-D915B4D7D144}"
 EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "05_a_overlay_polygon_example", "05_a_overlay_polygon_example.vcproj", "{119F9CCD-4B5F-4623-B4C1-F65E6323B24F}"
 EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "05_b_overlay_linestring_polygon_example", "05_b_overlay_linestring_polygon_example.vcproj", "{3A803CEA-0902-4355-886A-799C596D0B46}"
 EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "07_a_graph_route_example", "07_a_graph_route_example.vcproj", "{47D30DD8-CBB1-4527-811F-F0193E22B317}"
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "07_b_graph_route_example", "07_b_graph_route_example.vcproj", "{940B049A-51AF-48DE-B366-11B42B98E3B3}"
+EndProject
 Global
         GlobalSection(SolutionConfigurationPlatforms) = preSolution
                 Debug|Win32 = Debug|Win32
@@ -38,10 +40,6 @@
                 {34346EC5-1EE8-49D5-AF24-D915B4D7D144}.Debug|Win32.Build.0 = Debug|Win32
                 {34346EC5-1EE8-49D5-AF24-D915B4D7D144}.Release|Win32.ActiveCfg = Release|Win32
                 {34346EC5-1EE8-49D5-AF24-D915B4D7D144}.Release|Win32.Build.0 = Release|Win32
-		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Debug|Win32.ActiveCfg = Debug|Win32
-		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Debug|Win32.Build.0 = Debug|Win32
-		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Release|Win32.ActiveCfg = Release|Win32
-		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Release|Win32.Build.0 = Release|Win32
                 {34346EC5-1EE8-49D5-AC21-D915B4D7D144}.Debug|Win32.ActiveCfg = Debug|Win32
                 {34346EC5-1EE8-49D5-AC21-D915B4D7D144}.Debug|Win32.Build.0 = Debug|Win32
                 {34346EC5-1EE8-49D5-AC21-D915B4D7D144}.Release|Win32.ActiveCfg = Release|Win32
@@ -54,6 +52,14 @@
                 {3A803CEA-0902-4355-886A-799C596D0B46}.Debug|Win32.Build.0 = Debug|Win32
                 {3A803CEA-0902-4355-886A-799C596D0B46}.Release|Win32.ActiveCfg = Release|Win32
                 {3A803CEA-0902-4355-886A-799C596D0B46}.Release|Win32.Build.0 = Release|Win32
+		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Debug|Win32.ActiveCfg = Debug|Win32
+		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Debug|Win32.Build.0 = Debug|Win32
+		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Release|Win32.ActiveCfg = Release|Win32
+		{47D30DD8-CBB1-4527-811F-F0193E22B317}.Release|Win32.Build.0 = Release|Win32
+		{940B049A-51AF-48DE-B366-11B42B98E3B3}.Debug|Win32.ActiveCfg = Debug|Win32
+		{940B049A-51AF-48DE-B366-11B42B98E3B3}.Debug|Win32.Build.0 = Debug|Win32
+		{940B049A-51AF-48DE-B366-11B42B98E3B3}.Release|Win32.ActiveCfg = Release|Win32
+		{940B049A-51AF-48DE-B366-11B42B98E3B3}.Release|Win32.Build.0 = Release|Win32
         EndGlobalSection
         GlobalSection(SolutionProperties) = preSolution
                 HideSolutionNode = FALSE