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