My Project
Loading...
Searching...
No Matches
NagamochiIbaraki< GR, CM, TR > Class Template Reference

Detailed Description

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

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.

Warning
The value type of the capacity map should be able to hold any cut value of the graph, otherwise the result can overflow.
Note
This capacity is supposed to be integer type.

#include <lemon/nagamochi_ibaraki.h>

+ Inheritance diagram for NagamochiIbaraki< GR, CM, TR >:

Classes

struct  SetHeap
 Named parameter for setting heap and cross reference type More...
 
struct  SetStandardHeap
 Named parameter for setting heap and cross reference type with automatic allocation More...
 
struct  SetUnitCapacity
 Named parameter for setting the capacity map to a constMap<Edge, int, 1>() instance More...
 

Public Types

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.
 

Public Member Functions

 NagamochiIbaraki (const Graph &graph, const CapacityMap &capacity)
 Constructor.
 
 NagamochiIbaraki (const Graph &graph)
 Constructor.
 
 ~NagamochiIbaraki ()
 Destructor.
 
NagamochiIbarakiheap (Heap &hp, HeapCrossRef &cr)
 Sets the heap and the cross reference used by algorithm.
 
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.

void init ()
 Initializes the internal data structures.
 
bool processNextPhase ()
 Processes the next phase.
 
void start ()
 Executes the algorithm.
 
void run ()
 Runs NagamochiIbaraki algorithm.
 
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.

Value minCutValue () const
 Returns the min cut value.
 
template<typename CutMap >
Value minCutMap (CutMap &cutMap) const
 Returns a min cut in a NodeMap.
 

Constructor & Destructor Documentation

◆ NagamochiIbaraki() [1/2]

template<typename GR , typename CM , typename TR >
NagamochiIbaraki ( const Graph & graph,
const CapacityMap & capacity )
inline
Parameters
graphThe graph the algorithm runs on.
capacityThe capacity map used by the algorithm.

◆ NagamochiIbaraki() [2/2]

template<typename GR , typename CM , typename TR >
NagamochiIbaraki ( const Graph & graph)
inline

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
graphThe graph the algorithm runs on.

◆ ~NagamochiIbaraki()

template<typename GR , typename CM , typename TR >
~NagamochiIbaraki ( )
inline

Destructor.

Member Function Documentation

◆ heap()

template<typename GR , typename CM , typename TR >
NagamochiIbaraki & heap ( Heap & hp,
HeapCrossRef & cr )
inline

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)

◆ init()

template<typename GR , typename CM , typename TR >
void init ( )
inline

Initializes the internal data structures.

◆ processNextPhase()

template<typename GR , typename CM , typename TR >
bool processNextPhase ( )
inline

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.

◆ start()

template<typename GR , typename CM , typename TR >
void start ( )
inline

Executes the algorithm.

Precondition
init() must be called

◆ run()

template<typename GR , typename CM , typename TR >
void run ( )
inline

This method runs the Min cut algorithm

Note
mc.run(s) is just a shortcut of the following code.
mc.init();
mc.start();

◆ minCutValue()

template<typename GR , typename CM , typename TR >
Value minCutValue ( ) const
inline

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

◆ minCutMap()

template<typename GR , typename CM , typename TR >
template<typename CutMap >
Value minCutMap ( CutMap & cutMap) const
inline

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

Parameters
cutMapA writable node map with bool (or convertible) value type.