1.1 --- a/doc/graphs.dox Mon Sep 27 18:11:27 2004 +0000
1.2 +++ b/doc/graphs.dox Tue Sep 28 07:00:58 2004 +0000
1.3 @@ -28,7 +28,7 @@
1.4
1.5 The implemented graph structures are the following.
1.6 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
1.7 -the hugo::skeleton::ErasableGraph "ErasableGraph" concept
1.8 +the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept
1.9 and it also have some convenience features.
1.10 \li \ref hugo::SmartGraph "SmartGraph" is a more memory
1.11 efficient version of \ref hugo::ListGraph "ListGraph". The
1.12 @@ -45,7 +45,7 @@
1.13 attach data to the edges in such a way that the stored data
1.14 are shared by the edge pairs.
1.15 \li \ref hugo::FullGraph "FullGraph"
1.16 -implements a full graph. It is a \ref ConstGraph, so you cannot
1.17 +implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot
1.18 change the number of nodes once it is constructed. It is extremely memory
1.19 efficient: it uses constant amount of memory independently from the number of
1.20 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
2.1 --- a/src/hugo/bfs.h Mon Sep 27 18:11:27 2004 +0000
2.2 +++ b/src/hugo/bfs.h Tue Sep 28 07:00:58 2004 +0000
2.3 @@ -49,13 +49,13 @@
2.4 public:
2.5 ///The type of the underlying graph.
2.6 typedef GR Graph;
2.7 - ///.
2.8 + ///\e
2.9 typedef typename Graph::Node Node;
2.10 - ///.
2.11 + ///\e
2.12 typedef typename Graph::NodeIt NodeIt;
2.13 - ///.
2.14 + ///\e
2.15 typedef typename Graph::Edge Edge;
2.16 - ///.
2.17 + ///\e
2.18 typedef typename Graph::OutEdgeIt OutEdgeIt;
2.19
2.20 ///\brief The type of the map that stores the last
2.21 @@ -108,6 +108,7 @@
2.22 ///Constructor.
2.23
2.24 ///\param _G the graph the algorithm will run on.
2.25 + ///
2.26 Bfs(const Graph& _G) :
2.27 G(&_G),
2.28 predecessor(NULL), local_predecessor(false),
3.1 --- a/src/hugo/dfs.h Mon Sep 27 18:11:27 2004 +0000
3.2 +++ b/src/hugo/dfs.h Tue Sep 28 07:00:58 2004 +0000
3.3 @@ -48,13 +48,13 @@
3.4 public:
3.5 ///The type of the underlying graph.
3.6 typedef GR Graph;
3.7 - /// .
3.8 + ///\e
3.9 typedef typename Graph::Node Node;
3.10 - /// .
3.11 + ///\e
3.12 typedef typename Graph::NodeIt NodeIt;
3.13 - /// .
3.14 + ///\e
3.15 typedef typename Graph::Edge Edge;
3.16 - /// .
3.17 + ///\e
3.18 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.19
3.20 ///\brief The type of the map that stores the last
3.21 @@ -107,6 +107,7 @@
3.22 ///Constructor.
3.23
3.24 ///\param _G the graph the algorithm will run on.
3.25 + ///
3.26 Dfs(const Graph& _G) :
3.27 G(&_G),
3.28 predecessor(NULL), local_predecessor(false),
4.1 --- a/src/hugo/dijkstra.h Mon Sep 27 18:11:27 2004 +0000
4.2 +++ b/src/hugo/dijkstra.h Tue Sep 28 07:00:58 2004 +0000
4.3 @@ -71,13 +71,13 @@
4.4 public:
4.5 ///The type of the underlying graph.
4.6 typedef GR Graph;
4.7 - ///.
4.8 + ///\e
4.9 typedef typename Graph::Node Node;
4.10 - ///.
4.11 + ///\e
4.12 typedef typename Graph::NodeIt NodeIt;
4.13 - ///.
4.14 + ///\e
4.15 typedef typename Graph::Edge Edge;
4.16 - ///.
4.17 + ///\e
4.18 typedef typename Graph::OutEdgeIt OutEdgeIt;
4.19
4.20 ///The type of the length of the edges.
5.1 --- a/src/hugo/fib_heap.h Mon Sep 27 18:11:27 2004 +0000
5.2 +++ b/src/hugo/fib_heap.h Tue Sep 28 07:00:58 2004 +0000
5.3 @@ -35,7 +35,7 @@
5.4 ///This class implements the \e Fibonacci \e heap data structure. A \e heap
5.5 ///is a data structure for storing items with specified values called \e
5.6 ///priorities in such a way that finding the item with minimum priority is
5.7 - ///efficient. \ref Compare specifies the ordering of the priorities. In a heap
5.8 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
5.9 ///one can change the priority of an item, add or erase an item, etc.
5.10 ///
5.11 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
5.12 @@ -117,19 +117,19 @@
5.13 */
5.14 void push (Item const item, PrioType const value);
5.15
5.16 - ///Returns the item with minimum priority relative to \ref Compare.
5.17 + ///Returns the item with minimum priority relative to \c Compare.
5.18
5.19 /**
5.20 - This method returns the item with minimum priority relative to \ref
5.21 + This method returns the item with minimum priority relative to \c
5.22 Compare.
5.23 \pre The heap must be nonempty.
5.24 */
5.25 Item top() const { return container[minimum].name; }
5.26
5.27 - ///Returns the minimum priority relative to \ref Compare.
5.28 + ///Returns the minimum priority relative to \c Compare.
5.29
5.30 /**
5.31 - It returns the minimum priority relative to \ref Compare.
5.32 + It returns the minimum priority relative to \c Compare.
5.33 \pre The heap must be nonempty.
5.34 */
5.35 PrioType prio() const { return container[minimum].prio; }
5.36 @@ -155,10 +155,10 @@
5.37 }
5.38
5.39
5.40 - ///Deletes the item with minimum priority relative to \ref Compare.
5.41 + ///Deletes the item with minimum priority relative to \c Compare.
5.42
5.43 /**
5.44 - This method deletes the item with minimum priority relative to \ref
5.45 + This method deletes the item with minimum priority relative to \c
5.46 Compare from the heap.
5.47 \pre The heap must be non-empty.
5.48 */
5.49 @@ -177,7 +177,7 @@
5.50 /**
5.51 This method decreases the priority of \c item to \c value.
5.52 \pre \c item must be stored in the heap with priority at least \c
5.53 - value relative to \ref Compare.
5.54 + value relative to \c Compare.
5.55 */
5.56 void decrease (Item item, PrioType const value);
5.57
5.58 @@ -187,7 +187,7 @@
5.59 This method sets the priority of \c item to \c value. Though
5.60 there is no precondition on the priority of \c item, this
5.61 method should be used only if it is indeed necessary to increase
5.62 - (relative to \ref Compare) the priority of \c item, because this
5.63 + (relative to \c Compare) the priority of \c item, because this
5.64 method is inefficient.
5.65 */
5.66 void increase (Item item, PrioType const value) {
6.1 --- a/src/hugo/graph_wrapper.h Mon Sep 27 18:11:27 2004 +0000
6.2 +++ b/src/hugo/graph_wrapper.h Tue Sep 28 07:00:58 2004 +0000
6.3 @@ -605,6 +605,9 @@
6.4 ///\brief A wrapper for composing a subgraph of a
6.5 /// bidirected graph made from a directed one.
6.6 ///
6.7 + /// A wrapper for composing a subgraph of a
6.8 + /// bidirected graph made from a directed one.
6.9 + ///
6.10 ///\warning Graph wrappers are in even more experimental state than the other
6.11 ///parts of the lib. Use them at you own risk.
6.12 ///
7.1 --- a/src/hugo/list_graph.h Mon Sep 27 18:11:27 2004 +0000
7.2 +++ b/src/hugo/list_graph.h Tue Sep 28 07:00:58 2004 +0000
7.3 @@ -421,16 +421,16 @@
7.4 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
7.5 ///of oppositely directed edges.
7.6 ///There is a new edge map type called
7.7 - ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
7.8 + ///\ref hugo::SymListGraph::SymEdgeMap "SymEdgeMap"
7.9 ///that complements this
7.10 ///feature by
7.11 ///storing shared values for the edge pairs. The usual
7.12 - ///\ref Graph::EdgeMap "EdgeMap"
7.13 + ///\ref hugo::skeleton::StaticGraph::EdgeMap "EdgeMap"
7.14 ///can be used
7.15 ///as well.
7.16 ///
7.17 ///The oppositely directed edge can also be obtained easily
7.18 - ///using \ref opposite.
7.19 + ///using \ref hugo::SymListGraph::opposite() "opposite()" member function.
7.20 ///
7.21 ///Here erase(Edge) deletes a pair of edges.
7.22 ///
8.1 --- a/src/hugo/maps.h Mon Sep 27 18:11:27 2004 +0000
8.2 +++ b/src/hugo/maps.h Tue Sep 28 07:00:58 2004 +0000
8.3 @@ -35,9 +35,9 @@
8.4 class MapBase
8.5 {
8.6 public:
8.7 - /// .
8.8 + ///\e
8.9 typedef K KeyType;
8.10 - /// .
8.11 + ///\e
8.12 typedef T ValueType;
8.13 };
8.14
8.15 @@ -74,9 +74,10 @@
8.16 /// The value of the map will be uninitialized.
8.17 /// (More exactly it will be default constructed.)
8.18 ConstMap() {}
8.19 - /// .
8.20 + ///\e
8.21
8.22 /// \param _v The initial value of the map.
8.23 + ///
8.24 ConstMap(const T &_v) : v(_v) {}
8.25
8.26 T operator[](const K&) const { return v; }
9.1 --- a/src/hugo/preflow.h Mon Sep 27 18:11:27 2004 +0000
9.2 +++ b/src/hugo/preflow.h Tue Sep 28 07:00:58 2004 +0000
9.3 @@ -44,7 +44,8 @@
9.4 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref
9.5 ///setFlow.
9.6 ///
9.7 - ///After running \ref phase1() or \ref preflow(), the actual flow
9.8 + ///After running \ref hugo::Preflow::phase1() "phase1()"
9.9 + ///or \ref hugo::Preflow::run() "run()", the actual flow
9.10 ///value can be obtained by calling \ref flowValue(). The minimum
9.11 ///value cut can be written into a <tt>bool</tt> node map by
9.12 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes
9.13 @@ -96,8 +97,9 @@
9.14 ///the \e target.
9.15 ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at
9.16 ///least the sum of the out-flows in every node except the \e source.
9.17 - ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be
9.18 - ///set to the constant zero flow in the beginning of the algorithm in this case.
9.19 + ///- \c NO_FLOW: indicates an unspecified edge map. \c flow will be
9.20 + ///set to the constant zero flow in the beginning of
9.21 + ///the algorithm in this case.
9.22 ///
9.23 enum FlowEnum{
9.24 NO_FLOW,
9.25 @@ -194,9 +196,9 @@
9.26 ///first phase. After the first phase the maximum flow value and a
9.27 ///minimum value cut can already be computed, though a maximum flow
9.28 ///is not yet obtained. So after calling this method \ref flowValue
9.29 - ///and \ref actMinCut gives proper results.
9.30 - ///\warning \ref minCut, \ref minMinCut and \ref maxMinCut do not
9.31 - ///give minimum value cuts unless calling \ref phase2.
9.32 + ///and \ref MinCut() gives proper results.
9.33 + ///\warning \ref minCut(), \ref minMinCut() and \ref maxMinCut() do not
9.34 + ///give minimum value cuts unless calling \ref phase2().
9.35 void phase1()
9.36 {
9.37 int heur0=(int)(H0*n); //time while running 'bound decrease'
9.38 @@ -349,7 +351,7 @@
9.39 /// Returns the value of the maximum flow.
9.40
9.41 /// Returns the value of the maximum flow by returning the excess
9.42 - /// of the target node \ref t. This value equals to the value of
9.43 + /// of the target node \c t. This value equals to the value of
9.44 /// the maximum flow already after running \ref phase1.
9.45 Num flowValue() const {
9.46 return excess[t];
9.47 @@ -362,7 +364,7 @@
9.48 ///cut. This method can be called both after running \ref
9.49 ///phase1 and \ref phase2. It is much faster after
9.50 ///\ref phase1. \pre M should be a bool-valued node-map. \pre
9.51 - ///If \ref mincut is called after \ref phase2 then M should
9.52 + ///If \ref minCut() is called after \ref phase2() then M should
9.53 ///be initialized to false.
9.54 template<typename _CutMap>
9.55 void minCut(_CutMap& M) const {
9.56 @@ -425,7 +427,7 @@
9.57 ///Sets \c M to the characteristic vector of the minimum value cut
9.58 ///which is inclusionwise maximum. It is computed by processing a
9.59 ///backward bfs from the target node \c t in the residual graph.
9.60 - ///\pre \ref phase2() or preflow() should already be run.
9.61 + ///\pre \ref phase2() or run() should already be run.
9.62 template<typename _CutMap>
9.63 void maxMinCut(_CutMap& M) const {
9.64
10.1 --- a/src/hugo/skeletons/graph.h Mon Sep 27 18:11:27 2004 +0000
10.2 +++ b/src/hugo/skeletons/graph.h Tue Sep 28 07:00:58 2004 +0000
10.3 @@ -92,7 +92,7 @@
10.4
10.5 /// Inequality operator
10.6
10.7 - /// \sa \ref operator==(Node n)
10.8 + /// \sa operator==(Node n)
10.9 ///
10.10 bool operator!=(Node) const { return true; }
10.11
10.12 @@ -180,7 +180,7 @@
10.13 bool operator==(Edge) const { return true; }
10.14 /// Inequality operator
10.15
10.16 - /// \sa \ref operator==(Node n)
10.17 + /// \sa operator==(Node n)
10.18 ///
10.19 bool operator!=(Edge) const { return true; }
10.20 ///Comparison operator.
10.21 @@ -382,12 +382,12 @@
10.22 ///\todo Should each graph provide \c id?
10.23 int id(const Edge&) const { return 0; }
10.24
10.25 - /// .
10.26 + ///\e
10.27
10.28 ///\todo Should it be in the concept?
10.29 ///
10.30 int nodeNum() const { return 0; }
10.31 - /// .
10.32 + ///\e
10.33
10.34 ///\todo Should it be in the concept?
10.35 ///
10.36 @@ -405,9 +405,9 @@
10.37 {
10.38 public:
10.39
10.40 - /// .
10.41 + ///\e
10.42 NodeMap(const StaticGraph&) { }
10.43 - /// .
10.44 + ///\e
10.45 NodeMap(const StaticGraph&, T) { }
10.46
10.47 ///Copy constructor
10.48 @@ -429,9 +429,9 @@
10.49 {
10.50 public:
10.51
10.52 - /// .
10.53 + ///\e
10.54 EdgeMap(const StaticGraph&) { }
10.55 - /// .
10.56 + ///\e
10.57 EdgeMap(const StaticGraph&, T) { }
10.58
10.59 ///Copy constructor
11.1 --- a/src/hugo/skeletons/sym_graph.h Mon Sep 27 18:11:27 2004 +0000
11.2 +++ b/src/hugo/skeletons/sym_graph.h Tue Sep 28 07:00:58 2004 +0000
11.3 @@ -45,7 +45,7 @@
11.4 /// Also, you will find here the full documentation of a certain graph
11.5 /// feature, the documentation of a real symmetric graph imlementation
11.6 /// like @ref SymListGraph or
11.7 - /// @ref SymSmartGraph will just refer to this structure.
11.8 + /// @ref hugo::SymSmartGraph will just refer to this structure.
11.9 class StaticSymGraph
11.10 {
11.11 public:
11.12 @@ -93,7 +93,7 @@
11.13
11.14 /// Inequality operator
11.15
11.16 - /// \sa \ref operator==(Node n)
11.17 + /// \sa operator==(Node n)
11.18 ///
11.19 bool operator!=(Node) const { return true; }
11.20
11.21 @@ -181,7 +181,7 @@
11.22 bool operator==(SymEdge) const { return true; }
11.23 /// Inequality operator
11.24
11.25 - /// \sa \ref operator==(Node n)
11.26 + /// \sa operator==(Node n)
11.27 ///
11.28 bool operator!=(SymEdge) const { return true; }
11.29 ///Comparison operator.
11.30 @@ -223,7 +223,7 @@
11.31 bool operator==(Edge) const { return true; }
11.32 /// Inequality operator
11.33
11.34 - /// \sa \ref operator==(Node n)
11.35 + /// \sa operator==(Node n)
11.36 ///
11.37 bool operator!=(Edge) const { return true; }
11.38 ///Comparison operator.
11.39 @@ -489,12 +489,12 @@
11.40 ///\todo Should each graph provide \c id?
11.41 int id(const SymEdge&) const { return 0; }
11.42
11.43 - /// .
11.44 + ///\e
11.45
11.46 ///\todo Should it be in the concept?
11.47 ///
11.48 int nodeNum() const { return 0; }
11.49 - /// .
11.50 + ///\e
11.51
11.52 ///\todo Should it be in the concept?
11.53 ///
11.54 @@ -524,9 +524,9 @@
11.55 {
11.56 public:
11.57
11.58 - /// .
11.59 + ///\e
11.60 NodeMap(const StaticSymGraph&) { }
11.61 - /// .
11.62 + ///\e
11.63 NodeMap(const StaticSymGraph&, T) { }
11.64
11.65 ///Copy constructor
11.66 @@ -548,9 +548,9 @@
11.67 {
11.68 public:
11.69
11.70 - /// .
11.71 + ///\e
11.72 EdgeMap(const StaticSymGraph&) { }
11.73 - /// .
11.74 + ///\e
11.75 EdgeMap(const StaticSymGraph&, T) { }
11.76
11.77 ///Copy constructor
11.78 @@ -572,9 +572,9 @@
11.79 {
11.80 public:
11.81
11.82 - /// .
11.83 + ///\e
11.84 SymEdgeMap(const StaticSymGraph&) { }
11.85 - /// .
11.86 + ///\e
11.87 SymEdgeMap(const StaticSymGraph&, T) { }
11.88
11.89 ///Copy constructor