LEMON/LEMON-official Changeset - r947:abb95d48e89e

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r947:abb95d48e89e

« 946:5df6a8

948:9f6ed8 »

r947:abb95d48e89e

Fri, 16 Oct 2009 09:35:46

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Add traits class + named parameters to Suurballe (#323) The following types can be modified using named parameters: - FlowMap - PotentialMap - Path - Heap + HeapCrossRef

0 2 0

default

2 files changed with 146 insertions and 21 deletions:

lemon/suurballe.h

138

test/suurballe_test.cc

↑ Collapse diff ↑

lemon/suurballe.h

Show inline comments

@@ -21,99 +21,140 @@
 		///\ingroup shortest_path
 		///\file
 		///\brief An algorithm for finding arc-disjoint paths between two
 		/// nodes having minimum total length.
 		#include <vector>
 		#include <limits>
 		#include <lemon/bin_heap.h>
 		#include <lemon/path.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \brief Default traits class of Suurballe algorithm.
 		  ///
 		  /// Default traits class of Suurballe algorithm.
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam LEN The type of the length map.
 		  /// The default value is <tt>GR::ArcMap<int></tt>.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int> >
 		#endif
 		  struct SuurballeDefaultTraits
+		  {
 		    /// The type of the digraph.
 		    typedef GR Digraph;
 		    /// The type of the length map.
 		    typedef LEN LengthMap;
 		    /// The type of the lengths.
 		    typedef typename LEN::Value Length;
 		    /// The type of the flow map.
 		    typedef typename GR::template ArcMap<int> FlowMap;
 		    /// The type of the potential map.
 		    typedef typename GR::template NodeMap<Length> PotentialMap;
 		    /// \brief The path type
 		    ///
 		    /// The type used for storing the found arc-disjoint paths.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		    /// The cross reference type used for the heap.
 		    typedef typename GR::template NodeMap<int> HeapCrossRef;
 		    /// \brief The heap type used for internal Dijkstra computations.
 		    ///
 		    /// The type of the heap used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
 		    /// and its priority type must be \c Length.
 		    typedef BinHeap<Length, HeapCrossRef> Heap;
 		  };
 		  /// \addtogroup shortest_path
 		  /// @{
 		  /// \brief Algorithm for finding arc-disjoint paths between two nodes
 		  /// having minimum total length.
 		  ///
 		  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
 		  /// finding arc-disjoint paths having minimum total length (cost)
 		  /// from a given source node to a given target node in a digraph.
 		  ///
 		  /// Note that this problem is a special case of the \ref min_cost_flow
 		  /// "minimum cost flow problem". This implementation is actually an
 		  /// efficient specialized version of the \ref CapacityScaling
 		  /// "successive shortest path" algorithm directly for this problem.
 		  /// Therefore this class provides query functions for flow values and
 		  /// node potentials (the dual solution) just like the minimum cost flow
 		  /// algorithms.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam LEN The type of the length map.
 		  /// The default value is <tt>GR::ArcMap<int></tt>.
 		  ///
 		  /// \warning Length values should be \e non-negative.
 		  ///
 		  /// \note For finding \e node-disjoint paths, this algorithm can be used
 		  /// along with the \ref SplitNodes adaptor.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
+		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
-		             typename LEN = typename GR::template ArcMap<int> >
+		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = SuurballeDefaultTraits<GR, LEN> >
 		#endif
 		  class Suurballe
+		  {
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef ConstMap<Arc, int> ConstArcMap;
 		    typedef typename GR::template NodeMap<Arc> PredMap;
 		  public:
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// The type of the digraph.
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map.
-		    typedef LEN LengthMap;
+		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the lengths.
 		    typedef typename LengthMap::Value Length;
 		#ifdef DOXYGEN
 		    typedef typename TR::Length Length;
 		    /// The type of the flow map.
-		    typedef GR::ArcMap<int> FlowMap;
+		    typedef typename TR::FlowMap FlowMap;
 		    /// The type of the potential map.
 		    typedef GR::NodeMap<Length> PotentialMap;
 		#else
 		    /// The type of the flow map.
 		    typedef typename Digraph::template ArcMap<int> FlowMap;
 		    /// The type of the potential map.
 		    typedef typename Digraph::template NodeMap<Length> PotentialMap;
-		#endif
+		    typedef typename TR::PotentialMap PotentialMap;
 		    /// The type of the path structures.
 		    typedef typename TR::Path Path;
 		    /// The cross reference type used for the heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    /// The heap type used for internal Dijkstra computations.
 		    typedef typename TR::Heap Heap;
 		    /// The type of the path structures.
 		    typedef SimplePath<GR> Path;
 		    /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    typedef BinHeap<Length, HeapCrossRef> Heap;
 		    // ResidualDijkstra is a special implementation of the
 		    // Dijkstra algorithm for finding shortest paths in the
 		    // residual network with respect to the reduced arc lengths
 		    // and modifying the node potentials according to the
 		    // distance of the nodes.
 		    class ResidualDijkstra
+		    {
 		    private:
 		      const Digraph &_graph;
 		      const LengthMap &_length;
 		      const FlowMap &_flow;
 		      PotentialMap &_pi;
 		      PredMap &_pred;
 		      Node _s;
 		      Node _t;
@@ -241,32 +282,109 @@
 		                  break;
+		              }
+		            }
+		          }
+		        }
 		        if (heap.empty()) return false;
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		    }; //class ResidualDijkstra
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c FlowMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c FlowMap type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPotentialMapTraits : public Traits {
 		      typedef T PotentialMap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c PotentialMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PotentialMap type.
 		    template <typename T>
 		    struct SetPotentialMap
 		      : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c %Path type.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    template <typename T>
 		    struct SetPath
 		      : public Suurballe<GR, LEN, SetPathTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
 		    };
 		    template <typename H, typename CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef H Heap;
 		      typedef CR HeapCrossRef;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c Heap and \c HeapCrossRef types.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c Heap
 		    /// and \c HeapCrossRef types with automatic allocation.
 		    /// They will be used for internal Dijkstra computations.
 		    /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
 		    /// concept and its priority type must be \c Length.
 		    template <typename H,
 		              typename CR = typename Digraph::template NodeMap<int> >
 		    struct SetHeap
 		      : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
 		      typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
 		    };
 		    /// @}
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_graph;
 		    // The length map
 		    const LengthMap &_length;
 		    // Arc map of the current flow
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    // Node map of the current potentials
 		    PotentialMap *_potential;
 		    bool _local_potential;
 		    // The source node
 		    Node _s;

test/suurballe_test.cc

Show inline comments

@@ -10,32 +10,33 @@
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/path.h>
 		#include <lemon/suurballe.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/heap.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
@@ -68,33 +69,39 @@
 		  "12 11  30\n"
 		  "@attributes\n"
 		  "source  1\n"
 		  "target 12\n"
 		  "@end\n";
 		// Check the interface of Suurballe
 		void checkSuurballeCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  typedef concepts::ReadMap<Arc, VType> LengthMap;
-		  typedef Suurballe<Digraph, LengthMap> SuurballeType;
+		  typedef Suurballe<Digraph, LengthMap> ST;
 		  typedef Suurballe<Digraph, LengthMap>
 		    ::SetFlowMap<ST::FlowMap>
 		    ::SetPotentialMap<ST::PotentialMap>
 		    ::SetPath<SimplePath<Digraph> >
 		    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
 		    ::Create SuurballeType;
 		  Digraph g;
 		  Node n;
 		  Arc e;
 		  LengthMap len;
 		  SuurballeType::FlowMap flow(g);
 		  SuurballeType::PotentialMap pi(g);
 		  SuurballeType suurb_test(g, len);
 		  const SuurballeType& const_suurb_test = suurb_test;
 		  suurb_test
 		    .flowMap(flow)
 		    .potentialMap(pi);
 		  int k;

0 comments (0 inline)

RhodeCode

Login to your account