lemon-0.x: comparison lemon/min

equal deleted inserted replaced

-:cf1551c720fd
+:4272689413a7
 /* -*- C++ -*-
-* lemon/minimum_cut.h - Part of LEMON, a generic C++ optimization library
+* lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */
-#ifndef LEMON_MINIMUM_CUT_H
+#ifndef LEMON_MIN_CUT_H
-#define LEMON_MINIMUM_CUT_H
+#define LEMON_MIN_CUT_H
 /// \ingroup topology
 /// \file
-/// \brief Maximum cardinality search and minimum cut in undirected graphs.
+/// \brief Maximum cardinality search and min cut in undirected graphs.
 #include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
 #include <lemon/linear_heap.h>
 #include <functional>
 namespace lemon {
-namespace _minimum_cut_bits {
+namespace _min_cut_bits {
 template <typename CapacityMap>
 struct HeapSelector {
 template <typename Key, typename Value, typename Ref>
 struct Selector {
 /// the \ref BinHeap, but it is specialized when the
 /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
 /// to LinearHeap.
 ///
 /// \sa MaxCardinalitySearch
-typedef typename _minimum_cut_bits
+typedef typename _min_cut_bits
 ::HeapSelector<CapacityMap>
 ::template Selector<typename Graph::Node, Value, HeapCrossRef>
 ::Heap Heap;
 /// \brief Instantiates a Heap.
 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
 ///@}
 };
-/// \brief Default traits class of MinimumCut class.
+/// \brief Default traits class of MinCut class.
 ///
-/// Default traits class of MinimumCut class.
+/// Default traits class of MinCut class.
 /// \param Graph Graph type.
 /// \param CapacityMap Type of length map.
 template <typename _Graph, typename _CapacityMap>
-struct MinimumCutDefaultTraits {
+struct MinCutDefaultTraits {
 /// \brief The type of the capacity of the edges.
 typedef typename _CapacityMap::Value Value;
 /// The graph type the algorithm runs on.
 typedef _Graph Graph;
-/// The WorkGraph type which is an EraseableGraph
+/// The AuxGraph type which is an EraseableGraph
-typedef ListUGraph WorkGraph;
+typedef ListUGraph AuxGraph;
-/// \brief Instantiates a WorkGraph.
+/// \brief Instantiates a AuxGraph.
 ///
-/// This function instantiates a \ref WorkGraph.
+/// This function instantiates a \ref AuxGraph.
-static WorkGraph *createWorkGraph() {
+static AuxGraph *createAuxGraph() {
-return new WorkGraph();
+return new AuxGraph();
 }
 /// \brief The type of the map that stores the edge capacities.
 ///
 /// The type of the map that stores the edge capacities.
 #endif
 {
 throw UninitializedParameter();
 }
-/// \brief The WorkCapacityMap type
+/// \brief The AuxCapacityMap type
 ///
-/// The type of the map that stores the working edge capacities.
+/// The type of the map that stores the auxing edge capacities.
-typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
+typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
-/// \brief Instantiates a WorkCapacityMap.
+/// \brief Instantiates a AuxCapacityMap.
 ///
-/// This function instantiates a \ref WorkCapacityMap.
+/// This function instantiates a \ref AuxCapacityMap.
-static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
+static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
-return new WorkCapacityMap(graph);
+return new AuxCapacityMap(graph);
 }
 /// \brief The cross reference type used by heap.
 ///
 /// The cross reference type used by heap.
 /// Usually it is \c Graph::NodeMap<int>.
-typedef WorkGraph::NodeMap<int> HeapCrossRef;
+typedef AuxGraph::NodeMap<int> HeapCrossRef;
 /// \brief Instantiates a HeapCrossRef.
 ///
 /// This function instantiates a \ref HeapCrossRef.
 /// \param graph is the graph, to which we would like to define the
 /// HeapCrossRef.
-static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
+static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
 return new HeapCrossRef(graph);
 }
-/// \brief The heap type used by MinimumCut algorithm.
+/// \brief The heap type used by MinCut algorithm.
 ///
-/// The heap type used by MinimumCut algorithm. It should
+/// The heap type used by MinCut algorithm. It should
 /// maximalize the priorities and the heap's key type is
-/// the work graph's node.
+/// the aux graph's node.
 ///
 /// \sa BinHeap
-/// \sa MinimumCut
+/// \sa MinCut
-typedef typename _minimum_cut_bits
+typedef typename _min_cut_bits
 ::HeapSelector<CapacityMap>
-::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
+::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
 ::Heap Heap;
 /// \brief Instantiates a Heap.
 ///
 /// This function instantiates a \ref Heap.
 /// \param crossref The cross reference of the heap.
 static Heap *createHeap(HeapCrossRef& crossref) {
 return new Heap(crossref);
 }
-/// \brief Map from the WorkGraph's node type to the Graph's node type.
+/// \brief Map from the AuxGraph's node type to the Graph's node type.
 ///
-/// Map from the WorkGraph's node type to the Graph's node type.
+/// Map from the AuxGraph's node type to the Graph's node type.
-typedef typename WorkGraph
+typedef typename AuxGraph
 ::template NodeMap<typename Graph::Node> NodeRefMap;
 /// \brief Instantiates a NodeRefMap.
 ///
 /// This function instantiates a \ref NodeRefMap.
-static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
+static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
 return new NodeRefMap(graph);
 }
 /// \brief Map from the Graph's node type to the Graph's node type.
 ///
 }
 };
-namespace _minimum_cut_bits {
+namespace _min_cut_bits {
 template <typename _Key>
 class LastTwoMap {
 public:
 typedef _Key Key;
 typedef bool Value;
 };
 }
 /// \ingroup topology
 ///
-/// \brief Calculates the minimum cut in an undirected graph.
+/// \brief Calculates the min cut in an undirected graph.
 ///
-/// Calculates the minimum cut in an undirected graph.
+/// Calculates the min cut in an undirected graph.
 /// The algorithm separates the graph's nodes to two partitions with the
-/// minimum sum of edge capacities between the two partitions. The
+/// min sum of edge capacities between the two partitions. The
-/// algorithm can be used to test the network reliability specifically
+/// algorithm can be used to test the netaux reliability specifically
-/// to test how many links have to be destroyed in the network to split it
+/// to test how many links have to be destroyed in the netaux to split it
-/// at least two distinict subnetwork.
+/// at least two distinict subnetaux.
 ///
 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
 /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
 /// map is used then it uses LinearHeap which results O(n*e) time complexity.
 #ifdef DOXYGEN
 template <typename _Graph, typename _CapacityMap, typename _Traits>
 #else
 template <typename _Graph = ListUGraph,
 	    typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
-	    typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
+	    typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
 #endif
-class MinimumCut {
+class MinCut {
 public:
 /// \brief \ref Exception for uninitialized parameters.
 ///
 /// This error represents problems in the initialization
 /// of the parameters of the algorithms.
 class UninitializedParameter : public lemon::UninitializedParameter {
 public:
 virtual const char* exceptionName() const {
-	return "lemon::MinimumCut::UninitializedParameter";
+	return "lemon::MinCut::UninitializedParameter";
 }
 };
 private:
 /// The type of the capacity of the edges.
 typedef typename Traits::CapacityMap::Value Value;
 /// The type of the map that stores the edge capacities.
 typedef typename Traits::CapacityMap CapacityMap;
-/// The type of the work graph
+/// The type of the aux graph
-typedef typename Traits::WorkGraph WorkGraph;
+typedef typename Traits::AuxGraph AuxGraph;
-/// The type of the work capacity map
+/// The type of the aux capacity map
-typedef typename Traits::WorkCapacityMap WorkCapacityMap;
+typedef typename Traits::AuxCapacityMap AuxCapacityMap;
 /// The cross reference type used for the current heap.
 typedef typename Traits::HeapCrossRef HeapCrossRef;
 /// The heap type used by the max cardinality algorithm.
 typedef typename Traits::Heap Heap;
-/// The node refrefernces between the original and work graph type.
+/// The node refrefernces between the original and aux graph type.
 typedef typename Traits::NodeRefMap NodeRefMap;
 /// The list node refrefernces in the original graph type.
 typedef typename Traits::ListRefMap ListRefMap;
 public:
 /// the capacity type to constMap<UEdge, int, 1>()
 ///
 /// \ref named-templ-param "Named parameter" for setting
 /// the capacity type to constMap<UEdge, int, 1>()
 struct DefNeutralCapacity
-: public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
+: public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
-typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
+typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
 };
 template <class H, class CR>
 struct DefHeapTraits : public Traits {
 typedef CR HeapCrossRef;
 typedef H Heap;
-static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
+static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
 	throw UninitializedParameter();
 }
 static Heap *createHeap(HeapCrossRef &) {
 	throw UninitializedParameter();
 }
 ///
 /// \ref named-templ-param "Named parameter" for setting heap and cross
 /// reference type
 template <class H, class CR = typename Graph::template NodeMap<int> >
 struct DefHeap
-: public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
+: public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
-typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
+typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
 };
 template <class H, class CR>
 struct DefStandardHeapTraits : public Traits {
 typedef CR HeapCrossRef;
 typedef H Heap;
-static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
+static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
 	return new HeapCrossRef(graph);
 }
 static Heap *createHeap(HeapCrossRef &crossref) {
 	return new Heap(crossref);
 }
 /// reference type. It can allocate the heap and the cross reference
 /// object if the cross reference's constructor waits for the graph as
 /// parameter and the heap's constructor waits for the cross reference.
 template <class H, class CR = typename Graph::template NodeMap<int> >
 struct DefStandardHeap
-: public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
+: public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
-typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
+typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
 Create;
 };
 ///@}
 const CapacityMap *_capacity;
 /// \brief Indicates if \ref _capacity is locally allocated
 /// (\c true) or not.
 bool local_capacity;
-/// Pointer to the work graph.
+/// Pointer to the aux graph.
-WorkGraph *_work_graph;
+AuxGraph *_aux_graph;
-/// \brief Indicates if \ref _work_graph is locally allocated
+/// \brief Indicates if \ref _aux_graph is locally allocated
 /// (\c true) or not.
-bool local_work_graph;
+bool local_aux_graph;
-/// Pointer to the work capacity map
+/// Pointer to the aux capacity map
-WorkCapacityMap *_work_capacity;
+AuxCapacityMap *_aux_capacity;
-/// \brief Indicates if \ref _work_capacity is locally allocated
+/// \brief Indicates if \ref _aux_capacity is locally allocated
 /// (\c true) or not.
-bool local_work_capacity;
+bool local_aux_capacity;
 /// Pointer to the heap cross references.
 HeapCrossRef *_heap_cross_ref;
 /// \brief Indicates if \ref _heap_cross_ref is locally allocated
 /// (\c true) or not.
 bool local_heap_cross_ref;
 /// Pointer to the heap.
 Heap *_heap;
 /// Indicates if \ref _heap is locally allocated (\c true) or not.
 bool local_heap;
-/// The minimum cut value.
+/// The min cut value.
-Value _minimum_cut;
+Value _min_cut;
-/// The number of the nodes of the work graph.
+/// The number of the nodes of the aux graph.
 int _node_num;
 /// The first and last node of the min cut in the next list;
 typename Graph::Node _first_node, _last_node;
 /// \brief The first and last element in the list associated
-/// to the work graph node.
+/// to the aux graph node.
 NodeRefMap *_first, *_last;
 /// \brief The next node in the node lists.
 ListRefMap *_next;
 void create_structures() {
 if (!_capacity) {
 local_capacity = true;
 _capacity = Traits::createCapacityMap(*_graph);
 }
-if(!_work_graph) {
+if(!_aux_graph) {
-	local_work_graph = true;
+	local_aux_graph = true;
-	_work_graph = Traits::createWorkGraph();
+	_aux_graph = Traits::createAuxGraph();
 }
-if(!_work_capacity) {
+if(!_aux_capacity) {
-	local_work_capacity = true;
+	local_aux_capacity = true;
-	_work_capacity = Traits::createWorkCapacityMap(*_work_graph);
+	_aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
 }
-_first = Traits::createNodeRefMap(*_work_graph);
+_first = Traits::createNodeRefMap(*_aux_graph);
-_last = Traits::createNodeRefMap(*_work_graph);
+_last = Traits::createNodeRefMap(*_aux_graph);
 _next = Traits::createListRefMap(*_graph);
-typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
+typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
 for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
 _next->set(it, INVALID);
-typename WorkGraph::Node node = _work_graph->addNode();
+typename AuxGraph::Node node = _aux_graph->addNode();
 _first->set(node, it);
 _last->set(node, it);
 ref.set(it, node);
 }
 for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
 if (_graph->source(it) == _graph->target(it)) continue;
-typename WorkGraph::UEdge uedge =
+typename AuxGraph::UEdge uedge =
-_work_graph->addEdge(ref[_graph->source(it)],
+_aux_graph->addEdge(ref[_graph->source(it)],
 ref[_graph->target(it)]);
-_work_capacity->set(uedge, (*_capacity)[it]);
+_aux_capacity->set(uedge, (*_capacity)[it]);
 }
 if (!_heap_cross_ref) {
 	local_heap_cross_ref = true;
-	_heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
+	_heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
 }
 if (!_heap) {
 	local_heap = true;
 	_heap = Traits::createHeap(*_heap_cross_ref);
 }
 }
 public :
-typedef MinimumCut Create;
+typedef MinCut Create;
 /// \brief Constructor.
 ///
 ///\param graph the graph the algorithm will run on.
 ///\param capacity the capacity map used by the algorithm.
-MinimumCut(const Graph& graph, const CapacityMap& capacity)
+MinCut(const Graph& graph, const CapacityMap& capacity)
 : _graph(&graph),
 _capacity(&capacity), local_capacity(false),
-_work_graph(0), local_work_graph(false),
+_aux_graph(0), local_aux_graph(false),
-_work_capacity(0), local_work_capacity(false),
+_aux_capacity(0), local_aux_capacity(false),
 _heap_cross_ref(0), local_heap_cross_ref(false),
 _heap(0), local_heap(false),
 _first(0), _last(0), _next(0) {}
 /// \brief Constructor.
 /// defines how can we instantiate a local capacity map.
 /// If the DefNeutralCapacity used the algorithm automatically
 /// construct the capacity map.
 ///
 ///\param graph the graph the algorithm will run on.
-MinimumCut(const Graph& graph)
+MinCut(const Graph& graph)
 : _graph(&graph),
 _capacity(0), local_capacity(false),
-_work_graph(0), local_work_graph(false),
+_aux_graph(0), local_aux_graph(false),
-_work_capacity(0), local_work_capacity(false),
+_aux_capacity(0), local_aux_capacity(false),
 _heap_cross_ref(0), local_heap_cross_ref(false),
 _heap(0), local_heap(false),
 _first(0), _last(0), _next(0) {}
 /// \brief Destructor.
 ///
 /// Destructor.
-~MinimumCut() {
+~MinCut() {
 if (local_heap) delete _heap;
 if (local_heap_cross_ref) delete _heap_cross_ref;
 if (_first) delete _first;
 if (_last) delete _last;
 if (_next) delete _next;
-if (local_work_capacity) delete _work_capacity;
+if (local_aux_capacity) delete _aux_capacity;
-if (local_work_graph) delete _work_graph;
+if (local_aux_graph) delete _aux_graph;
 if (local_capacity) delete _capacity;
 }
 /// \brief Sets the heap and the cross reference used by algorithm.
 ///
 /// Sets the heap and the cross reference used by algorithm.
 /// If you don't use this function before calling \ref run(),
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated heap and cross reference, of course.
 /// \return <tt> (*this) </tt>
-MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
+MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
 {
 if (local_heap_cross_ref) {
 	delete _heap_cross_ref;
 	local_heap_cross_ref=false;
 }
 }
 _heap = &heap;
 return *this;
 }
-/// \brief Sets the work graph.
+/// \brief Sets the aux graph.
 ///
-/// Sets the work graph used by algorithm.
+/// Sets the aux graph used by algorithm.
 /// If you don't use this function before calling \ref run(),
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated graph, of course.
 /// \return <tt> (*this) </tt>
-MinimumCut &workGraph(WorkGraph& work_graph)
+MinCut &auxGraph(AuxGraph& aux_graph)
 {
-if(local_work_graph) {
+if(local_aux_graph) {
-	delete _work_graph;
+	delete _aux_graph;
-	local_work_graph=false;
+	local_aux_graph=false;
 }
-_work_graph = &work_graph;
+_aux_graph = &aux_graph;
 return *this;
 }
-/// \brief Sets the work capacity map.
+/// \brief Sets the aux capacity map.
 ///
-/// Sets the work capacity map used by algorithm.
+/// Sets the aux capacity map used by algorithm.
 /// If you don't use this function before calling \ref run(),
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated graph, of course.
 /// \return <tt> (*this) </tt>
-MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
+MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
 {
-if(local_work_capacity) {
+if(local_aux_capacity) {
-	delete _work_capacity;
+	delete _aux_capacity;
-	local_work_capacity=false;
+	local_aux_capacity=false;
 }
-_work_capacity = &work_capacity_map;
+_aux_capacity = &aux_capacity_map;
 return *this;
 }
 /// \name Execution control
 /// The simplest way to execute the algorithm is to use
 /// \brief Processes the next phase
 ///
 /// Processes the next phase in the algorithm. The function
 /// should be called countNodes(graph) - 1 times to get
-/// surely the minimum cut in the graph. The
+/// surely the min cut in the graph. The
 ///
 ///\return %True when the algorithm finished.
 bool processNextPhase() {
 if (_node_num <= 1) return true;
-using namespace _minimum_cut_bits;
+using namespace _min_cut_bits;
-typedef typename WorkGraph::Node Node;
+typedef typename AuxGraph::Node Node;
-typedef typename WorkGraph::NodeIt NodeIt;
+typedef typename AuxGraph::NodeIt NodeIt;
-typedef typename WorkGraph::UEdge UEdge;
+typedef typename AuxGraph::UEdge UEdge;
-typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
+typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
-typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
+typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
 template DefHeap<Heap, HeapCrossRef>::
 template DefCardinalityMap<NullMap<Node, Value> >::
 template DefProcessedMap<LastTwoMap<Node> >::
 Create MaxCardinalitySearch;
-MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
+MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
-for (NodeIt it(*_work_graph); it != INVALID; ++it) {
+for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
 _heap_cross_ref->set(it, Heap::PRE_HEAP);
 }
 mcs.heap(*_heap, *_heap_cross_ref);
 LastTwoMap<Node> last_two_nodes(_node_num);
 NullMap<Node, Value> cardinality;
 mcs.cardinalityMap(cardinality);
 mcs.run();
-Node new_node = _work_graph->addNode();
+Node new_node = _aux_graph->addNode();
-typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
+typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
 Node first_node = last_two_nodes[0];
 Node second_node = last_two_nodes[1];
 _next->set((*_last)[first_node], (*_first)[second_node]);
 _first->set(new_node, (*_first)[first_node]);
 _last->set(new_node, (*_last)[second_node]);
 Value current_cut = 0;
-for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
+for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
-Node node = _work_graph->runningNode(it);
+Node node = _aux_graph->runningNode(it);
-current_cut += (*_work_capacity)[it];
+current_cut += (*_aux_capacity)[it];
 if (node == second_node) continue;
 if (edges[node] == INVALID) {
-edges[node] = _work_graph->addEdge(new_node, node);
+edges[node] = _aux_graph->addEdge(new_node, node);
-(*_work_capacity)[edges[node]] = (*_work_capacity)[it];
+(*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
 } else {
-(*_work_capacity)[edges[node]] += (*_work_capacity)[it];
+(*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
 }
 }
-if (_first_node == INVALID || current_cut < _minimum_cut) {
+if (_first_node == INVALID || current_cut < _min_cut) {
 _first_node = (*_first)[first_node];
 _last_node = (*_last)[first_node];
-_minimum_cut = current_cut;
+_min_cut = current_cut;
 }
-_work_graph->erase(first_node);
+_aux_graph->erase(first_node);
-for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
+for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
-Node node = _work_graph->runningNode(it);
+Node node = _aux_graph->runningNode(it);
 if (edges[node] == INVALID) {
-edges[node] = _work_graph->addEdge(new_node, node);
+edges[node] = _aux_graph->addEdge(new_node, node);
-(*_work_capacity)[edges[node]] = (*_work_capacity)[it];
+(*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
 } else {
-(*_work_capacity)[edges[node]] += (*_work_capacity)[it];
+(*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
 }
 }
-_work_graph->erase(second_node);
+_aux_graph->erase(second_node);
 --_node_num;
 return _node_num == 1;
 }
 void start() {
 while (!processNextPhase());
 }
-/// \brief Runs %MinimumCut algorithm.
+/// \brief Runs %MinCut algorithm.
 ///
-/// This method runs the %Minimum cut algorithm
+/// This method runs the %Min cut algorithm
 ///
 /// \note mc.run(s) is just a shortcut of the following code.
 ///\code
 ///  mc.init();
 ///  mc.start();
 }
 ///@}
 /// \name Query Functions
-/// The result of the %MinimumCut algorithm can be obtained using these
+/// The result of the %MinCut algorithm can be obtained using these
 /// functions.\n
 /// Before the use of these functions,
 /// either run() or start() must be called.
 ///@{
-/// \brief Returns the minimum cut value.
+/// \brief Returns the min cut value.
 ///
-/// Returns the minimum cut value if the algorithm finished.
+/// Returns the min cut value if the algorithm finished.
 /// After the first processNextPhase() it is a value of a
 /// valid cut in the graph.
 Value minCut() const {
-return _minimum_cut;
+return _min_cut;
 }
-/// \brief Returns a minimum cut in a NodeMap.
+/// \brief Returns a min cut in a NodeMap.
 ///
 /// It sets the nodes of one of the two partitions to true in
 /// the given BoolNodeMap. The map contains a valid cut if the
 /// map have been set false previously.
 template <typename NodeMap>
 }
 nodeMap.set(_last_node, true);
 return minCut();
 }
-/// \brief Returns a minimum cut in a NodeMap.
+/// \brief Returns a min cut in a NodeMap.
 ///
 /// It sets the nodes of one of the two partitions to true and
 /// the other partition to false. The function first set all of the
 /// nodes to false and after it call the quickMinCut() member.
 template <typename NodeMap>
 }
 quickMinCut(nodeMap);
 return minCut();
 }
-/// \brief Returns a minimum cut in an EdgeMap.
+/// \brief Returns a min cut in an EdgeMap.
 ///
-/// If an undirected edge is in a minimum cut then it will be
+/// If an undirected edge is in a min cut then it will be
 /// set to true and the others will be set to false in the given map.
 template <typename EdgeMap>
 Value cutEdges(EdgeMap& edgeMap) const {
 typename Graph::template NodeMap<bool> cut(*_graph, false);
 quickMinCut(cut);

changeset 1977	8ef02f0c4245
parent 1973	30c97275f337
child 1993	2115143eceea