lemon-0.x: comparison lemon/minimum

equal deleted inserted replaced

-:532e4523e83b
+:1f51a697ab2b
 /* -*- C++ -*-
-* lemon/minimal_cut.h - Part of LEMON, a generic C++ optimization library
+* lemon/minimum_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_MINIMAL_CUT_H
+#ifndef LEMON_MINIMUM_CUT_H
-#define LEMON_MINIMAL_CUT_H
+#define LEMON_MINIMUM_CUT_H
 /// \ingroup topology
 /// \file
-/// \brief Maximum cardinality search and minimal cut in undirected graphs.
+/// \brief Maximum cardinality search and minimum cut in undirected graphs.
 #include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
 #include <lemon/linear_heap.h>
 #include <functional>
 namespace lemon {
-namespace _minimal_cut_bits {
+namespace _minimum_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 _minimal_cut_bits
+typedef typename _minimum_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 MinimalCut class.
+/// \brief Default traits class of MinimumCut class.
 ///
-/// Default traits class of MinimalCut class.
+/// Default traits class of MinimumCut class.
 /// \param Graph Graph type.
 /// \param CapacityMap Type of length map.
 template <typename _Graph, typename _CapacityMap>
-struct MinimalCutDefaultTraits {
+struct MinimumCutDefaultTraits {
 /// \brief The type of the capacity of the edges.
 typedef typename _CapacityMap::Value Value;
 /// The graph type the algorithm runs on.
 typedef _Graph Graph;
 /// HeapCrossRef.
 static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
 return new HeapCrossRef(graph);
 }
-/// \brief The heap type used by MinimalCut algorithm.
+/// \brief The heap type used by MinimumCut algorithm.
 ///
-/// The heap type used by MinimalCut algorithm. It should
+/// The heap type used by MinimumCut algorithm. It should
 /// maximalize the priorities and the heap's key type is
 /// the work graph's node.
 ///
 /// \sa BinHeap
-/// \sa MinimalCut
+/// \sa MinimumCut
-typedef typename _minimal_cut_bits
+typedef typename _minimum_cut_bits
 ::HeapSelector<CapacityMap>
 ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
 ::Heap Heap;
 /// \brief Instantiates a Heap.
 }
 };
-namespace _minimal_cut_bits {
+namespace _minimum_cut_bits {
 template <typename _Key>
 class LastTwoMap {
 public:
 typedef _Key Key;
 typedef bool Value;
 };
 }
 /// \ingroup topology
 ///
-/// \brief Calculates the minimal cut in an undirected graph.
+/// \brief Calculates the minimum cut in an undirected graph.
 ///
-/// Calculates the minimal cut in an undirected graph.
+/// Calculates the minimum cut in an undirected graph.
 /// The algorithm separates the graph's nodes to two partitions with the
-/// minimal sum of edge capacities between the two partitions. The
+/// minimum sum of edge capacities between the two partitions. The
 /// algorithm can be used to test the network reliability specifically
 /// to test how many links have to be destroyed in the network to split it
 /// at least two distinict subnetwork.
 ///
 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
 #ifdef DOXYGEN
 template <typename _Graph, typename _CapacityMap, typename _Traits>
 #else
 template <typename _Graph = ListUGraph,
 	    typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
-	    typename _Traits = MinimalCutDefaultTraits<_Graph, _CapacityMap> >
+	    typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
 #endif
-class MinimalCut {
+class MinimumCut {
 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::MinimalCut::UninitializedParameter";
+	return "lemon::MinimumCut::UninitializedParameter";
 }
 };
 private:
 /// 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 MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
+: public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
-typedef MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
+typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
 };
 template <class H, class CR>
 struct DefHeapTraits : public Traits {
 ///
 /// \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 MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
+: public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
-typedef MinimalCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
+typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
 };
 template <class H, class CR>
 struct DefStandardHeapTraits : public Traits {
 typedef CR HeapCrossRef;
 /// 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 MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
+: public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
-typedef MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
+typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
 Create;
 };
 ///@}
 /// Pointer to the heap.
 Heap *_heap;
 /// Indicates if \ref _heap is locally allocated (\c true) or not.
 bool local_heap;
-/// The minimal cut value.
+/// The minimum cut value.
-Value _minimal_cut;
+Value _minimum_cut;
 /// The number of the nodes of the work graph.
 int _node_num;
 /// The first and last node of the min cut in the next list;
 typename Graph::Node _first_node, _last_node;
 }
 }
 public :
-typedef MinimalCut Create;
+typedef MinimumCut Create;
 /// \brief Constructor.
 ///
 ///\param graph the graph the algorithm will run on.
 ///\param capacity the capacity map used by the algorithm.
-MinimalCut(const Graph& graph, const CapacityMap& capacity)
+MinimumCut(const Graph& graph, const CapacityMap& capacity)
 : _graph(&graph),
 _capacity(&capacity), local_capacity(false),
 _work_graph(0), local_work_graph(false),
 _work_capacity(0), local_work_capacity(false),
 _heap_cross_ref(0), local_heap_cross_ref(false),
 /// 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.
-MinimalCut(const Graph& graph)
+MinimumCut(const Graph& graph)
 : _graph(&graph),
 _capacity(0), local_capacity(false),
 _work_graph(0), local_work_graph(false),
 _work_capacity(0), local_work_capacity(false),
 _heap_cross_ref(0), local_heap_cross_ref(false),
 _first(0), _last(0), _next(0) {}
 /// \brief Destructor.
 ///
 /// Destructor.
-~MinimalCut() {
+~MinimumCut() {
 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;
 /// 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>
-MinimalCut &heap(Heap& heap, HeapCrossRef &crossRef)
+MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
 {
 if (local_heap_cross_ref) {
 	delete _heap_cross_ref;
 	local_heap_cross_ref=false;
 }
 /// Sets the work 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>
-MinimalCut &workGraph(WorkGraph& work_graph)
+MinimumCut &workGraph(WorkGraph& work_graph)
 {
 if(local_work_graph) {
 	delete _work_graph;
 	local_work_graph=false;
 }
 /// Sets the work 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>
-MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
+MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
 {
 if(local_work_capacity) {
 	delete _work_capacity;
 	local_work_capacity=false;
 }
 /// \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 minimal cut in the graph. The
+/// surely the minimum cut in the graph. The
 ///
 ///\return %True when the algorithm finished.
 bool processNextPhase() {
 if (_node_num <= 1) return true;
-using namespace _minimal_cut_bits;
+using namespace _minimum_cut_bits;
 typedef typename WorkGraph::Node Node;
 typedef typename WorkGraph::NodeIt NodeIt;
 typedef typename WorkGraph::UEdge UEdge;
 typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
 } else {
 (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
 }
 }
-if (_first_node == INVALID || current_cut < _minimal_cut) {
+if (_first_node == INVALID || current_cut < _minimum_cut) {
 _first_node = (*_first)[first_node];
 _last_node = (*_last)[first_node];
-_minimal_cut = current_cut;
+_minimum_cut = current_cut;
 }
 _work_graph->erase(first_node);
 for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
 void start() {
 while (!processNextPhase());
 }
-/// \brief Runs %MinimalCut algorithm.
+/// \brief Runs %MinimumCut algorithm.
 ///
-/// This method runs the %Minimal cut algorithm
+/// This method runs the %Minimum 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 %MinimalCut algorithm can be obtained using these
+/// The result of the %MinimumCut algorithm can be obtained using these
 /// functions.\n
 /// Before the use of these functions,
 /// either run() or start() must be called.
 ///@{
-/// \brief Returns the minimal cut value.
+/// \brief Returns the minimum cut value.
 ///
-/// Returns the minimal cut value if the algorithm finished.
+/// Returns the minimum 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 _minimal_cut;
+return _minimum_cut;
 }
-/// \brief Returns a minimal cut in a NodeMap.
+/// \brief Returns a minimum 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 setted false previously.
 template <typename NodeMap>
 }
 nodeMap.set(_last_node, true);
 return minCut();
 }
-/// \brief Returns a minimal cut in a NodeMap.
+/// \brief Returns a minimum 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 minimal cut in an EdgeMap.
+/// \brief Returns a minimum cut in an EdgeMap.
 ///
 /// If an undirected edge is cut edge then it will be
 /// setted to true and the others will be setted to false in the given map.
 template <typename EdgeMap>
 Value cutEdges(EdgeMap& edgeMap) const {

changeset 1968	78e6e2d1fd96
parent 1967	5d81ba873b90
child 1973	30c97275f337