# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1235401450 0
# Node ID 6d3a9eec82b45b4b2affe75fd9eed0081a43a249
# Parent 6643fc6dafc12d8b86079d81598934a0f1d422da# Parent 9605e051942f399348f853dccb5e19e24c0b1cde
Merge
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/bfs.h
--- a/lemon/bfs.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/bfs.h Mon Feb 23 15:04:10 2009 +0000
@@ -49,11 +49,11 @@
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
- ///Instantiates a PredMap.
+ ///Instantiates a \c PredMap.
- ///This function instantiates a PredMap.
+ ///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
- ///PredMap.
+ ///\ref PredMap.
static PredMap *createPredMap(const Digraph &g)
{
return new PredMap(g);
@@ -64,11 +64,11 @@
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
- ///Instantiates a ProcessedMap.
+ ///Instantiates a \c ProcessedMap.
- ///This function instantiates a ProcessedMap.
+ ///This function instantiates a \ref ProcessedMap.
///\param g is the digraph, to which
- ///we would like to define the ProcessedMap
+ ///we would like to define the \ref ProcessedMap
#ifdef DOXYGEN
static ProcessedMap *createProcessedMap(const Digraph &g)
#else
@@ -83,11 +83,11 @@
///The type of the map that indicates which nodes are reached.
///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap<bool> ReachedMap;
- ///Instantiates a ReachedMap.
+ ///Instantiates a \c ReachedMap.
- ///This function instantiates a ReachedMap.
+ ///This function instantiates a \ref ReachedMap.
///\param g is the digraph, to which
- ///we would like to define the ReachedMap.
+ ///we would like to define the \ref ReachedMap.
static ReachedMap *createReachedMap(const Digraph &g)
{
return new ReachedMap(g);
@@ -98,11 +98,11 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<int> DistMap;
- ///Instantiates a DistMap.
+ ///Instantiates a \c DistMap.
- ///This function instantiates a DistMap.
+ ///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define the
- ///DistMap.
+ ///\ref DistMap.
static DistMap *createDistMap(const Digraph &g)
{
return new DistMap(g);
@@ -221,10 +221,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
@@ -241,10 +241,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
@@ -261,10 +261,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ReachedMap type.
+ ///\c ReachedMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///ReachedMap type.
+ ///\c ReachedMap type.
///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template <class T>
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
@@ -281,10 +281,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
@@ -300,10 +300,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///If you don't set it explicitly, it will be automatically allocated.
struct SetStandardProcessedMap :
public Bfs< Digraph, SetStandardProcessedMapTraits > {
@@ -1194,9 +1194,9 @@
///
/// This class defines the interface of the BfsVisit events, and
/// it could be the base of a real visitor class.
- template <typename _Digraph>
+ template <typename GR>
struct BfsVisitor {
- typedef _Digraph Digraph;
+ typedef GR Digraph;
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
/// \brief Called for the source node(s) of the BFS.
@@ -1224,9 +1224,9 @@
void examine(const Arc& arc) {}
};
#else
- template <typename _Digraph>
+ template <typename GR>
struct BfsVisitor {
- typedef _Digraph Digraph;
+ typedef GR Digraph;
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
void start(const Node&) {}
@@ -1254,12 +1254,12 @@
/// \brief Default traits class of BfsVisit class.
///
/// Default traits class of BfsVisit class.
- /// \tparam _Digraph The type of the digraph the algorithm runs on.
- template<class _Digraph>
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ template<class GR>
struct BfsVisitDefaultTraits {
/// \brief The type of the digraph the algorithm runs on.
- typedef _Digraph Digraph;
+ typedef GR Digraph;
/// \brief The type of the map that indicates which nodes are reached.
///
@@ -1280,12 +1280,12 @@
/// \ingroup search
///
- /// \brief %BFS algorithm class with visitor interface.
+ /// \brief BFS algorithm class with visitor interface.
///
- /// This class provides an efficient implementation of the %BFS algorithm
+ /// This class provides an efficient implementation of the BFS algorithm
/// with visitor interface.
///
- /// The %BfsVisit class provides an alternative interface to the Bfs
+ /// The BfsVisit class provides an alternative interface to the Bfs
/// class. It works with callback mechanism, the BfsVisit object calls
/// the member functions of the \c Visitor class on every BFS event.
///
@@ -1294,37 +1294,37 @@
/// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
/// instead.
///
- /// \tparam _Digraph The type of the digraph the algorithm runs on.
- /// The default value is
- /// \ref ListDigraph. The value of _Digraph is not used directly by
- /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
- /// \tparam _Visitor The Visitor type that is used by the algorithm.
- /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// The default type is \ref ListDigraph.
+ /// The value of GR is not used directly by \ref BfsVisit,
+ /// it is only passed to \ref BfsVisitDefaultTraits.
+ /// \tparam VS The Visitor type that is used by the algorithm.
+ /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
/// does not observe the BFS events. If you want to observe the BFS
/// events, you should implement your own visitor class.
- /// \tparam _Traits Traits class to set various data types used by the
+ /// \tparam TR Traits class to set various data types used by the
/// algorithm. The default traits class is
- /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
+ /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
/// See \ref BfsVisitDefaultTraits for the documentation of
/// a BFS visit traits class.
#ifdef DOXYGEN
- template <typename _Digraph, typename _Visitor, typename _Traits>
+ template <typename GR, typename VS, typename TR>
#else
- template <typename _Digraph = ListDigraph,
- typename _Visitor = BfsVisitor<_Digraph>,
- typename _Traits = BfsVisitDefaultTraits<_Digraph> >
+ template <typename GR = ListDigraph,
+ typename VS = BfsVisitor<GR>,
+ typename TR = BfsVisitDefaultTraits<GR> >
#endif
class BfsVisit {
public:
///The traits class.
- typedef _Traits Traits;
+ typedef TR Traits;
///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
///The visitor type used by the algorithm.
- typedef _Visitor Visitor;
+ typedef VS Visitor;
///The type of the map that indicates which nodes are reached.
typedef typename Traits::ReachedMap ReachedMap;
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/bits/array_map.h
--- a/lemon/bits/array_map.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/bits/array_map.h Mon Feb 23 15:04:10 2009 +0000
@@ -135,7 +135,7 @@
// \brief Template assign operator.
//
- // The given parameter should be conform to the ReadMap
+ // The given parameter should conform to the ReadMap
// concecpt and could be indiced by the current item set of
// the NodeMap. In this case the value for each item
// is assigned by the value of the given ReadMap.
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/bits/vector_map.h
--- a/lemon/bits/vector_map.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/bits/vector_map.h Mon Feb 23 15:04:10 2009 +0000
@@ -124,7 +124,7 @@
// \brief Template assign operator.
//
- // The given parameter should be conform to the ReadMap
+ // The given parameter should conform to the ReadMap
// concecpt and could be indiced by the current item set of
// the NodeMap. In this case the value for each item
// is assigned by the value of the given ReadMap.
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/circulation.h
--- a/lemon/circulation.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/circulation.h Mon Feb 23 15:04:10 2009 +0000
@@ -31,30 +31,30 @@
/// \brief Default traits class of Circulation class.
///
/// Default traits class of Circulation class.
- /// \tparam _Diraph Digraph type.
- /// \tparam _LCapMap Lower bound capacity map type.
- /// \tparam _UCapMap Upper bound capacity map type.
- /// \tparam _DeltaMap Delta map type.
- template <typename _Diraph, typename _LCapMap,
- typename _UCapMap, typename _DeltaMap>
+ /// \tparam GR Digraph type.
+ /// \tparam LM Lower bound capacity map type.
+ /// \tparam UM Upper bound capacity map type.
+ /// \tparam DM Delta map type.
+ template <typename GR, typename LM,
+ typename UM, typename DM>
struct CirculationDefaultTraits {
/// \brief The type of the digraph the algorithm runs on.
- typedef _Diraph Digraph;
+ typedef GR Digraph;
/// \brief The type of the map that stores the circulation lower
/// bound.
///
/// The type of the map that stores the circulation lower bound.
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef _LCapMap LCapMap;
+ typedef LM LCapMap;
/// \brief The type of the map that stores the circulation upper
/// bound.
///
/// The type of the map that stores the circulation upper bound.
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef _UCapMap UCapMap;
+ typedef UM UCapMap;
/// \brief The type of the map that stores the lower bound for
/// the supply of the nodes.
@@ -62,7 +62,7 @@
/// The type of the map that stores the lower bound for the supply
/// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
/// concept.
- typedef _DeltaMap DeltaMap;
+ typedef DM DeltaMap;
/// \brief The type of the flow values.
typedef typename DeltaMap::Value Value;
@@ -137,35 +137,33 @@
\ref min_cost_flow "minimum cost flow" problem can be calculated
in this way.
- \tparam _Digraph The type of the digraph the algorithm runs on.
- \tparam _LCapMap The type of the lower bound capacity map. The default
- map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
- \tparam _UCapMap The type of the upper bound capacity map. The default
- map type is \c _LCapMap.
- \tparam _DeltaMap The type of the map that stores the lower bound
+ \tparam GR The type of the digraph the algorithm runs on.
+ \tparam LM The type of the lower bound capacity map. The default
+ map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ \tparam UM The type of the upper bound capacity map. The default
+ map type is \c LM.
+ \tparam DM The type of the map that stores the lower bound
for the supply of the nodes. The default map type is
- \c _Digraph::ArcMap<_UCapMap::Value>.
+ \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
*/
#ifdef DOXYGEN
-template< typename _Digraph,
- typename _LCapMap,
- typename _UCapMap,
- typename _DeltaMap,
- typename _Traits >
+template< typename GR,
+ typename LM,
+ typename UM,
+ typename DM,
+ typename TR >
#else
-template< typename _Digraph,
- typename _LCapMap = typename _Digraph::template ArcMap<int>,
- typename _UCapMap = _LCapMap,
- typename _DeltaMap = typename _Digraph::
- template NodeMap<typename _UCapMap::Value>,
- typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
- _UCapMap, _DeltaMap> >
+template< typename GR,
+ typename LM = typename GR::template ArcMap<int>,
+ typename UM = LM,
+ typename DM = typename GR::template NodeMap<typename UM::Value>,
+ typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
#endif
class Circulation {
public:
///The \ref CirculationDefaultTraits "traits class" of the algorithm.
- typedef _Traits Traits;
+ typedef TR Traits;
///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
///The type of the flow values.
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/concepts/graph_components.h
--- a/lemon/concepts/graph_components.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/concepts/graph_components.h Mon Feb 23 15:04:10 2009 +0000
@@ -114,7 +114,7 @@
/// \brief An empty base directed graph class.
///
/// This class provides the minimal set of features needed for a
- /// directed graph structure. All digraph concepts have to be
+ /// directed graph structure. All digraph concepts have to
/// conform to this base directed graph. It just provides types
/// for nodes and arcs and functions to get the source and the
/// target of the arcs.
@@ -179,7 +179,7 @@
///
/// This class provides the minimal set of features needed for an
/// undirected graph structure. All undirected graph concepts have
- /// to be conform to this base graph. It just provides types for
+ /// to conform to this base graph. It just provides types for
/// nodes, arcs and edges and functions to get the
/// source and the target of the arcs and edges,
/// conversion from arcs to edges and function to get
@@ -294,7 +294,7 @@
///
/// This class provides beside the core digraph features
/// core id functions for the digraph structure.
- /// The most of the base digraphs should be conform to this concept.
+ /// The most of the base digraphs should conform to this concept.
/// The id's are unique and immutable.
template <typename _Base = BaseDigraphComponent>
class IDableDigraphComponent : public _Base {
@@ -372,7 +372,7 @@
///
/// This class provides beside the core undirected graph features
/// core id functions for the undirected graph structure. The
- /// most of the base undirected graphs should be conform to this
+ /// most of the base undirected graphs should conform to this
/// concept. The id's are unique and immutable.
template <typename _Base = BaseGraphComponent>
class IDableGraphComponent : public IDableDigraphComponent<_Base> {
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/dfs.h
--- a/lemon/dfs.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/dfs.h Mon Feb 23 15:04:10 2009 +0000
@@ -49,11 +49,11 @@
///arcs of the %DFS paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
- ///Instantiates a PredMap.
+ ///Instantiates a \c PredMap.
- ///This function instantiates a PredMap.
+ ///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
- ///PredMap.
+ ///\ref PredMap.
static PredMap *createPredMap(const Digraph &g)
{
return new PredMap(g);
@@ -64,11 +64,11 @@
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
- ///Instantiates a ProcessedMap.
+ ///Instantiates a \c ProcessedMap.
- ///This function instantiates a ProcessedMap.
+ ///This function instantiates a \ref ProcessedMap.
///\param g is the digraph, to which
- ///we would like to define the ProcessedMap
+ ///we would like to define the \ref ProcessedMap.
#ifdef DOXYGEN
static ProcessedMap *createProcessedMap(const Digraph &g)
#else
@@ -83,11 +83,11 @@
///The type of the map that indicates which nodes are reached.
///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap<bool> ReachedMap;
- ///Instantiates a ReachedMap.
+ ///Instantiates a \c ReachedMap.
- ///This function instantiates a ReachedMap.
+ ///This function instantiates a \ref ReachedMap.
///\param g is the digraph, to which
- ///we would like to define the ReachedMap.
+ ///we would like to define the \ref ReachedMap.
static ReachedMap *createReachedMap(const Digraph &g)
{
return new ReachedMap(g);
@@ -98,11 +98,11 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<int> DistMap;
- ///Instantiates a DistMap.
+ ///Instantiates a \c DistMap.
- ///This function instantiates a DistMap.
+ ///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define the
- ///DistMap.
+ ///\ref DistMap.
static DistMap *createDistMap(const Digraph &g)
{
return new DistMap(g);
@@ -220,10 +220,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
@@ -240,10 +240,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
@@ -260,10 +260,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ReachedMap type.
+ ///\c ReachedMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///ReachedMap type.
+ ///\c ReachedMap type.
///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template <class T>
struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
@@ -280,10 +280,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
@@ -298,10 +298,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///If you don't set it explicitly, it will be automatically allocated.
struct SetStandardProcessedMap :
public Dfs< Digraph, SetStandardProcessedMapTraits > {
@@ -1126,9 +1126,9 @@
///
/// This class defines the interface of the DfsVisit events, and
/// it could be the base of a real visitor class.
- template <typename _Digraph>
+ template <typename GR>
struct DfsVisitor {
- typedef _Digraph Digraph;
+ typedef GR Digraph;
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
/// \brief Called for the source node of the DFS.
@@ -1164,9 +1164,9 @@
void backtrack(const Arc& arc) {}
};
#else
- template <typename _Digraph>
+ template <typename GR>
struct DfsVisitor {
- typedef _Digraph Digraph;
+ typedef GR Digraph;
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
void start(const Node&) {}
@@ -1199,11 +1199,11 @@
///
/// Default traits class of DfsVisit class.
/// \tparam _Digraph The type of the digraph the algorithm runs on.
- template<class _Digraph>
+ template<class GR>
struct DfsVisitDefaultTraits {
/// \brief The type of the digraph the algorithm runs on.
- typedef _Digraph Digraph;
+ typedef GR Digraph;
/// \brief The type of the map that indicates which nodes are reached.
///
@@ -1224,12 +1224,12 @@
/// \ingroup search
///
- /// \brief %DFS algorithm class with visitor interface.
+ /// \brief DFS algorithm class with visitor interface.
///
- /// This class provides an efficient implementation of the %DFS algorithm
+ /// This class provides an efficient implementation of the DFS algorithm
/// with visitor interface.
///
- /// The %DfsVisit class provides an alternative interface to the Dfs
+ /// The DfsVisit class provides an alternative interface to the Dfs
/// class. It works with callback mechanism, the DfsVisit object calls
/// the member functions of the \c Visitor class on every DFS event.
///
@@ -1238,37 +1238,37 @@
/// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
/// instead.
///
- /// \tparam _Digraph The type of the digraph the algorithm runs on.
- /// The default value is
- /// \ref ListDigraph. The value of _Digraph is not used directly by
- /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
- /// \tparam _Visitor The Visitor type that is used by the algorithm.
- /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// The default type is \ref ListDigraph.
+ /// The value of GR is not used directly by \ref DfsVisit,
+ /// it is only passed to \ref DfsVisitDefaultTraits.
+ /// \tparam VS The Visitor type that is used by the algorithm.
+ /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
/// does not observe the DFS events. If you want to observe the DFS
/// events, you should implement your own visitor class.
- /// \tparam _Traits Traits class to set various data types used by the
+ /// \tparam TR Traits class to set various data types used by the
/// algorithm. The default traits class is
- /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
+ /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
/// See \ref DfsVisitDefaultTraits for the documentation of
/// a DFS visit traits class.
#ifdef DOXYGEN
- template <typename _Digraph, typename _Visitor, typename _Traits>
+ template <typename GR, typename VS, typename TR>
#else
- template <typename _Digraph = ListDigraph,
- typename _Visitor = DfsVisitor<_Digraph>,
- typename _Traits = DfsVisitDefaultTraits<_Digraph> >
+ template <typename GR = ListDigraph,
+ typename VS = DfsVisitor<GR>,
+ typename TR = DfsVisitDefaultTraits<GR> >
#endif
class DfsVisit {
public:
///The traits class.
- typedef _Traits Traits;
+ typedef TR Traits;
///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
///The visitor type used by the algorithm.
- typedef _Visitor Visitor;
+ typedef VS Visitor;
///The type of the map that indicates which nodes are reached.
typedef typename Traits::ReachedMap ReachedMap;
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/dijkstra.h
--- a/lemon/dijkstra.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/dijkstra.h Mon Feb 23 15:04:10 2009 +0000
@@ -73,7 +73,7 @@
///The type of the length of the arcs.
typedef typename LM::Value Value;
- /// Operation traits for Dijkstra algorithm.
+ /// Operation traits for %Dijkstra algorithm.
/// This class defines the operations that are used in the algorithm.
/// \see DijkstraDefaultOperationTraits
@@ -84,7 +84,7 @@
/// The cross reference type used by the heap.
/// Usually it is \c Digraph::NodeMap<int>.
typedef typename Digraph::template NodeMap<int> HeapCrossRef;
- ///Instantiates a \ref HeapCrossRef.
+ ///Instantiates a \c HeapCrossRef.
///This function instantiates a \ref HeapCrossRef.
/// \param g is the digraph, to which we would like to define the
@@ -94,14 +94,14 @@
return new HeapCrossRef(g);
}
- ///The heap type used by the Dijkstra algorithm.
+ ///The heap type used by the %Dijkstra algorithm.
///The heap type used by the Dijkstra algorithm.
///
///\sa BinHeap
///\sa Dijkstra
typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
- ///Instantiates a \ref Heap.
+ ///Instantiates a \c Heap.
///This function instantiates a \ref Heap.
static Heap *createHeap(HeapCrossRef& r)
@@ -116,11 +116,11 @@
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
- ///Instantiates a PredMap.
+ ///Instantiates a \c PredMap.
- ///This function instantiates a PredMap.
+ ///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
- ///PredMap.
+ ///\ref PredMap.
static PredMap *createPredMap(const Digraph &g)
{
return new PredMap(g);
@@ -132,11 +132,11 @@
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
///By default it is a NullMap.
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
- ///Instantiates a ProcessedMap.
+ ///Instantiates a \c ProcessedMap.
- ///This function instantiates a ProcessedMap.
+ ///This function instantiates a \ref ProcessedMap.
///\param g is the digraph, to which
- ///we would like to define the ProcessedMap
+ ///we would like to define the \ref ProcessedMap.
#ifdef DOXYGEN
static ProcessedMap *createProcessedMap(const Digraph &g)
#else
@@ -151,11 +151,11 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
- ///Instantiates a DistMap.
+ ///Instantiates a \c DistMap.
- ///This function instantiates a DistMap.
+ ///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define
- ///the DistMap
+ ///the \ref DistMap.
static DistMap *createDistMap(const Digraph &g)
{
return new DistMap(g);
@@ -216,7 +216,8 @@
typedef typename TR::HeapCrossRef HeapCrossRef;
///The heap type used by the algorithm.
typedef typename TR::Heap Heap;
- ///The operation traits class.
+ ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
+ ///of the algorithm.
typedef typename TR::OperationTraits OperationTraits;
///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
@@ -232,7 +233,7 @@
//Pointer to the underlying digraph.
const Digraph *G;
//Pointer to the length map.
- const LengthMap *length;
+ const LengthMap *_length;
//Pointer to the map of predecessors arcs.
PredMap *_pred;
//Indicates if _pred is locally allocated (true) or not.
@@ -297,10 +298,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///PredMap type.
+ ///\c PredMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetPredMap
@@ -318,10 +319,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///DistMap type.
+ ///\c DistMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetDistMap
@@ -339,10 +340,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type.
+ ///\c ProcessedMap type.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template <class T>
struct SetProcessedMap
@@ -358,10 +359,10 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///
///\ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+ ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
///If you don't set it explicitly, it will be automatically allocated.
struct SetStandardProcessedMap
: public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
@@ -439,7 +440,7 @@
///\c OperationTraits type
///
///\ref named-templ-param "Named parameter" for setting
- ///\ref OperationTraits type.
+ ///\c OperationTraits type.
template <class T>
struct SetOperationTraits
: public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
@@ -458,10 +459,10 @@
///Constructor.
///Constructor.
- ///\param _g The digraph the algorithm runs on.
- ///\param _length The length map used by the algorithm.
- Dijkstra(const Digraph& _g, const LengthMap& _length) :
- G(&_g), length(&_length),
+ ///\param g The digraph the algorithm runs on.
+ ///\param length The length map used by the algorithm.
+ Dijkstra(const Digraph& g, const LengthMap& length) :
+ G(&g), _length(&length),
_pred(NULL), local_pred(false),
_dist(NULL), local_dist(false),
_processed(NULL), local_processed(false),
@@ -485,7 +486,7 @@
///\return <tt> (*this) </tt>
Dijkstra &lengthMap(const LengthMap &m)
{
- length = &m;
+ _length = &m;
return *this;
}
@@ -638,12 +639,12 @@
Node w=G->target(e);
switch(_heap->state(w)) {
case Heap::PRE_HEAP:
- _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
+ _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
_pred->set(w,e);
break;
case Heap::IN_HEAP:
{
- Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
+ Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
_heap->decrease(w, newvalue);
_pred->set(w,e);
diff -r 6643fc6dafc1 -r 6d3a9eec82b4 lemon/preflow.h
--- a/lemon/preflow.h Mon Feb 23 15:03:55 2009 +0000
+++ b/lemon/preflow.h Mon Feb 23 15:04:10 2009 +0000
@@ -31,19 +31,19 @@
/// \brief Default traits class of Preflow class.
///
/// Default traits class of Preflow class.
- /// \tparam _Digraph Digraph type.
- /// \tparam _CapacityMap Capacity map type.
- template <typename _Digraph, typename _CapacityMap>
+ /// \tparam GR Digraph type.
+ /// \tparam CM Capacity map type.
+ template <typename GR, typename CM>
struct PreflowDefaultTraits {
/// \brief The type of the digraph the algorithm runs on.
- typedef _Digraph Digraph;
+ typedef GR Digraph;
/// \brief The type of the map that stores the arc capacities.
///
/// The type of the map that stores the arc capacities.
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef _CapacityMap CapacityMap;
+ typedef CM CapacityMap;
/// \brief The type of the flow values.
typedef typename CapacityMap::Value Value;
@@ -104,21 +104,21 @@
/// the maximum flow value and the minimum cut is obtained. The
/// second phase constructs a feasible maximum flow on each arc.
///
- /// \tparam _Digraph The type of the digraph the algorithm runs on.
- /// \tparam _CapacityMap The type of the capacity map. The default map
- /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// \tparam CM The type of the capacity map. The default map
+ /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
#ifdef DOXYGEN
- template <typename _Digraph, typename _CapacityMap, typename _Traits>
+ template <typename GR, typename CM, typename TR>
#else
- template <typename _Digraph,
- typename _CapacityMap = typename _Digraph::template ArcMap<int>,
- typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
+ template <typename GR,
+ typename CM = typename GR::template ArcMap<int>,
+ typename TR = PreflowDefaultTraits<GR, CM> >
#endif
class Preflow {
public:
///The \ref PreflowDefaultTraits "traits class" of the algorithm.
- typedef _Traits Traits;
+ typedef TR Traits;
///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
///The type of the capacity map.