Changeset 1968:78e6e2d1fd96 in lemon-0.x for lemon/minimum_cut.h

Timestamp:

02/14/06 11:41:16 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2547

Message:

Name modification

File:

• lemon/minimum_cut.h (moved) (moved from lemon/minimal_cut.h) (28 diffs)

lemon/minimum_cut.h

@@ -1 +1 @@
 /* -*- 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
@@ -15 +15 @@
  */
 
-#ifndef LEMON_MINIMAL_CUT_H
-#define LEMON_MINIMAL_CUT_H
+#ifndef LEMON_MINIMUM_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>
@@ -35 +35 @@
 namespace lemon {
 
-  namespace _minimal_cut_bits {
+  namespace _minimum_cut_bits {
 
     template <typename CapacityMap>
@@ -98 +98 @@
     ///
     /// \sa MaxCardinalitySearch
-    typedef typename _minimal_cut_bits
+    typedef typename _minimum_cut_bits
     ::HeapSelector<CapacityMap>
     ::template Selector<typename Graph::Node, Value, HeapCrossRef>
@@ -689 +689 @@
   };
 
-  /// \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;
@@ -757 +757 @@
     }
     
-    /// \brief The heap type used by MinimalCut algorithm.
-    ///
-    /// The heap type used by MinimalCut algorithm. It should
+    /// \brief The heap type used by MinimumCut algorithm.
+    ///
+    /// 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
-    typedef typename _minimal_cut_bits
+    /// \sa MinimumCut
+    typedef typename _minimum_cut_bits
     ::HeapSelector<CapacityMap>
     ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
@@ -807 +807 @@
   };
 
-  namespace _minimal_cut_bits {
+  namespace _minimum_cut_bits {
     template <typename _Key>
     class LastTwoMap {
@@ -831 +831 @@
   /// \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 
@@ -848 +848 @@
   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.
@@ -859 +859 @@
     public:
       virtual const char* exceptionName() const {
-        return "lemon::MinimalCut::UninitializedParameter";
+        return "lemon::MinimumCut::UninitializedParameter";
       }
     };
@@ -905 +905 @@
     /// the capacity type to constMap<UEdge, int, 1>()
     struct DefNeutralCapacity
-      : public MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 
-      typedef MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
+      : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 
+      typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
     };
 
@@ -928 +928 @@
     template <class H, class CR = typename Graph::template NodeMap<int> >
     struct DefHeap
-      : public MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 
-      typedef MinimalCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
+      : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 
+      typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
     };
 
@@ -953 +953 @@
     template <class H, class CR = typename Graph::template NodeMap<int> >
     struct DefStandardHeap
-      : public MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 
-      typedef MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 
+      : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 
+      typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 
       Create;
     };
@@ -990 +990 @@
     bool local_heap;
 
-    /// The minimal cut value.
-    Value _minimal_cut;
+    /// The minimum cut value.
+    Value _minimum_cut;
     /// The number of the nodes of the work graph.
     int _node_num;
@@ -1053 +1053 @@
   public :
 
-    typedef MinimalCut Create;
+    typedef MinimumCut Create;
 
 
@@ -1060 +1060 @@
     ///\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),
@@ -1077 +1077 @@
     ///
     ///\param graph the graph the algorithm will run on.
-    MinimalCut(const Graph& graph) 
+    MinimumCut(const Graph& graph) 
       : _graph(&graph), 
         _capacity(0), local_capacity(false),
@@ -1089 +1089 @@
     ///
     /// Destructor.
-    ~MinimalCut() {
+    ~MinimumCut() {
       if (local_heap) delete _heap;
       if (local_heap_cross_ref) delete _heap_cross_ref;
@@ -1107 +1107 @@
     /// 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) {
@@ -1129 +1129 @@
     /// automatically allocated graph, of course.
     /// \return <tt> (*this) </tt>
-    MinimalCut &workGraph(WorkGraph& work_graph)
+    MinimumCut &workGraph(WorkGraph& work_graph)
     {
       if(local_work_graph) {
@@ -1146 +1146 @@
     /// 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) {
@@ -1179 +1179 @@
     /// 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;
@@ -1235 +1235 @@
       }
 
-      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;
       }
 
@@ -1268 +1268 @@
 
 
-    /// \brief Runs %MinimalCut algorithm.
-    ///
-    /// This method runs the %Minimal cut algorithm
+    /// \brief Runs %MinimumCut algorithm.
+    ///
+    /// This method runs the %Minimum cut algorithm
     ///
     /// \note mc.run(s) is just a shortcut of the following code.
@@ -1285 +1285 @@
 
     /// \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,
@@ -1292 +1292 @@
     ///@{
 
-    /// \brief Returns the minimal cut value.
-    ///
-    /// Returns the minimal cut value if the algorithm finished.
+    /// \brief Returns the minimum cut value.
+    ///
+    /// 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;
-    }
-
-    /// \brief Returns a minimal cut in a NodeMap.
+      return _minimum_cut;
+    }
+
+    /// \brief Returns a minimum cut in a NodeMap.
     ///
     /// It sets the nodes of one of the two partitions to true in
@@ -1316 +1316 @@
     }
 
-    /// \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
@@ -1330 +1330 @@
     }
 
-    /// \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