1.1 --- a/lemon/bfs.h Mon Feb 23 15:03:55 2009 +0000
1.2 +++ b/lemon/bfs.h Mon Feb 23 15:04:10 2009 +0000
1.3 @@ -49,11 +49,11 @@
1.4 ///arcs of the shortest paths.
1.5 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.6 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.7 - ///Instantiates a PredMap.
1.8 + ///Instantiates a \c PredMap.
1.9
1.10 - ///This function instantiates a PredMap.
1.11 + ///This function instantiates a \ref PredMap.
1.12 ///\param g is the digraph, to which we would like to define the
1.13 - ///PredMap.
1.14 + ///\ref PredMap.
1.15 static PredMap *createPredMap(const Digraph &g)
1.16 {
1.17 return new PredMap(g);
1.18 @@ -64,11 +64,11 @@
1.19 ///The type of the map that indicates which nodes are processed.
1.20 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.21 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.22 - ///Instantiates a ProcessedMap.
1.23 + ///Instantiates a \c ProcessedMap.
1.24
1.25 - ///This function instantiates a ProcessedMap.
1.26 + ///This function instantiates a \ref ProcessedMap.
1.27 ///\param g is the digraph, to which
1.28 - ///we would like to define the ProcessedMap
1.29 + ///we would like to define the \ref ProcessedMap
1.30 #ifdef DOXYGEN
1.31 static ProcessedMap *createProcessedMap(const Digraph &g)
1.32 #else
1.33 @@ -83,11 +83,11 @@
1.34 ///The type of the map that indicates which nodes are reached.
1.35 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.36 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.37 - ///Instantiates a ReachedMap.
1.38 + ///Instantiates a \c ReachedMap.
1.39
1.40 - ///This function instantiates a ReachedMap.
1.41 + ///This function instantiates a \ref ReachedMap.
1.42 ///\param g is the digraph, to which
1.43 - ///we would like to define the ReachedMap.
1.44 + ///we would like to define the \ref ReachedMap.
1.45 static ReachedMap *createReachedMap(const Digraph &g)
1.46 {
1.47 return new ReachedMap(g);
1.48 @@ -98,11 +98,11 @@
1.49 ///The type of the map that stores the distances of the nodes.
1.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.51 typedef typename Digraph::template NodeMap<int> DistMap;
1.52 - ///Instantiates a DistMap.
1.53 + ///Instantiates a \c DistMap.
1.54
1.55 - ///This function instantiates a DistMap.
1.56 + ///This function instantiates a \ref DistMap.
1.57 ///\param g is the digraph, to which we would like to define the
1.58 - ///DistMap.
1.59 + ///\ref DistMap.
1.60 static DistMap *createDistMap(const Digraph &g)
1.61 {
1.62 return new DistMap(g);
1.63 @@ -221,10 +221,10 @@
1.64 }
1.65 };
1.66 ///\brief \ref named-templ-param "Named parameter" for setting
1.67 - ///PredMap type.
1.68 + ///\c PredMap type.
1.69 ///
1.70 ///\ref named-templ-param "Named parameter" for setting
1.71 - ///PredMap type.
1.72 + ///\c PredMap type.
1.73 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.74 template <class T>
1.75 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.76 @@ -241,10 +241,10 @@
1.77 }
1.78 };
1.79 ///\brief \ref named-templ-param "Named parameter" for setting
1.80 - ///DistMap type.
1.81 + ///\c DistMap type.
1.82 ///
1.83 ///\ref named-templ-param "Named parameter" for setting
1.84 - ///DistMap type.
1.85 + ///\c DistMap type.
1.86 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.87 template <class T>
1.88 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.89 @@ -261,10 +261,10 @@
1.90 }
1.91 };
1.92 ///\brief \ref named-templ-param "Named parameter" for setting
1.93 - ///ReachedMap type.
1.94 + ///\c ReachedMap type.
1.95 ///
1.96 ///\ref named-templ-param "Named parameter" for setting
1.97 - ///ReachedMap type.
1.98 + ///\c ReachedMap type.
1.99 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.100 template <class T>
1.101 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.102 @@ -281,10 +281,10 @@
1.103 }
1.104 };
1.105 ///\brief \ref named-templ-param "Named parameter" for setting
1.106 - ///ProcessedMap type.
1.107 + ///\c ProcessedMap type.
1.108 ///
1.109 ///\ref named-templ-param "Named parameter" for setting
1.110 - ///ProcessedMap type.
1.111 + ///\c ProcessedMap type.
1.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 template <class T>
1.114 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.115 @@ -300,10 +300,10 @@
1.116 }
1.117 };
1.118 ///\brief \ref named-templ-param "Named parameter" for setting
1.119 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.120 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.121 ///
1.122 ///\ref named-templ-param "Named parameter" for setting
1.123 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.124 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.125 ///If you don't set it explicitly, it will be automatically allocated.
1.126 struct SetStandardProcessedMap :
1.127 public Bfs< Digraph, SetStandardProcessedMapTraits > {
1.128 @@ -1194,9 +1194,9 @@
1.129 ///
1.130 /// This class defines the interface of the BfsVisit events, and
1.131 /// it could be the base of a real visitor class.
1.132 - template <typename _Digraph>
1.133 + template <typename GR>
1.134 struct BfsVisitor {
1.135 - typedef _Digraph Digraph;
1.136 + typedef GR Digraph;
1.137 typedef typename Digraph::Arc Arc;
1.138 typedef typename Digraph::Node Node;
1.139 /// \brief Called for the source node(s) of the BFS.
1.140 @@ -1224,9 +1224,9 @@
1.141 void examine(const Arc& arc) {}
1.142 };
1.143 #else
1.144 - template <typename _Digraph>
1.145 + template <typename GR>
1.146 struct BfsVisitor {
1.147 - typedef _Digraph Digraph;
1.148 + typedef GR Digraph;
1.149 typedef typename Digraph::Arc Arc;
1.150 typedef typename Digraph::Node Node;
1.151 void start(const Node&) {}
1.152 @@ -1254,12 +1254,12 @@
1.153 /// \brief Default traits class of BfsVisit class.
1.154 ///
1.155 /// Default traits class of BfsVisit class.
1.156 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.157 - template<class _Digraph>
1.158 + /// \tparam GR The type of the digraph the algorithm runs on.
1.159 + template<class GR>
1.160 struct BfsVisitDefaultTraits {
1.161
1.162 /// \brief The type of the digraph the algorithm runs on.
1.163 - typedef _Digraph Digraph;
1.164 + typedef GR Digraph;
1.165
1.166 /// \brief The type of the map that indicates which nodes are reached.
1.167 ///
1.168 @@ -1280,12 +1280,12 @@
1.169
1.170 /// \ingroup search
1.171 ///
1.172 - /// \brief %BFS algorithm class with visitor interface.
1.173 + /// \brief BFS algorithm class with visitor interface.
1.174 ///
1.175 - /// This class provides an efficient implementation of the %BFS algorithm
1.176 + /// This class provides an efficient implementation of the BFS algorithm
1.177 /// with visitor interface.
1.178 ///
1.179 - /// The %BfsVisit class provides an alternative interface to the Bfs
1.180 + /// The BfsVisit class provides an alternative interface to the Bfs
1.181 /// class. It works with callback mechanism, the BfsVisit object calls
1.182 /// the member functions of the \c Visitor class on every BFS event.
1.183 ///
1.184 @@ -1294,37 +1294,37 @@
1.185 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1.186 /// instead.
1.187 ///
1.188 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.189 - /// The default value is
1.190 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.191 - /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1.192 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.193 - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1.194 + /// \tparam GR The type of the digraph the algorithm runs on.
1.195 + /// The default type is \ref ListDigraph.
1.196 + /// The value of GR is not used directly by \ref BfsVisit,
1.197 + /// it is only passed to \ref BfsVisitDefaultTraits.
1.198 + /// \tparam VS The Visitor type that is used by the algorithm.
1.199 + /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1.200 /// does not observe the BFS events. If you want to observe the BFS
1.201 /// events, you should implement your own visitor class.
1.202 - /// \tparam _Traits Traits class to set various data types used by the
1.203 + /// \tparam TR Traits class to set various data types used by the
1.204 /// algorithm. The default traits class is
1.205 - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.206 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
1.207 /// See \ref BfsVisitDefaultTraits for the documentation of
1.208 /// a BFS visit traits class.
1.209 #ifdef DOXYGEN
1.210 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.211 + template <typename GR, typename VS, typename TR>
1.212 #else
1.213 - template <typename _Digraph = ListDigraph,
1.214 - typename _Visitor = BfsVisitor<_Digraph>,
1.215 - typename _Traits = BfsVisitDefaultTraits<_Digraph> >
1.216 + template <typename GR = ListDigraph,
1.217 + typename VS = BfsVisitor<GR>,
1.218 + typename TR = BfsVisitDefaultTraits<GR> >
1.219 #endif
1.220 class BfsVisit {
1.221 public:
1.222
1.223 ///The traits class.
1.224 - typedef _Traits Traits;
1.225 + typedef TR Traits;
1.226
1.227 ///The type of the digraph the algorithm runs on.
1.228 typedef typename Traits::Digraph Digraph;
1.229
1.230 ///The visitor type used by the algorithm.
1.231 - typedef _Visitor Visitor;
1.232 + typedef VS Visitor;
1.233
1.234 ///The type of the map that indicates which nodes are reached.
1.235 typedef typename Traits::ReachedMap ReachedMap;
2.1 --- a/lemon/bits/array_map.h Mon Feb 23 15:03:55 2009 +0000
2.2 +++ b/lemon/bits/array_map.h Mon Feb 23 15:04:10 2009 +0000
2.3 @@ -135,7 +135,7 @@
2.4
2.5 // \brief Template assign operator.
2.6 //
2.7 - // The given parameter should be conform to the ReadMap
2.8 + // The given parameter should conform to the ReadMap
2.9 // concecpt and could be indiced by the current item set of
2.10 // the NodeMap. In this case the value for each item
2.11 // is assigned by the value of the given ReadMap.
3.1 --- a/lemon/bits/vector_map.h Mon Feb 23 15:03:55 2009 +0000
3.2 +++ b/lemon/bits/vector_map.h Mon Feb 23 15:04:10 2009 +0000
3.3 @@ -124,7 +124,7 @@
3.4
3.5 // \brief Template assign operator.
3.6 //
3.7 - // The given parameter should be conform to the ReadMap
3.8 + // The given parameter should conform to the ReadMap
3.9 // concecpt and could be indiced by the current item set of
3.10 // the NodeMap. In this case the value for each item
3.11 // is assigned by the value of the given ReadMap.
4.1 --- a/lemon/circulation.h Mon Feb 23 15:03:55 2009 +0000
4.2 +++ b/lemon/circulation.h Mon Feb 23 15:04:10 2009 +0000
4.3 @@ -31,30 +31,30 @@
4.4 /// \brief Default traits class of Circulation class.
4.5 ///
4.6 /// Default traits class of Circulation class.
4.7 - /// \tparam _Diraph Digraph type.
4.8 - /// \tparam _LCapMap Lower bound capacity map type.
4.9 - /// \tparam _UCapMap Upper bound capacity map type.
4.10 - /// \tparam _DeltaMap Delta map type.
4.11 - template <typename _Diraph, typename _LCapMap,
4.12 - typename _UCapMap, typename _DeltaMap>
4.13 + /// \tparam GR Digraph type.
4.14 + /// \tparam LM Lower bound capacity map type.
4.15 + /// \tparam UM Upper bound capacity map type.
4.16 + /// \tparam DM Delta map type.
4.17 + template <typename GR, typename LM,
4.18 + typename UM, typename DM>
4.19 struct CirculationDefaultTraits {
4.20
4.21 /// \brief The type of the digraph the algorithm runs on.
4.22 - typedef _Diraph Digraph;
4.23 + typedef GR Digraph;
4.24
4.25 /// \brief The type of the map that stores the circulation lower
4.26 /// bound.
4.27 ///
4.28 /// The type of the map that stores the circulation lower bound.
4.29 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
4.30 - typedef _LCapMap LCapMap;
4.31 + typedef LM LCapMap;
4.32
4.33 /// \brief The type of the map that stores the circulation upper
4.34 /// bound.
4.35 ///
4.36 /// The type of the map that stores the circulation upper bound.
4.37 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
4.38 - typedef _UCapMap UCapMap;
4.39 + typedef UM UCapMap;
4.40
4.41 /// \brief The type of the map that stores the lower bound for
4.42 /// the supply of the nodes.
4.43 @@ -62,7 +62,7 @@
4.44 /// The type of the map that stores the lower bound for the supply
4.45 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
4.46 /// concept.
4.47 - typedef _DeltaMap DeltaMap;
4.48 + typedef DM DeltaMap;
4.49
4.50 /// \brief The type of the flow values.
4.51 typedef typename DeltaMap::Value Value;
4.52 @@ -137,35 +137,33 @@
4.53 \ref min_cost_flow "minimum cost flow" problem can be calculated
4.54 in this way.
4.55
4.56 - \tparam _Digraph The type of the digraph the algorithm runs on.
4.57 - \tparam _LCapMap The type of the lower bound capacity map. The default
4.58 - map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
4.59 - \tparam _UCapMap The type of the upper bound capacity map. The default
4.60 - map type is \c _LCapMap.
4.61 - \tparam _DeltaMap The type of the map that stores the lower bound
4.62 + \tparam GR The type of the digraph the algorithm runs on.
4.63 + \tparam LM The type of the lower bound capacity map. The default
4.64 + map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
4.65 + \tparam UM The type of the upper bound capacity map. The default
4.66 + map type is \c LM.
4.67 + \tparam DM The type of the map that stores the lower bound
4.68 for the supply of the nodes. The default map type is
4.69 - \c _Digraph::ArcMap<_UCapMap::Value>.
4.70 + \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
4.71 */
4.72 #ifdef DOXYGEN
4.73 -template< typename _Digraph,
4.74 - typename _LCapMap,
4.75 - typename _UCapMap,
4.76 - typename _DeltaMap,
4.77 - typename _Traits >
4.78 +template< typename GR,
4.79 + typename LM,
4.80 + typename UM,
4.81 + typename DM,
4.82 + typename TR >
4.83 #else
4.84 -template< typename _Digraph,
4.85 - typename _LCapMap = typename _Digraph::template ArcMap<int>,
4.86 - typename _UCapMap = _LCapMap,
4.87 - typename _DeltaMap = typename _Digraph::
4.88 - template NodeMap<typename _UCapMap::Value>,
4.89 - typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
4.90 - _UCapMap, _DeltaMap> >
4.91 +template< typename GR,
4.92 + typename LM = typename GR::template ArcMap<int>,
4.93 + typename UM = LM,
4.94 + typename DM = typename GR::template NodeMap<typename UM::Value>,
4.95 + typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
4.96 #endif
4.97 class Circulation {
4.98 public:
4.99
4.100 ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
4.101 - typedef _Traits Traits;
4.102 + typedef TR Traits;
4.103 ///The type of the digraph the algorithm runs on.
4.104 typedef typename Traits::Digraph Digraph;
4.105 ///The type of the flow values.
5.1 --- a/lemon/concepts/graph_components.h Mon Feb 23 15:03:55 2009 +0000
5.2 +++ b/lemon/concepts/graph_components.h Mon Feb 23 15:04:10 2009 +0000
5.3 @@ -114,7 +114,7 @@
5.4 /// \brief An empty base directed graph class.
5.5 ///
5.6 /// This class provides the minimal set of features needed for a
5.7 - /// directed graph structure. All digraph concepts have to be
5.8 + /// directed graph structure. All digraph concepts have to
5.9 /// conform to this base directed graph. It just provides types
5.10 /// for nodes and arcs and functions to get the source and the
5.11 /// target of the arcs.
5.12 @@ -179,7 +179,7 @@
5.13 ///
5.14 /// This class provides the minimal set of features needed for an
5.15 /// undirected graph structure. All undirected graph concepts have
5.16 - /// to be conform to this base graph. It just provides types for
5.17 + /// to conform to this base graph. It just provides types for
5.18 /// nodes, arcs and edges and functions to get the
5.19 /// source and the target of the arcs and edges,
5.20 /// conversion from arcs to edges and function to get
5.21 @@ -294,7 +294,7 @@
5.22 ///
5.23 /// This class provides beside the core digraph features
5.24 /// core id functions for the digraph structure.
5.25 - /// The most of the base digraphs should be conform to this concept.
5.26 + /// The most of the base digraphs should conform to this concept.
5.27 /// The id's are unique and immutable.
5.28 template <typename _Base = BaseDigraphComponent>
5.29 class IDableDigraphComponent : public _Base {
5.30 @@ -372,7 +372,7 @@
5.31 ///
5.32 /// This class provides beside the core undirected graph features
5.33 /// core id functions for the undirected graph structure. The
5.34 - /// most of the base undirected graphs should be conform to this
5.35 + /// most of the base undirected graphs should conform to this
5.36 /// concept. The id's are unique and immutable.
5.37 template <typename _Base = BaseGraphComponent>
5.38 class IDableGraphComponent : public IDableDigraphComponent<_Base> {
6.1 --- a/lemon/dfs.h Mon Feb 23 15:03:55 2009 +0000
6.2 +++ b/lemon/dfs.h Mon Feb 23 15:04:10 2009 +0000
6.3 @@ -49,11 +49,11 @@
6.4 ///arcs of the %DFS paths.
6.5 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.6 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
6.7 - ///Instantiates a PredMap.
6.8 + ///Instantiates a \c PredMap.
6.9
6.10 - ///This function instantiates a PredMap.
6.11 + ///This function instantiates a \ref PredMap.
6.12 ///\param g is the digraph, to which we would like to define the
6.13 - ///PredMap.
6.14 + ///\ref PredMap.
6.15 static PredMap *createPredMap(const Digraph &g)
6.16 {
6.17 return new PredMap(g);
6.18 @@ -64,11 +64,11 @@
6.19 ///The type of the map that indicates which nodes are processed.
6.20 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.21 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
6.22 - ///Instantiates a ProcessedMap.
6.23 + ///Instantiates a \c ProcessedMap.
6.24
6.25 - ///This function instantiates a ProcessedMap.
6.26 + ///This function instantiates a \ref ProcessedMap.
6.27 ///\param g is the digraph, to which
6.28 - ///we would like to define the ProcessedMap
6.29 + ///we would like to define the \ref ProcessedMap.
6.30 #ifdef DOXYGEN
6.31 static ProcessedMap *createProcessedMap(const Digraph &g)
6.32 #else
6.33 @@ -83,11 +83,11 @@
6.34 ///The type of the map that indicates which nodes are reached.
6.35 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
6.36 typedef typename Digraph::template NodeMap<bool> ReachedMap;
6.37 - ///Instantiates a ReachedMap.
6.38 + ///Instantiates a \c ReachedMap.
6.39
6.40 - ///This function instantiates a ReachedMap.
6.41 + ///This function instantiates a \ref ReachedMap.
6.42 ///\param g is the digraph, to which
6.43 - ///we would like to define the ReachedMap.
6.44 + ///we would like to define the \ref ReachedMap.
6.45 static ReachedMap *createReachedMap(const Digraph &g)
6.46 {
6.47 return new ReachedMap(g);
6.48 @@ -98,11 +98,11 @@
6.49 ///The type of the map that stores the distances of the nodes.
6.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.51 typedef typename Digraph::template NodeMap<int> DistMap;
6.52 - ///Instantiates a DistMap.
6.53 + ///Instantiates a \c DistMap.
6.54
6.55 - ///This function instantiates a DistMap.
6.56 + ///This function instantiates a \ref DistMap.
6.57 ///\param g is the digraph, to which we would like to define the
6.58 - ///DistMap.
6.59 + ///\ref DistMap.
6.60 static DistMap *createDistMap(const Digraph &g)
6.61 {
6.62 return new DistMap(g);
6.63 @@ -220,10 +220,10 @@
6.64 }
6.65 };
6.66 ///\brief \ref named-templ-param "Named parameter" for setting
6.67 - ///PredMap type.
6.68 + ///\c PredMap type.
6.69 ///
6.70 ///\ref named-templ-param "Named parameter" for setting
6.71 - ///PredMap type.
6.72 + ///\c PredMap type.
6.73 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.74 template <class T>
6.75 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
6.76 @@ -240,10 +240,10 @@
6.77 }
6.78 };
6.79 ///\brief \ref named-templ-param "Named parameter" for setting
6.80 - ///DistMap type.
6.81 + ///\c DistMap type.
6.82 ///
6.83 ///\ref named-templ-param "Named parameter" for setting
6.84 - ///DistMap type.
6.85 + ///\c DistMap type.
6.86 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.87 template <class T>
6.88 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
6.89 @@ -260,10 +260,10 @@
6.90 }
6.91 };
6.92 ///\brief \ref named-templ-param "Named parameter" for setting
6.93 - ///ReachedMap type.
6.94 + ///\c ReachedMap type.
6.95 ///
6.96 ///\ref named-templ-param "Named parameter" for setting
6.97 - ///ReachedMap type.
6.98 + ///\c ReachedMap type.
6.99 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
6.100 template <class T>
6.101 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
6.102 @@ -280,10 +280,10 @@
6.103 }
6.104 };
6.105 ///\brief \ref named-templ-param "Named parameter" for setting
6.106 - ///ProcessedMap type.
6.107 + ///\c ProcessedMap type.
6.108 ///
6.109 ///\ref named-templ-param "Named parameter" for setting
6.110 - ///ProcessedMap type.
6.111 + ///\c ProcessedMap type.
6.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
6.113 template <class T>
6.114 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
6.115 @@ -298,10 +298,10 @@
6.116 }
6.117 };
6.118 ///\brief \ref named-templ-param "Named parameter" for setting
6.119 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
6.120 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
6.121 ///
6.122 ///\ref named-templ-param "Named parameter" for setting
6.123 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
6.124 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
6.125 ///If you don't set it explicitly, it will be automatically allocated.
6.126 struct SetStandardProcessedMap :
6.127 public Dfs< Digraph, SetStandardProcessedMapTraits > {
6.128 @@ -1126,9 +1126,9 @@
6.129 ///
6.130 /// This class defines the interface of the DfsVisit events, and
6.131 /// it could be the base of a real visitor class.
6.132 - template <typename _Digraph>
6.133 + template <typename GR>
6.134 struct DfsVisitor {
6.135 - typedef _Digraph Digraph;
6.136 + typedef GR Digraph;
6.137 typedef typename Digraph::Arc Arc;
6.138 typedef typename Digraph::Node Node;
6.139 /// \brief Called for the source node of the DFS.
6.140 @@ -1164,9 +1164,9 @@
6.141 void backtrack(const Arc& arc) {}
6.142 };
6.143 #else
6.144 - template <typename _Digraph>
6.145 + template <typename GR>
6.146 struct DfsVisitor {
6.147 - typedef _Digraph Digraph;
6.148 + typedef GR Digraph;
6.149 typedef typename Digraph::Arc Arc;
6.150 typedef typename Digraph::Node Node;
6.151 void start(const Node&) {}
6.152 @@ -1199,11 +1199,11 @@
6.153 ///
6.154 /// Default traits class of DfsVisit class.
6.155 /// \tparam _Digraph The type of the digraph the algorithm runs on.
6.156 - template<class _Digraph>
6.157 + template<class GR>
6.158 struct DfsVisitDefaultTraits {
6.159
6.160 /// \brief The type of the digraph the algorithm runs on.
6.161 - typedef _Digraph Digraph;
6.162 + typedef GR Digraph;
6.163
6.164 /// \brief The type of the map that indicates which nodes are reached.
6.165 ///
6.166 @@ -1224,12 +1224,12 @@
6.167
6.168 /// \ingroup search
6.169 ///
6.170 - /// \brief %DFS algorithm class with visitor interface.
6.171 + /// \brief DFS algorithm class with visitor interface.
6.172 ///
6.173 - /// This class provides an efficient implementation of the %DFS algorithm
6.174 + /// This class provides an efficient implementation of the DFS algorithm
6.175 /// with visitor interface.
6.176 ///
6.177 - /// The %DfsVisit class provides an alternative interface to the Dfs
6.178 + /// The DfsVisit class provides an alternative interface to the Dfs
6.179 /// class. It works with callback mechanism, the DfsVisit object calls
6.180 /// the member functions of the \c Visitor class on every DFS event.
6.181 ///
6.182 @@ -1238,37 +1238,37 @@
6.183 /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
6.184 /// instead.
6.185 ///
6.186 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
6.187 - /// The default value is
6.188 - /// \ref ListDigraph. The value of _Digraph is not used directly by
6.189 - /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
6.190 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
6.191 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
6.192 + /// \tparam GR The type of the digraph the algorithm runs on.
6.193 + /// The default type is \ref ListDigraph.
6.194 + /// The value of GR is not used directly by \ref DfsVisit,
6.195 + /// it is only passed to \ref DfsVisitDefaultTraits.
6.196 + /// \tparam VS The Visitor type that is used by the algorithm.
6.197 + /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
6.198 /// does not observe the DFS events. If you want to observe the DFS
6.199 /// events, you should implement your own visitor class.
6.200 - /// \tparam _Traits Traits class to set various data types used by the
6.201 + /// \tparam TR Traits class to set various data types used by the
6.202 /// algorithm. The default traits class is
6.203 - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
6.204 + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
6.205 /// See \ref DfsVisitDefaultTraits for the documentation of
6.206 /// a DFS visit traits class.
6.207 #ifdef DOXYGEN
6.208 - template <typename _Digraph, typename _Visitor, typename _Traits>
6.209 + template <typename GR, typename VS, typename TR>
6.210 #else
6.211 - template <typename _Digraph = ListDigraph,
6.212 - typename _Visitor = DfsVisitor<_Digraph>,
6.213 - typename _Traits = DfsVisitDefaultTraits<_Digraph> >
6.214 + template <typename GR = ListDigraph,
6.215 + typename VS = DfsVisitor<GR>,
6.216 + typename TR = DfsVisitDefaultTraits<GR> >
6.217 #endif
6.218 class DfsVisit {
6.219 public:
6.220
6.221 ///The traits class.
6.222 - typedef _Traits Traits;
6.223 + typedef TR Traits;
6.224
6.225 ///The type of the digraph the algorithm runs on.
6.226 typedef typename Traits::Digraph Digraph;
6.227
6.228 ///The visitor type used by the algorithm.
6.229 - typedef _Visitor Visitor;
6.230 + typedef VS Visitor;
6.231
6.232 ///The type of the map that indicates which nodes are reached.
6.233 typedef typename Traits::ReachedMap ReachedMap;
7.1 --- a/lemon/dijkstra.h Mon Feb 23 15:03:55 2009 +0000
7.2 +++ b/lemon/dijkstra.h Mon Feb 23 15:04:10 2009 +0000
7.3 @@ -73,7 +73,7 @@
7.4 ///The type of the length of the arcs.
7.5 typedef typename LM::Value Value;
7.6
7.7 - /// Operation traits for Dijkstra algorithm.
7.8 + /// Operation traits for %Dijkstra algorithm.
7.9
7.10 /// This class defines the operations that are used in the algorithm.
7.11 /// \see DijkstraDefaultOperationTraits
7.12 @@ -84,7 +84,7 @@
7.13 /// The cross reference type used by the heap.
7.14 /// Usually it is \c Digraph::NodeMap<int>.
7.15 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
7.16 - ///Instantiates a \ref HeapCrossRef.
7.17 + ///Instantiates a \c HeapCrossRef.
7.18
7.19 ///This function instantiates a \ref HeapCrossRef.
7.20 /// \param g is the digraph, to which we would like to define the
7.21 @@ -94,14 +94,14 @@
7.22 return new HeapCrossRef(g);
7.23 }
7.24
7.25 - ///The heap type used by the Dijkstra algorithm.
7.26 + ///The heap type used by the %Dijkstra algorithm.
7.27
7.28 ///The heap type used by the Dijkstra algorithm.
7.29 ///
7.30 ///\sa BinHeap
7.31 ///\sa Dijkstra
7.32 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
7.33 - ///Instantiates a \ref Heap.
7.34 + ///Instantiates a \c Heap.
7.35
7.36 ///This function instantiates a \ref Heap.
7.37 static Heap *createHeap(HeapCrossRef& r)
7.38 @@ -116,11 +116,11 @@
7.39 ///arcs of the shortest paths.
7.40 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.41 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
7.42 - ///Instantiates a PredMap.
7.43 + ///Instantiates a \c PredMap.
7.44
7.45 - ///This function instantiates a PredMap.
7.46 + ///This function instantiates a \ref PredMap.
7.47 ///\param g is the digraph, to which we would like to define the
7.48 - ///PredMap.
7.49 + ///\ref PredMap.
7.50 static PredMap *createPredMap(const Digraph &g)
7.51 {
7.52 return new PredMap(g);
7.53 @@ -132,11 +132,11 @@
7.54 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.55 ///By default it is a NullMap.
7.56 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
7.57 - ///Instantiates a ProcessedMap.
7.58 + ///Instantiates a \c ProcessedMap.
7.59
7.60 - ///This function instantiates a ProcessedMap.
7.61 + ///This function instantiates a \ref ProcessedMap.
7.62 ///\param g is the digraph, to which
7.63 - ///we would like to define the ProcessedMap
7.64 + ///we would like to define the \ref ProcessedMap.
7.65 #ifdef DOXYGEN
7.66 static ProcessedMap *createProcessedMap(const Digraph &g)
7.67 #else
7.68 @@ -151,11 +151,11 @@
7.69 ///The type of the map that stores the distances of the nodes.
7.70 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.71 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
7.72 - ///Instantiates a DistMap.
7.73 + ///Instantiates a \c DistMap.
7.74
7.75 - ///This function instantiates a DistMap.
7.76 + ///This function instantiates a \ref DistMap.
7.77 ///\param g is the digraph, to which we would like to define
7.78 - ///the DistMap
7.79 + ///the \ref DistMap.
7.80 static DistMap *createDistMap(const Digraph &g)
7.81 {
7.82 return new DistMap(g);
7.83 @@ -216,7 +216,8 @@
7.84 typedef typename TR::HeapCrossRef HeapCrossRef;
7.85 ///The heap type used by the algorithm.
7.86 typedef typename TR::Heap Heap;
7.87 - ///The operation traits class.
7.88 + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
7.89 + ///of the algorithm.
7.90 typedef typename TR::OperationTraits OperationTraits;
7.91
7.92 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
7.93 @@ -232,7 +233,7 @@
7.94 //Pointer to the underlying digraph.
7.95 const Digraph *G;
7.96 //Pointer to the length map.
7.97 - const LengthMap *length;
7.98 + const LengthMap *_length;
7.99 //Pointer to the map of predecessors arcs.
7.100 PredMap *_pred;
7.101 //Indicates if _pred is locally allocated (true) or not.
7.102 @@ -297,10 +298,10 @@
7.103 }
7.104 };
7.105 ///\brief \ref named-templ-param "Named parameter" for setting
7.106 - ///PredMap type.
7.107 + ///\c PredMap type.
7.108 ///
7.109 ///\ref named-templ-param "Named parameter" for setting
7.110 - ///PredMap type.
7.111 + ///\c PredMap type.
7.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.113 template <class T>
7.114 struct SetPredMap
7.115 @@ -318,10 +319,10 @@
7.116 }
7.117 };
7.118 ///\brief \ref named-templ-param "Named parameter" for setting
7.119 - ///DistMap type.
7.120 + ///\c DistMap type.
7.121 ///
7.122 ///\ref named-templ-param "Named parameter" for setting
7.123 - ///DistMap type.
7.124 + ///\c DistMap type.
7.125 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.126 template <class T>
7.127 struct SetDistMap
7.128 @@ -339,10 +340,10 @@
7.129 }
7.130 };
7.131 ///\brief \ref named-templ-param "Named parameter" for setting
7.132 - ///ProcessedMap type.
7.133 + ///\c ProcessedMap type.
7.134 ///
7.135 ///\ref named-templ-param "Named parameter" for setting
7.136 - ///ProcessedMap type.
7.137 + ///\c ProcessedMap type.
7.138 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
7.139 template <class T>
7.140 struct SetProcessedMap
7.141 @@ -358,10 +359,10 @@
7.142 }
7.143 };
7.144 ///\brief \ref named-templ-param "Named parameter" for setting
7.145 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
7.146 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
7.147 ///
7.148 ///\ref named-templ-param "Named parameter" for setting
7.149 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
7.150 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
7.151 ///If you don't set it explicitly, it will be automatically allocated.
7.152 struct SetStandardProcessedMap
7.153 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
7.154 @@ -439,7 +440,7 @@
7.155 ///\c OperationTraits type
7.156 ///
7.157 ///\ref named-templ-param "Named parameter" for setting
7.158 - ///\ref OperationTraits type.
7.159 + ///\c OperationTraits type.
7.160 template <class T>
7.161 struct SetOperationTraits
7.162 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
7.163 @@ -458,10 +459,10 @@
7.164 ///Constructor.
7.165
7.166 ///Constructor.
7.167 - ///\param _g The digraph the algorithm runs on.
7.168 - ///\param _length The length map used by the algorithm.
7.169 - Dijkstra(const Digraph& _g, const LengthMap& _length) :
7.170 - G(&_g), length(&_length),
7.171 + ///\param g The digraph the algorithm runs on.
7.172 + ///\param length The length map used by the algorithm.
7.173 + Dijkstra(const Digraph& g, const LengthMap& length) :
7.174 + G(&g), _length(&length),
7.175 _pred(NULL), local_pred(false),
7.176 _dist(NULL), local_dist(false),
7.177 _processed(NULL), local_processed(false),
7.178 @@ -485,7 +486,7 @@
7.179 ///\return <tt> (*this) </tt>
7.180 Dijkstra &lengthMap(const LengthMap &m)
7.181 {
7.182 - length = &m;
7.183 + _length = &m;
7.184 return *this;
7.185 }
7.186
7.187 @@ -638,12 +639,12 @@
7.188 Node w=G->target(e);
7.189 switch(_heap->state(w)) {
7.190 case Heap::PRE_HEAP:
7.191 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
7.192 + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
7.193 _pred->set(w,e);
7.194 break;
7.195 case Heap::IN_HEAP:
7.196 {
7.197 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
7.198 + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
7.199 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
7.200 _heap->decrease(w, newvalue);
7.201 _pred->set(w,e);
8.1 --- a/lemon/preflow.h Mon Feb 23 15:03:55 2009 +0000
8.2 +++ b/lemon/preflow.h Mon Feb 23 15:04:10 2009 +0000
8.3 @@ -31,19 +31,19 @@
8.4 /// \brief Default traits class of Preflow class.
8.5 ///
8.6 /// Default traits class of Preflow class.
8.7 - /// \tparam _Digraph Digraph type.
8.8 - /// \tparam _CapacityMap Capacity map type.
8.9 - template <typename _Digraph, typename _CapacityMap>
8.10 + /// \tparam GR Digraph type.
8.11 + /// \tparam CM Capacity map type.
8.12 + template <typename GR, typename CM>
8.13 struct PreflowDefaultTraits {
8.14
8.15 /// \brief The type of the digraph the algorithm runs on.
8.16 - typedef _Digraph Digraph;
8.17 + typedef GR Digraph;
8.18
8.19 /// \brief The type of the map that stores the arc capacities.
8.20 ///
8.21 /// The type of the map that stores the arc capacities.
8.22 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
8.23 - typedef _CapacityMap CapacityMap;
8.24 + typedef CM CapacityMap;
8.25
8.26 /// \brief The type of the flow values.
8.27 typedef typename CapacityMap::Value Value;
8.28 @@ -104,21 +104,21 @@
8.29 /// the maximum flow value and the minimum cut is obtained. The
8.30 /// second phase constructs a feasible maximum flow on each arc.
8.31 ///
8.32 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
8.33 - /// \tparam _CapacityMap The type of the capacity map. The default map
8.34 - /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
8.35 + /// \tparam GR The type of the digraph the algorithm runs on.
8.36 + /// \tparam CM The type of the capacity map. The default map
8.37 + /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
8.38 #ifdef DOXYGEN
8.39 - template <typename _Digraph, typename _CapacityMap, typename _Traits>
8.40 + template <typename GR, typename CM, typename TR>
8.41 #else
8.42 - template <typename _Digraph,
8.43 - typename _CapacityMap = typename _Digraph::template ArcMap<int>,
8.44 - typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
8.45 + template <typename GR,
8.46 + typename CM = typename GR::template ArcMap<int>,
8.47 + typename TR = PreflowDefaultTraits<GR, CM> >
8.48 #endif
8.49 class Preflow {
8.50 public:
8.51
8.52 ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
8.53 - typedef _Traits Traits;
8.54 + typedef TR Traits;
8.55 ///The type of the digraph the algorithm runs on.
8.56 typedef typename Traits::Digraph Digraph;
8.57 ///The type of the capacity map.