COIN-OR::LEMON - Graph Library

Changeset 2530:f86f7e4eb2ba in lemon-0.x for lemon/nagamochi_ibaraki.h


Ignore:
Timestamp:
12/04/07 11:55:27 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3407
Message:

Reimplementation of Hao-Orlin algorithm
Little modifictaion in NagamochiIbaraki?
More docs for minimum cut algorithms

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/nagamochi_ibaraki.h

    r2506 r2530  
    848848  ///
    849849  /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
    850   /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. 
    851   /// When capacity map is neutral then it uses BucketHeap which
    852   /// results \f$ O(ne) \f$ time complexity.
     850  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$.
     851  /// When unit capacity minimum cut is computed then it uses
     852  /// BucketHeap which results \f$ O(ne) \f$ time complexity.
    853853  ///
    854854  /// \warning The value type of the capacity map should be able to hold
     
    907907    ///@{
    908908
    909     struct DefNeutralCapacityTraits : public Traits {
     909    struct DefUnitCapacityTraits : public Traits {
    910910      typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
    911911      static CapacityMap *createCapacityMap(const Graph&) {
     
    918918    /// \ref named-templ-param "Named parameter" for setting
    919919    /// the capacity type to constMap<UEdge, int, 1>()
    920     struct DefNeutralCapacity
     920    struct DefUnitCapacity
    921921      : public NagamochiIbaraki<Graph, CapacityMap,
    922                                 DefNeutralCapacityTraits> {
     922                                DefUnitCapacityTraits> {
    923923      typedef NagamochiIbaraki<Graph, CapacityMap,
    924                                DefNeutralCapacityTraits> Create;
     924                               DefUnitCapacityTraits> Create;
    925925    };
    926926
     
    11351135    /// This constructor can be used only when the Traits class
    11361136    /// defines how can we instantiate a local capacity map.
    1137     /// If the DefNeutralCapacity used the algorithm automatically
     1137    /// If the DefUnitCapacity used the algorithm automatically
    11381138    /// construct the capacity map.
    11391139    ///
Note: See TracChangeset for help on using the changeset viewer.