[Boost-commit] svn:boost r80957 - trunk/libs/graph/test

Subject: [Boost-commit] svn:boost r80957 - trunk/libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-10-11 12:45:34

Author: jewillco
Date: 2012-10-11 12:45:33 EDT (Thu, 11 Oct 2012)
New Revision: 80957
URL: http://svn.boost.org/trac/boost/changeset/80957

Log:
Added test from Juergen Hunold
Added:
   trunk/libs/graph/test/filtered_graph_properties_dijkstra.cpp   (contents, props changed)
Text files modified: 
   trunk/libs/graph/test/Jamfile.v2 |     1 +                                       
   1 files changed, 1 insertions(+), 0 deletions(-)

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2012-10-11 12:45:33 EDT (Thu, 11 Oct 2012)
@@ -124,6 +124,7 @@
     [ run random_spanning_tree_test.cpp ../build//boost_graph ]
     [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
     [ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
+    [ compile filtered_graph_properties_dijkstra.cpp ]
     ;
 
 # Run SDB tests only when -sSDB= is set.

Added: trunk/libs/graph/test/filtered_graph_properties_dijkstra.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/filtered_graph_properties_dijkstra.cpp	2012-10-11 12:45:33 EDT (Thu, 11 Oct 2012)
@@ -0,0 +1,111 @@
+// (c) Copyright Juergen Hunold 2012
+// 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)
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/filtered_graph.hpp>
+
+namespace boost {
+
+    enum edge_info_t { edge_info = 114 };
+
+    BOOST_INSTALL_PROPERTY( edge, info );
+}
+
+template< typename EdgeInfo,
+          typename Directed >
+class Graph
+{
+public:
+    typedef boost::property< boost::edge_info_t, EdgeInfo > tEdge_property;
+
+    typedef boost::adjacency_list< boost::setS,
+                                   boost::vecS,
+                                   Directed,
+                                   boost::no_property,
+                                   tEdge_property > tGraph;
+
+    typedef typename boost::graph_traits< tGraph >::vertex_descriptor tNode;
+    typedef typename boost::graph_traits< tGraph >::edge_descriptor   tEdge;
+
+protected:
+
+    tGraph          m_Graph;
+};
+
+class DataEdge;
+
+class UndirectedGraph
+    : public Graph< DataEdge*,
+                    boost::undirectedS >
+{
+public:
+
+    template< class Evaluator, class Filter >
+    void        dijkstra( Evaluator const&,
+                          Filter const& ) const;
+};
+
+template< typename Graph, typename Derived >
+struct Evaluator : public boost::put_get_helper< int, Derived >
+{
+    typedef int value_type;
+    typedef typename Graph::tEdge key_type;
+    typedef int reference;
+    typedef boost::readable_property_map_tag category;
+
+    explicit Evaluator( Graph const* pGraph );
+};
+
+
+template< typename Graph >
+struct LengthEvaluator : public Evaluator< Graph, LengthEvaluator<Graph> >
+{
+    explicit LengthEvaluator( Graph const* pGraph );
+
+    typedef typename Evaluator<Graph, LengthEvaluator<Graph> >::reference reference;
+    typedef typename Evaluator<Graph, LengthEvaluator<Graph> >::key_type key_type;
+
+    virtual reference operator[] ( key_type const& edge ) const;
+};
+
+template< class Graph >
+struct EdgeFilter
+{
+    typedef typename Graph::tEdge key_type;
+
+    EdgeFilter();
+
+    explicit EdgeFilter( Graph const*);
+
+    bool    operator()( key_type const& ) const;
+
+private:
+    const Graph*    m_pGraph;
+};
+
+
+template< class Evaluator, class Filter >
+void
+UndirectedGraph::dijkstra( Evaluator const& rEvaluator,
+                           Filter const& rFilter ) const
+{
+    tNode nodeSource = vertex(0, m_Graph);
+
+    std::vector< tNode > predecessors( num_vertices(m_Graph) );
+
+    boost::filtered_graph< tGraph, Filter > filteredGraph( m_Graph, rFilter );
+
+    boost::dijkstra_shortest_paths( filteredGraph,
+                                    nodeSource,
+                                    boost::predecessor_map( &predecessors[0] )
+                                    .weight_map( rEvaluator ) );
+}
+
+// explicit instantiation
+template void UndirectedGraph::dijkstra( LengthEvaluator<UndirectedGraph> const&,
+                                         EdgeFilter<UndirectedGraph> const& ) const;
+
+int main(int, char**) {return 0;} // Tests above will fail to compile if anything is broken