COIN-OR::LEMON - Graph Library

Changeset 1975:64db671eda28 in lemon-0.x for lemon


Ignore:
Timestamp:
02/20/06 10:40:07 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2560
Message:

Second renaming of min cut

Minimum => Min
Work => Aux

Location:
lemon
Files:
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r1971 r1975  
    6262        max_matching.h \
    6363        min_cost_flow.h \
    64         minimum_cut.h \
     64        min_cut.h \
    6565        suurballe.h \
    6666        preflow.h \
  • lemon/min_cut.h

    r1973 r1975  
    11/* -*- C++ -*-
    2  * lemon/minimum_cut.h - Part of LEMON, a generic C++ optimization library
     2 * lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    1515 */
    1616
    17 #ifndef LEMON_MINIMUM_CUT_H
    18 #define LEMON_MINIMUM_CUT_H
     17#ifndef LEMON_MIN_CUT_H
     18#define LEMON_MIN_CUT_H
    1919
    2020
    2121/// \ingroup topology
    2222/// \file
    23 /// \brief Maximum cardinality search and minimum cut in undirected graphs.
     23/// \brief Maximum cardinality search and min cut in undirected graphs.
    2424
    2525#include <lemon/list_graph.h>
     
    3535namespace lemon {
    3636
    37   namespace _minimum_cut_bits {
     37  namespace _min_cut_bits {
    3838
    3939    template <typename CapacityMap>
     
    9898    ///
    9999    /// \sa MaxCardinalitySearch
    100     typedef typename _minimum_cut_bits
     100    typedef typename _min_cut_bits
    101101    ::HeapSelector<CapacityMap>
    102102    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
     
    689689  };
    690690
    691   /// \brief Default traits class of MinimumCut class.
     691  /// \brief Default traits class of MinCut class.
    692692  ///
    693   /// Default traits class of MinimumCut class.
     693  /// Default traits class of MinCut class.
    694694  /// \param Graph Graph type.
    695695  /// \param CapacityMap Type of length map.
    696696  template <typename _Graph, typename _CapacityMap>
    697   struct MinimumCutDefaultTraits {
     697  struct MinCutDefaultTraits {
    698698    /// \brief The type of the capacity of the edges.
    699699    typedef typename _CapacityMap::Value Value;
     
    702702    typedef _Graph Graph;
    703703
    704     /// The WorkGraph type which is an EraseableGraph
    705     typedef ListUGraph WorkGraph;
    706 
    707     /// \brief Instantiates a WorkGraph.
    708     ///
    709     /// This function instantiates a \ref WorkGraph.
    710     static WorkGraph *createWorkGraph() {
    711       return new WorkGraph();
     704    /// The AuxGraph type which is an EraseableGraph
     705    typedef ListUGraph AuxGraph;
     706
     707    /// \brief Instantiates a AuxGraph.
     708    ///
     709    /// This function instantiates a \ref AuxGraph.
     710    static AuxGraph *createAuxGraph() {
     711      return new AuxGraph();
    712712    }
    713713
     
    730730    }
    731731
    732     /// \brief The WorkCapacityMap type
    733     ///
    734     /// The type of the map that stores the working edge capacities.
    735     typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
    736 
    737     /// \brief Instantiates a WorkCapacityMap.
    738     ///
    739     /// This function instantiates a \ref WorkCapacityMap.
    740     static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
    741       return new WorkCapacityMap(graph);
     732    /// \brief The AuxCapacityMap type
     733    ///
     734    /// The type of the map that stores the auxing edge capacities.
     735    typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
     736
     737    /// \brief Instantiates a AuxCapacityMap.
     738    ///
     739    /// This function instantiates a \ref AuxCapacityMap.
     740    static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
     741      return new AuxCapacityMap(graph);
    742742    }
    743743
     
    746746    /// The cross reference type used by heap.
    747747    /// Usually it is \c Graph::NodeMap<int>.
    748     typedef WorkGraph::NodeMap<int> HeapCrossRef;
     748    typedef AuxGraph::NodeMap<int> HeapCrossRef;
    749749
    750750    /// \brief Instantiates a HeapCrossRef.
     
    753753    /// \param graph is the graph, to which we would like to define the
    754754    /// HeapCrossRef.
    755     static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
     755    static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
    756756      return new HeapCrossRef(graph);
    757757    }
    758758   
    759     /// \brief The heap type used by MinimumCut algorithm.
    760     ///
    761     /// The heap type used by MinimumCut algorithm. It should
     759    /// \brief The heap type used by MinCut algorithm.
     760    ///
     761    /// The heap type used by MinCut algorithm. It should
    762762    /// maximalize the priorities and the heap's key type is
    763     /// the work graph's node.
     763    /// the aux graph's node.
    764764    ///
    765765    /// \sa BinHeap
    766     /// \sa MinimumCut
    767     typedef typename _minimum_cut_bits
     766    /// \sa MinCut
     767    typedef typename _min_cut_bits
    768768    ::HeapSelector<CapacityMap>
    769     ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
     769    ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
    770770    ::Heap Heap;
    771771   
     
    778778    }
    779779
    780     /// \brief Map from the WorkGraph's node type to the Graph's node type.
    781     ///
    782     /// Map from the WorkGraph's node type to the Graph's node type.
    783     typedef typename WorkGraph
     780    /// \brief Map from the AuxGraph's node type to the Graph's node type.
     781    ///
     782    /// Map from the AuxGraph's node type to the Graph's node type.
     783    typedef typename AuxGraph
    784784    ::template NodeMap<typename Graph::Node> NodeRefMap;
    785785
     
    787787    ///
    788788    /// This function instantiates a \ref NodeRefMap.
    789     static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
     789    static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
    790790      return new NodeRefMap(graph);
    791791    }
     
    807807  };
    808808
    809   namespace _minimum_cut_bits {
     809  namespace _min_cut_bits {
    810810    template <typename _Key>
    811811    class LastTwoMap {
     
    831831  /// \ingroup topology
    832832  ///
    833   /// \brief Calculates the minimum cut in an undirected graph.
     833  /// \brief Calculates the min cut in an undirected graph.
    834834  ///
    835   /// Calculates the minimum cut in an undirected graph.
     835  /// Calculates the min cut in an undirected graph.
    836836  /// The algorithm separates the graph's nodes to two partitions with the
    837   /// minimum sum of edge capacities between the two partitions. The
    838   /// algorithm can be used to test the network reliability specifically
    839   /// to test how many links have to be destroyed in the network to split it
    840   /// at least two distinict subnetwork.
     837  /// min sum of edge capacities between the two partitions. The
     838  /// algorithm can be used to test the netaux reliability specifically
     839  /// to test how many links have to be destroyed in the netaux to split it
     840  /// at least two distinict subnetaux.
    841841  ///
    842842  /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
     
    848848  template <typename _Graph = ListUGraph,
    849849            typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
    850             typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
     850            typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
    851851#endif
    852   class MinimumCut {
     852  class MinCut {
    853853  public:
    854854    /// \brief \ref Exception for uninitialized parameters.
     
    859859    public:
    860860      virtual const char* exceptionName() const {
    861         return "lemon::MinimumCut::UninitializedParameter";
     861        return "lemon::MinCut::UninitializedParameter";
    862862      }
    863863    };
     
    874874    /// The type of the map that stores the edge capacities.
    875875    typedef typename Traits::CapacityMap CapacityMap;
    876     /// The type of the work graph
    877     typedef typename Traits::WorkGraph WorkGraph;
    878     /// The type of the work capacity map
    879     typedef typename Traits::WorkCapacityMap WorkCapacityMap;
     876    /// The type of the aux graph
     877    typedef typename Traits::AuxGraph AuxGraph;
     878    /// The type of the aux capacity map
     879    typedef typename Traits::AuxCapacityMap AuxCapacityMap;
    880880    /// The cross reference type used for the current heap.
    881881    typedef typename Traits::HeapCrossRef HeapCrossRef;
    882882    /// The heap type used by the max cardinality algorithm.
    883883    typedef typename Traits::Heap Heap;
    884     /// The node refrefernces between the original and work graph type.
     884    /// The node refrefernces between the original and aux graph type.
    885885    typedef typename Traits::NodeRefMap NodeRefMap;
    886886    /// The list node refrefernces in the original graph type.
     
    905905    /// the capacity type to constMap<UEdge, int, 1>()
    906906    struct DefNeutralCapacity
    907       : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
    908       typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
     907      : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
     908      typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
    909909    };
    910910
     
    914914      typedef CR HeapCrossRef;
    915915      typedef H Heap;
    916       static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
     916      static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
    917917        throw UninitializedParameter();
    918918      }
     
    928928    template <class H, class CR = typename Graph::template NodeMap<int> >
    929929    struct DefHeap
    930       : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
    931       typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
     930      : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
     931      typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
    932932    };
    933933
     
    936936      typedef CR HeapCrossRef;
    937937      typedef H Heap;
    938       static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
     938      static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
    939939        return new HeapCrossRef(graph);
    940940      }
     
    953953    template <class H, class CR = typename Graph::template NodeMap<int> >
    954954    struct DefStandardHeap
    955       : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
    956       typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
     955      : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
     956      typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
    957957      Create;
    958958    };
     
    970970    bool local_capacity;
    971971
    972     /// Pointer to the work graph.
    973     WorkGraph *_work_graph;
    974     /// \brief Indicates if \ref _work_graph is locally allocated
     972    /// Pointer to the aux graph.
     973    AuxGraph *_aux_graph;
     974    /// \brief Indicates if \ref _aux_graph is locally allocated
    975975    /// (\c true) or not.
    976     bool local_work_graph;
    977     /// Pointer to the work capacity map
    978     WorkCapacityMap *_work_capacity;
    979     /// \brief Indicates if \ref _work_capacity is locally allocated
     976    bool local_aux_graph;
     977    /// Pointer to the aux capacity map
     978    AuxCapacityMap *_aux_capacity;
     979    /// \brief Indicates if \ref _aux_capacity is locally allocated
    980980    /// (\c true) or not.
    981     bool local_work_capacity;
     981    bool local_aux_capacity;
    982982    /// Pointer to the heap cross references.
    983983    HeapCrossRef *_heap_cross_ref;
     
    990990    bool local_heap;
    991991
    992     /// The minimum cut value.
    993     Value _minimum_cut;
    994     /// The number of the nodes of the work graph.
     992    /// The min cut value.
     993    Value _min_cut;
     994    /// The number of the nodes of the aux graph.
    995995    int _node_num;
    996996    /// The first and last node of the min cut in the next list;
     
    998998
    999999    /// \brief The first and last element in the list associated
    1000     /// to the work graph node.
     1000    /// to the aux graph node.
    10011001    NodeRefMap *_first, *_last;
    10021002    /// \brief The next node in the node lists.
     
    10081008        _capacity = Traits::createCapacityMap(*_graph);
    10091009      }
    1010       if(!_work_graph) {
    1011         local_work_graph = true;
    1012         _work_graph = Traits::createWorkGraph();
    1013       }
    1014       if(!_work_capacity) {
    1015         local_work_capacity = true;
    1016         _work_capacity = Traits::createWorkCapacityMap(*_work_graph);
    1017       }
    1018 
    1019       _first = Traits::createNodeRefMap(*_work_graph);
    1020       _last = Traits::createNodeRefMap(*_work_graph);
     1010      if(!_aux_graph) {
     1011        local_aux_graph = true;
     1012        _aux_graph = Traits::createAuxGraph();
     1013      }
     1014      if(!_aux_capacity) {
     1015        local_aux_capacity = true;
     1016        _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
     1017      }
     1018
     1019      _first = Traits::createNodeRefMap(*_aux_graph);
     1020      _last = Traits::createNodeRefMap(*_aux_graph);
    10211021
    10221022      _next = Traits::createListRefMap(*_graph);
    10231023
    1024       typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
     1024      typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
    10251025
    10261026      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
    10271027        _next->set(it, INVALID);
    1028         typename WorkGraph::Node node = _work_graph->addNode();
     1028        typename AuxGraph::Node node = _aux_graph->addNode();
    10291029        _first->set(node, it);
    10301030        _last->set(node, it);
     
    10341034      for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
    10351035        if (_graph->source(it) == _graph->target(it)) continue;
    1036         typename WorkGraph::UEdge uedge =
    1037           _work_graph->addEdge(ref[_graph->source(it)],
     1036        typename AuxGraph::UEdge uedge =
     1037          _aux_graph->addEdge(ref[_graph->source(it)],
    10381038                               ref[_graph->target(it)]);
    1039         _work_capacity->set(uedge, (*_capacity)[it]);
     1039        _aux_capacity->set(uedge, (*_capacity)[it]);
    10401040       
    10411041      }
     
    10431043      if (!_heap_cross_ref) {
    10441044        local_heap_cross_ref = true;
    1045         _heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
     1045        _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
    10461046      }
    10471047      if (!_heap) {
     
    10531053  public :
    10541054
    1055     typedef MinimumCut Create;
     1055    typedef MinCut Create;
    10561056
    10571057
     
    10601060    ///\param graph the graph the algorithm will run on.
    10611061    ///\param capacity the capacity map used by the algorithm.
    1062     MinimumCut(const Graph& graph, const CapacityMap& capacity)
     1062    MinCut(const Graph& graph, const CapacityMap& capacity)
    10631063      : _graph(&graph),
    10641064        _capacity(&capacity), local_capacity(false),
    1065         _work_graph(0), local_work_graph(false),
    1066         _work_capacity(0), local_work_capacity(false),
     1065        _aux_graph(0), local_aux_graph(false),
     1066        _aux_capacity(0), local_aux_capacity(false),
    10671067        _heap_cross_ref(0), local_heap_cross_ref(false),
    10681068        _heap(0), local_heap(false),
     
    10771077    ///
    10781078    ///\param graph the graph the algorithm will run on.
    1079     MinimumCut(const Graph& graph)
     1079    MinCut(const Graph& graph)
    10801080      : _graph(&graph),
    10811081        _capacity(0), local_capacity(false),
    1082         _work_graph(0), local_work_graph(false),
    1083         _work_capacity(0), local_work_capacity(false),
     1082        _aux_graph(0), local_aux_graph(false),
     1083        _aux_capacity(0), local_aux_capacity(false),
    10841084        _heap_cross_ref(0), local_heap_cross_ref(false),
    10851085        _heap(0), local_heap(false),
     
    10891089    ///
    10901090    /// Destructor.
    1091     ~MinimumCut() {
     1091    ~MinCut() {
    10921092      if (local_heap) delete _heap;
    10931093      if (local_heap_cross_ref) delete _heap_cross_ref;
     
    10951095      if (_last) delete _last;
    10961096      if (_next) delete _next;
    1097       if (local_work_capacity) delete _work_capacity;
    1098       if (local_work_graph) delete _work_graph;
     1097      if (local_aux_capacity) delete _aux_capacity;
     1098      if (local_aux_graph) delete _aux_graph;
    10991099      if (local_capacity) delete _capacity;
    11001100    }
     
    11071107    /// automatically allocated heap and cross reference, of course.
    11081108    /// \return <tt> (*this) </tt>
    1109     MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
     1109    MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
    11101110    {
    11111111      if (local_heap_cross_ref) {
     
    11221122    }
    11231123
    1124     /// \brief Sets the work graph.
    1125     ///
    1126     /// Sets the work graph used by algorithm.
     1124    /// \brief Sets the aux graph.
     1125    ///
     1126    /// Sets the aux graph used by algorithm.
    11271127    /// If you don't use this function before calling \ref run(),
    11281128    /// it will allocate one. The destuctor deallocates this
    11291129    /// automatically allocated graph, of course.
    11301130    /// \return <tt> (*this) </tt>
    1131     MinimumCut &workGraph(WorkGraph& work_graph)
     1131    MinCut &auxGraph(AuxGraph& aux_graph)
    11321132    {
    1133       if(local_work_graph) {
    1134         delete _work_graph;
    1135         local_work_graph=false;
    1136       }
    1137       _work_graph = &work_graph;
     1133      if(local_aux_graph) {
     1134        delete _aux_graph;
     1135        local_aux_graph=false;
     1136      }
     1137      _aux_graph = &aux_graph;
    11381138      return *this;
    11391139    }
    11401140
    1141     /// \brief Sets the work capacity map.
    1142     ///
    1143     /// Sets the work capacity map used by algorithm.
     1141    /// \brief Sets the aux capacity map.
     1142    ///
     1143    /// Sets the aux capacity map used by algorithm.
    11441144    /// If you don't use this function before calling \ref run(),
    11451145    /// it will allocate one. The destuctor deallocates this
    11461146    /// automatically allocated graph, of course.
    11471147    /// \return <tt> (*this) </tt>
    1148     MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
     1148    MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
    11491149    {
    1150       if(local_work_capacity) {
    1151         delete _work_capacity;
    1152         local_work_capacity=false;
    1153       }
    1154       _work_capacity = &work_capacity_map;
     1150      if(local_aux_capacity) {
     1151        delete _aux_capacity;
     1152        local_aux_capacity=false;
     1153      }
     1154      _aux_capacity = &aux_capacity_map;
    11551155      return *this;
    11561156    }
     
    11791179    /// Processes the next phase in the algorithm. The function
    11801180    /// should be called countNodes(graph) - 1 times to get
    1181     /// surely the minimum cut in the graph. The 
     1181    /// surely the min cut in the graph. The 
    11821182    ///
    11831183    ///\return %True when the algorithm finished.
    11841184    bool processNextPhase() {
    11851185      if (_node_num <= 1) return true;
    1186       using namespace _minimum_cut_bits;
    1187 
    1188       typedef typename WorkGraph::Node Node;
    1189       typedef typename WorkGraph::NodeIt NodeIt;
    1190       typedef typename WorkGraph::UEdge UEdge;
    1191       typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
     1186      using namespace _min_cut_bits;
     1187
     1188      typedef typename AuxGraph::Node Node;
     1189      typedef typename AuxGraph::NodeIt NodeIt;
     1190      typedef typename AuxGraph::UEdge UEdge;
     1191      typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
    11921192     
    1193       typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
     1193      typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
    11941194      template DefHeap<Heap, HeapCrossRef>::
    11951195      template DefCardinalityMap<NullMap<Node, Value> >::
     
    11971197      Create MaxCardinalitySearch;
    11981198     
    1199       MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
    1200       for (NodeIt it(*_work_graph); it != INVALID; ++it) {
     1199      MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
     1200      for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
    12011201        _heap_cross_ref->set(it, Heap::PRE_HEAP);
    12021202      }
     
    12111211      mcs.run();
    12121212
    1213       Node new_node = _work_graph->addNode();
    1214 
    1215       typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
     1213      Node new_node = _aux_graph->addNode();
     1214
     1215      typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
    12161216     
    12171217      Node first_node = last_two_nodes[0];
     
    12231223
    12241224      Value current_cut = 0;     
    1225       for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
    1226         Node node = _work_graph->runningNode(it);
    1227         current_cut += (*_work_capacity)[it];
     1225      for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
     1226        Node node = _aux_graph->runningNode(it);
     1227        current_cut += (*_aux_capacity)[it];
    12281228        if (node == second_node) continue;
    12291229        if (edges[node] == INVALID) {
    1230           edges[node] = _work_graph->addEdge(new_node, node);
    1231           (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
     1230          edges[node] = _aux_graph->addEdge(new_node, node);
     1231          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
    12321232        } else {
    1233           (*_work_capacity)[edges[node]] += (*_work_capacity)[it];         
     1233          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
    12341234        }
    12351235      }
    12361236
    1237       if (_first_node == INVALID || current_cut < _minimum_cut) {
     1237      if (_first_node == INVALID || current_cut < _min_cut) {
    12381238        _first_node = (*_first)[first_node];
    12391239        _last_node = (*_last)[first_node];
    1240         _minimum_cut = current_cut;
    1241       }
    1242 
    1243       _work_graph->erase(first_node);
    1244 
    1245       for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
    1246         Node node = _work_graph->runningNode(it);
     1240        _min_cut = current_cut;
     1241      }
     1242
     1243      _aux_graph->erase(first_node);
     1244
     1245      for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
     1246        Node node = _aux_graph->runningNode(it);
    12471247        if (edges[node] == INVALID) {
    1248           edges[node] = _work_graph->addEdge(new_node, node);
    1249           (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
     1248          edges[node] = _aux_graph->addEdge(new_node, node);
     1249          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
    12501250        } else {
    1251           (*_work_capacity)[edges[node]] += (*_work_capacity)[it];         
     1251          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
    12521252        }
    12531253      }
    1254       _work_graph->erase(second_node);
     1254      _aux_graph->erase(second_node);
    12551255
    12561256      --_node_num;
     
    12681268
    12691269
    1270     /// \brief Runs %MinimumCut algorithm.
    1271     ///
    1272     /// This method runs the %Minimum cut algorithm
     1270    /// \brief Runs %MinCut algorithm.
     1271    ///
     1272    /// This method runs the %Min cut algorithm
    12731273    ///
    12741274    /// \note mc.run(s) is just a shortcut of the following code.
     
    12851285
    12861286    /// \name Query Functions
    1287     /// The result of the %MinimumCut algorithm can be obtained using these
     1287    /// The result of the %MinCut algorithm can be obtained using these
    12881288    /// functions.\n
    12891289    /// Before the use of these functions,
     
    12921292    ///@{
    12931293
    1294     /// \brief Returns the minimum cut value.
    1295     ///
    1296     /// Returns the minimum cut value if the algorithm finished.
     1294    /// \brief Returns the min cut value.
     1295    ///
     1296    /// Returns the min cut value if the algorithm finished.
    12971297    /// After the first processNextPhase() it is a value of a
    12981298    /// valid cut in the graph.
    12991299    Value minCut() const {
    1300       return _minimum_cut;
    1301     }
    1302 
    1303     /// \brief Returns a minimum cut in a NodeMap.
     1300      return _min_cut;
     1301    }
     1302
     1303    /// \brief Returns a min cut in a NodeMap.
    13041304    ///
    13051305    /// It sets the nodes of one of the two partitions to true in
     
    13161316    }
    13171317
    1318     /// \brief Returns a minimum cut in a NodeMap.
     1318    /// \brief Returns a min cut in a NodeMap.
    13191319    ///
    13201320    /// It sets the nodes of one of the two partitions to true and
     
    13301330    }
    13311331
    1332     /// \brief Returns a minimum cut in an EdgeMap.
    1333     ///
    1334     /// If an undirected edge is in a minimum cut then it will be
     1332    /// \brief Returns a min cut in an EdgeMap.
     1333    ///
     1334    /// If an undirected edge is in a min cut then it will be
    13351335    /// set to true and the others will be set to false in the given map.
    13361336    template <typename EdgeMap>
Note: See TracChangeset for help on using the changeset viewer.