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 but with Fibonacci heap it can be decreased to . When the edges have unit capacities, BucketHeap
can be used which yields time complexity.
#include <lemon/nagamochi_ibaraki.h>
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. More... | |
NagamochiIbaraki (const Graph &graph) | |
Constructor. More... | |
~NagamochiIbaraki () | |
Destructor. More... | |
NagamochiIbaraki & | heap (Heap &hp, HeapCrossRef &cr) |
Sets the heap and the cross reference used by algorithm. More... | |
Execution control | |
The simplest way to execute the algorithm is to use one of the member functions called | |
void | init () |
Initializes the internal data structures. More... | |
bool | processNextPhase () |
Processes the next phase. More... | |
void | start () |
Executes the algorithm. More... | |
void | run () |
Runs NagamochiIbaraki algorithm. More... | |
Query Functions | |
Value | minCutValue () const |
Returns the min cut value. More... | |
template<typename CutMap > | |
Value | minCutMap (CutMap &cutMap) const |
Returns a min cut in a NodeMap. More... | |
|
inline |
graph | The graph the algorithm runs on. |
capacity | The capacity map used by the algorithm. |
|
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.
graph | The graph the algorithm runs on. |
|
inline |
Destructor.
|
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.
(*this)
|
inline |
Initializes the internal data structures.
|
inline |
Processes the next phase in the algorithm. It must be called at most one less the number of the nodes in the graph.
|
inline |
Executes the algorithm.
|
inline |
This method runs the Min cut algorithm
|
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.