COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
02/14/06 11:41:16 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2547
Message:

Name modification

Location:
lemon
Files:
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r1967 r1968  
    5959        max_matching.h \
    6060        min_cost_flow.h \
    61         minimal_cut.h \
     61        minimum_cut.h \
    6262        suurballe.h \
    6363        preflow.h \
  • lemon/minimum_cut.h

    r1967 r1968  
    11/* -*- C++ -*-
    2  * lemon/minimal_cut.h - Part of LEMON, a generic C++ optimization library
     2 * lemon/minimum_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_MINIMAL_CUT_H
    18 #define LEMON_MINIMAL_CUT_H
     17#ifndef LEMON_MINIMUM_CUT_H
     18#define LEMON_MINIMUM_CUT_H
    1919
    2020
    2121/// \ingroup topology
    2222/// \file
    23 /// \brief Maximum cardinality search and minimal cut in undirected graphs.
     23/// \brief Maximum cardinality search and minimum cut in undirected graphs.
    2424
    2525#include <lemon/list_graph.h>
     
    3535namespace lemon {
    3636
    37   namespace _minimal_cut_bits {
     37  namespace _minimum_cut_bits {
    3838
    3939    template <typename CapacityMap>
     
    9898    ///
    9999    /// \sa MaxCardinalitySearch
    100     typedef typename _minimal_cut_bits
     100    typedef typename _minimum_cut_bits
    101101    ::HeapSelector<CapacityMap>
    102102    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
     
    689689  };
    690690
    691   /// \brief Default traits class of MinimalCut class.
     691  /// \brief Default traits class of MinimumCut class.
    692692  ///
    693   /// Default traits class of MinimalCut class.
     693  /// Default traits class of MinimumCut class.
    694694  /// \param Graph Graph type.
    695695  /// \param CapacityMap Type of length map.
    696696  template <typename _Graph, typename _CapacityMap>
    697   struct MinimalCutDefaultTraits {
     697  struct MinimumCutDefaultTraits {
    698698    /// \brief The type of the capacity of the edges.
    699699    typedef typename _CapacityMap::Value Value;
     
    757757    }
    758758   
    759     /// \brief The heap type used by MinimalCut algorithm.
    760     ///
    761     /// The heap type used by MinimalCut algorithm. It should
     759    /// \brief The heap type used by MinimumCut algorithm.
     760    ///
     761    /// The heap type used by MinimumCut algorithm. It should
    762762    /// maximalize the priorities and the heap's key type is
    763763    /// the work graph's node.
    764764    ///
    765765    /// \sa BinHeap
    766     /// \sa MinimalCut
    767     typedef typename _minimal_cut_bits
     766    /// \sa MinimumCut
     767    typedef typename _minimum_cut_bits
    768768    ::HeapSelector<CapacityMap>
    769769    ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
     
    807807  };
    808808
    809   namespace _minimal_cut_bits {
     809  namespace _minimum_cut_bits {
    810810    template <typename _Key>
    811811    class LastTwoMap {
     
    831831  /// \ingroup topology
    832832  ///
    833   /// \brief Calculates the minimal cut in an undirected graph.
     833  /// \brief Calculates the minimum cut in an undirected graph.
    834834  ///
    835   /// Calculates the minimal cut in an undirected graph.
     835  /// Calculates the minimum cut in an undirected graph.
    836836  /// The algorithm separates the graph's nodes to two partitions with the
    837   /// minimal sum of edge capacities between the two partitions. The
     837  /// minimum sum of edge capacities between the two partitions. The
    838838  /// algorithm can be used to test the network reliability specifically
    839839  /// to test how many links have to be destroyed in the network to split it
     
    848848  template <typename _Graph = ListUGraph,
    849849            typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
    850             typename _Traits = MinimalCutDefaultTraits<_Graph, _CapacityMap> >
     850            typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
    851851#endif
    852   class MinimalCut {
     852  class MinimumCut {
    853853  public:
    854854    /// \brief \ref Exception for uninitialized parameters.
     
    859859    public:
    860860      virtual const char* exceptionName() const {
    861         return "lemon::MinimalCut::UninitializedParameter";
     861        return "lemon::MinimumCut::UninitializedParameter";
    862862      }
    863863    };
     
    905905    /// the capacity type to constMap<UEdge, int, 1>()
    906906    struct DefNeutralCapacity
    907       : public MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
    908       typedef MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
     907      : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
     908      typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
    909909    };
    910910
     
    928928    template <class H, class CR = typename Graph::template NodeMap<int> >
    929929    struct DefHeap
    930       : public MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
    931       typedef MinimalCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
     930      : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
     931      typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
    932932    };
    933933
     
    953953    template <class H, class CR = typename Graph::template NodeMap<int> >
    954954    struct DefStandardHeap
    955       : public MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
    956       typedef MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
     955      : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
     956      typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
    957957      Create;
    958958    };
     
    990990    bool local_heap;
    991991
    992     /// The minimal cut value.
    993     Value _minimal_cut;
     992    /// The minimum cut value.
     993    Value _minimum_cut;
    994994    /// The number of the nodes of the work graph.
    995995    int _node_num;
     
    10531053  public :
    10541054
    1055     typedef MinimalCut Create;
     1055    typedef MinimumCut Create;
    10561056
    10571057
     
    10601060    ///\param graph the graph the algorithm will run on.
    10611061    ///\param capacity the capacity map used by the algorithm.
    1062     MinimalCut(const Graph& graph, const CapacityMap& capacity)
     1062    MinimumCut(const Graph& graph, const CapacityMap& capacity)
    10631063      : _graph(&graph),
    10641064        _capacity(&capacity), local_capacity(false),
     
    10771077    ///
    10781078    ///\param graph the graph the algorithm will run on.
    1079     MinimalCut(const Graph& graph)
     1079    MinimumCut(const Graph& graph)
    10801080      : _graph(&graph),
    10811081        _capacity(0), local_capacity(false),
     
    10891089    ///
    10901090    /// Destructor.
    1091     ~MinimalCut() {
     1091    ~MinimumCut() {
    10921092      if (local_heap) delete _heap;
    10931093      if (local_heap_cross_ref) delete _heap_cross_ref;
     
    11071107    /// automatically allocated heap and cross reference, of course.
    11081108    /// \return <tt> (*this) </tt>
    1109     MinimalCut &heap(Heap& heap, HeapCrossRef &crossRef)
     1109    MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
    11101110    {
    11111111      if (local_heap_cross_ref) {
     
    11291129    /// automatically allocated graph, of course.
    11301130    /// \return <tt> (*this) </tt>
    1131     MinimalCut &workGraph(WorkGraph& work_graph)
     1131    MinimumCut &workGraph(WorkGraph& work_graph)
    11321132    {
    11331133      if(local_work_graph) {
     
    11461146    /// automatically allocated graph, of course.
    11471147    /// \return <tt> (*this) </tt>
    1148     MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
     1148    MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
    11491149    {
    11501150      if(local_work_capacity) {
     
    11791179    /// Processes the next phase in the algorithm. The function
    11801180    /// should be called countNodes(graph) - 1 times to get
    1181     /// surely the minimal cut in the graph. The 
     1181    /// surely the minimum 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 _minimal_cut_bits;
     1186      using namespace _minimum_cut_bits;
    11871187
    11881188      typedef typename WorkGraph::Node Node;
     
    12351235      }
    12361236
    1237       if (_first_node == INVALID || current_cut < _minimal_cut) {
     1237      if (_first_node == INVALID || current_cut < _minimum_cut) {
    12381238        _first_node = (*_first)[first_node];
    12391239        _last_node = (*_last)[first_node];
    1240         _minimal_cut = current_cut;
     1240        _minimum_cut = current_cut;
    12411241      }
    12421242
     
    12681268
    12691269
    1270     /// \brief Runs %MinimalCut algorithm.
    1271     ///
    1272     /// This method runs the %Minimal cut algorithm
     1270    /// \brief Runs %MinimumCut algorithm.
     1271    ///
     1272    /// This method runs the %Minimum 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 %MinimalCut algorithm can be obtained using these
     1287    /// The result of the %MinimumCut algorithm can be obtained using these
    12881288    /// functions.\n
    12891289    /// Before the use of these functions,
     
    12921292    ///@{
    12931293
    1294     /// \brief Returns the minimal cut value.
    1295     ///
    1296     /// Returns the minimal cut value if the algorithm finished.
     1294    /// \brief Returns the minimum cut value.
     1295    ///
     1296    /// Returns the minimum 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 _minimal_cut;
    1301     }
    1302 
    1303     /// \brief Returns a minimal cut in a NodeMap.
     1300      return _minimum_cut;
     1301    }
     1302
     1303    /// \brief Returns a minimum 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 minimal cut in a NodeMap.
     1318    /// \brief Returns a minimum 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 minimal cut in an EdgeMap.
     1332    /// \brief Returns a minimum cut in an EdgeMap.
    13331333    ///
    13341334    /// If an undirected edge is cut edge then it will be
Note: See TracChangeset for help on using the changeset viewer.