1.1 --- a/lemon/suurballe.h Wed Mar 17 12:35:52 2010 +0100
1.2 +++ b/lemon/suurballe.h Sat Mar 06 14:35:12 2010 +0000
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -65,7 +65,7 @@
1.13 /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.14 /// and it must have an \c addBack() function.
1.15 typedef lemon::Path<Digraph> Path;
1.16 -
1.17 +
1.18 /// The cross reference type used for the heap.
1.19 typedef typename GR::template NodeMap<int> HeapCrossRef;
1.20
1.21 @@ -158,7 +158,7 @@
1.22 PredMap &_pred;
1.23 Node _s;
1.24 Node _t;
1.25 -
1.26 +
1.27 PotentialMap _dist;
1.28 std::vector<Node> _proc_nodes;
1.29
1.30 @@ -167,9 +167,9 @@
1.31 // Constructor
1.32 ResidualDijkstra(Suurballe &srb) :
1.33 _graph(srb._graph), _length(srb._length),
1.34 - _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred),
1.35 + _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred),
1.36 _s(srb._s), _t(srb._t), _dist(_graph) {}
1.37 -
1.38 +
1.39 // Run the algorithm and return true if a path is found
1.40 // from the source node to the target node.
1.41 bool run(int cnt) {
1.42 @@ -177,7 +177,7 @@
1.43 }
1.44
1.45 private:
1.46 -
1.47 +
1.48 // Execute the algorithm for the first time (the flow and potential
1.49 // functions have to be identically zero).
1.50 bool startFirst() {
1.51 @@ -348,7 +348,7 @@
1.52 : public Suurballe<GR, LEN, SetPathTraits<T> > {
1.53 typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
1.54 };
1.55 -
1.56 +
1.57 template <typename H, typename CR>
1.58 struct SetHeapTraits : public Traits {
1.59 typedef H Heap;
1.60 @@ -359,7 +359,7 @@
1.61 /// \c Heap and \c HeapCrossRef types.
1.62 ///
1.63 /// \ref named-templ-param "Named parameter" for setting \c Heap
1.64 - /// and \c HeapCrossRef types with automatic allocation.
1.65 + /// and \c HeapCrossRef types with automatic allocation.
1.66 /// They will be used for internal Dijkstra computations.
1.67 /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
1.68 /// concept and its priority type must be \c Length.
1.69 @@ -397,7 +397,7 @@
1.70
1.71 // The pred arc map
1.72 PredMap _pred;
1.73 -
1.74 +
1.75 // Data for full init
1.76 PotentialMap *_init_dist;
1.77 PredMap *_init_pred;
1.78 @@ -555,7 +555,7 @@
1.79 ::Create dijk(_graph, _length);
1.80 dijk.distMap(*_init_dist).predMap(*_init_pred);
1.81 dijk.run(s);
1.82 -
1.83 +
1.84 _full_init = true;
1.85 }
1.86
1.87 @@ -599,7 +599,7 @@
1.88 int findFlow(const Node& t, int k = 2) {
1.89 _t = t;
1.90 ResidualDijkstra dijkstra(*this);
1.91 -
1.92 +
1.93 // Initialization
1.94 for (ArcIt e(_graph); e != INVALID; ++e) {
1.95 (*_flow)[e] = 0;
1.96 @@ -613,7 +613,7 @@
1.97 while ((e = (*_init_pred)[u]) != INVALID) {
1.98 (*_flow)[e] = 1;
1.99 u = _graph.source(e);
1.100 - }
1.101 + }
1.102 _path_num = 1;
1.103 } else {
1.104 for (NodeIt n(_graph); n != INVALID; ++n) {