NagamochiIbaraki

Declared in lemon/nagamochi_ibaraki.h, in the group Minimum Cut Algorithms; the same class on the Doxygen site.

template< typename GR , typename CM , typename TR >
class NagamochiIbaraki

Calculates the minimum cut in an undirected graph.

Calculates the minimum cut in an undirected graph with the Nagamochi-Ibaraki algorithm. The algorithm separates the graph’s nodes into two partitions with the minimum sum of edge capacities between the two partitions. The algorithm can be used to test the network reliability, especially to test how many links have to be destroyed in the network to split it to at least two distinict subnetworks.

The complexity of the algorithm is \( O(nm\log(n)) \) but with Fibonacci heap it can be decreased to \( O(nm+n^2\log(n)) \). When the edges have unit capacities, BucketHeap can be used which yields \( O(nm) \) time complexity.

Note

This capacity is supposed to be integer type.

Warning

The value type of the capacity map should be able to hold any cut value of the graph, otherwise the result can overflow.

Execution control

The simplest way to execute the algorithm is to use one of the member functions called run()

.

If you need more control on the execution, first you must call

init() and then call the start() or proper times the processNextPhase() member functions.

inline void init()

Initializes the internal data structures.

Pre:

The graph has at least one node. A graph of one node has no cut, and the algorithm then gives the value 0 and that node.

inline bool processNextPhase()

Processes the next phase.

Processes the next phase in the algorithm. It must be called at most one less the number of the nodes in the graph.

Returns:

True when the algorithm finished.

inline void start()

Executes the algorithm.

Pre:

init() must be called

inline void run()

Runs NagamochiIbaraki algorithm.

This method runs the Min cut algorithm

Note

mc.run(s) is just a shortcut of the following code.

mc.init();
mc.start();

Pre:

The graph has at least one node.

Query Functions

The result of the NagamochiIbaraki algorithm can be obtained using these functions.

Before the use of these functions, either

run() or start() must be called.

inline Value minCutValue() const

Returns the min cut value.

Returns the min cut value if the algorithm finished. After the first processNextPhase() it is a value of a valid cut in the graph.

template< typename CutMap >
inline Value minCutMap( CutMap & cutMap ) const

Returns a min cut in a NodeMap.

It sets the nodes of one of the two partitions to true and the other partition to false.

Parameters:

cutMap – A writable node map with bool (or convertible) value type.

Public Types

typedef TR Traits
typedef Traits::Graph Graph

The type of the underlying graph.

typedef Traits::CapacityMap CapacityMap

The type of the capacity map.

typedef Traits::CapacityMap::Value Value

The value type of the capacity map.

typedef Traits::Heap Heap

The heap type used by the algorithm.

typedef Traits::HeapCrossRef HeapCrossRef

The cross reference type used for the heap.

typedef NagamochiIbaraki Create

Public Functions

inline NagamochiIbaraki( const Graph & graph , const CapacityMap & capacity )

Constructor.

Parameters:
  • graph – The graph the algorithm runs on.

  • capacity – The capacity map used by the algorithm.

inline NagamochiIbaraki( const Graph & graph )

Constructor.

This constructor can be used only when the Traits class defines how can the local capacity map be instantiated. If the SetUnitCapacity used the algorithm automatically constructs the capacity map.

Parameters:

graph – The graph the algorithm runs on.

inline NagamochiIbaraki & tolerance( const Tolerance< Value > & tolerance )

Sets the tolerance used by the algorithm.

Sets the tolerance object used by the algorithm on the capacities and the cut values.

Returns:

(*this)

inline const Tolerance< Value > & tolerance() const

Returns a const reference to the tolerance.

inline ~NagamochiIbaraki()

Destructor.

inline NagamochiIbaraki & heap( Heap & hp , HeapCrossRef & cr )

Sets the heap and the cross reference used by algorithm. If you don’t use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated heap and cross reference, of course.

Returns:

(*this)

Protected Functions

inline NagamochiIbaraki()
struct SetUnitCapacityTraits : public Traits

Public Types

typedef ConstMap< typename Graph::Edge , Const< int , 1 > > CapacityMap

Public Static Functions

static inline CapacityMap * createCapacityMap( const Graph & )
struct SetUnitCapacity : public NagamochiIbaraki< Graph , CapacityMap , SetUnitCapacityTraits >

Named parameter for setting the capacity map to a constMap< Edge , int , 1 >() instance

Public Types

typedef NagamochiIbaraki< Graph , CapacityMap , SetUnitCapacityTraits > Create
template< class H , class CR >
struct SetHeapTraits : public Traits

Public Types

typedef CR HeapCrossRef
typedef H Heap

Public Static Functions

static inline HeapCrossRef * createHeapCrossRef( const Graph & )
static inline Heap * createHeap(HeapCrossRef&)
template< class H , class CR = typename Graph::template NodeMap< int > >
struct SetHeap : public NagamochiIbaraki< Graph , CapacityMap , SetHeapTraits< H , typename Graph::template NodeMap< int > > >

Named parameter for setting heap and cross reference type. The heap has to maximize the priorities.

Public Types

typedef NagamochiIbaraki< Graph , CapacityMap , SetHeapTraits< H , CR > > Create
template< class H , class CR >
struct SetStandardHeapTraits : public Traits

Public Types

typedef CR HeapCrossRef
typedef H Heap

Public Static Functions

static inline HeapCrossRef * createHeapCrossRef( const Graph & graph )
static inline Heap * createHeap( HeapCrossRef & crossref )
template< class H , class CR = typename Graph::template NodeMap< int > >
struct SetStandardHeap : public NagamochiIbaraki< Graph , CapacityMap , SetStandardHeapTraits< H , typename Graph::template NodeMap< int > > >

Named parameter for setting heap and cross reference type with automatic allocation. They should have standard constructor interfaces to be able to automatically created by the algorithm (i.e. the graph should be passed to the constructor of the cross reference and the cross reference should be passed to the constructor of the heap). However, external heap and cross reference objects could also be passed to the algorithm using the heap() function before calling run() or init(). The heap has to maximize the priorities.

See also

SetHeap

Public Types

typedef NagamochiIbaraki< Graph , CapacityMap , SetStandardHeapTraits< H , CR > > Create