NagamochiIbaraki< _Graph, _CapacityMap, _Traits > Class Template Reference
[Minimum Cut algorithms]

---

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Traits>
class lemon::NagamochiIbaraki< _Graph, _CapacityMap, _Traits >

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 specifically to test how many links have to be destroyed in the network to split it at least two distinict subnetwork.

The complexity of the algorithm is but with Fibonacci heap it can be decreased to . When unit capacity minimum cut is computed then it uses BucketHeap which results 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.

#include <lemon/nagamochi_ibaraki.h>

List of all members.

Classes
struct	DefHeap
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
struct	DefUnitCapacity
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Member Functions
	NagamochiIbaraki (const Graph &graph, const CapacityMap &capacity)
	Constructor.
	NagamochiIbaraki (const Graph &graph)
	Constructor.
	~NagamochiIbaraki ()
NagamochiIbaraki &	heap (Heap &hp, HeapCrossRef &cr)
	Sets the heap and the cross reference used by algorithm.
NagamochiIbaraki &	auxGraph (AuxGraph &aux_graph)
	Sets the aux graph.
NagamochiIbaraki &	auxCapacityMap (AuxCapacityMap &aux_capacity_map)
	Sets the aux capacity map.
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 ()
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	minCut () const
	Returns the min cut value.
template<typename NodeMap >
Value	quickMinCut (NodeMap &nodeMap) const
	Returns a min cut in a NodeMap.
template<typename NodeMap >
Value	minCut (NodeMap &nodeMap) const
	Returns a min cut in a NodeMap.
template<typename EdgeMap >
Value	cutEdges (EdgeMap &edgeMap) const
	Returns a min cut in an EdgeMap.
Private Types
typedef Traits::Graph	Graph
	The type of the underlying graph.
typedef Traits::CapacityMap::Value	Value
	The type of the capacity of the edges.
typedef Traits::CapacityMap	CapacityMap
	The type of the map that stores the edge capacities.
typedef Traits::AuxGraph	AuxGraph
	The type of the aux graph.
typedef Traits::AuxCapacityMap	AuxCapacityMap
	The type of the aux capacity map.
typedef Traits::AuxCutValueMap	AuxCutValueMap
	The type of the aux cut value map.
typedef Traits::HeapCrossRef	HeapCrossRef
	The cross reference type used for the current heap.
typedef Traits::Heap	Heap
	The heap type used by the max cardinality algorithm.
typedef Traits::NodeRefMap	NodeRefMap
	The node refrefernces between the original and aux graph type.
typedef Traits::ListRefMap	ListRefMap
	The list node refrefernces in the original graph type.
Private Attributes
const Graph *	_graph
	Pointer to the underlying graph.
const CapacityMap *	_capacity
	Pointer to the capacity map.
bool	local_capacity
	Indicates if _capacity is locally allocated (true) or not.
AuxGraph *	_aux_graph
	Pointer to the aux graph.
bool	local_aux_graph
	Indicates if _aux_graph is locally allocated (true) or not.
AuxCapacityMap *	_aux_capacity
	Pointer to the aux capacity map.
bool	local_aux_capacity
	Indicates if _aux_capacity is locally allocated (true) or not.
AuxCutValueMap *	_aux_cut_value
	Pointer to the aux cut value map.
bool	local_aux_cut_value
	Indicates if _aux_cut_value is locally allocated (true) or not.
HeapCrossRef *	_heap_cross_ref
	Pointer to the heap cross references.
bool	local_heap_cross_ref
	Indicates if _heap_cross_ref is locally allocated (true) or not.
Heap *	_heap
	Pointer to the heap.
bool	local_heap
	Indicates if _heap is locally allocated (true) or not.
Value	_min_cut
	The min cut value.
int	_node_num
	The number of the nodes of the aux graph.
std::vector< typename Graph::Node >	_cut
	The first and last node of the min cut in the next list.
NodeRefMap *	_first
	The first and last element in the list associated to the aux graph node.
ListRefMap *	_next
	The next node in the node lists.

---

Constructor & Destructor Documentation

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

Parameters:

	graph	the graph the algorithm will run on.
	capacity	the capacity map used by the algorithm.

NagamochiIbaraki

(

const Graph &

graph

)

[inline]

This constructor can be used only when the Traits class defines how can we instantiate a local capacity map. If the DefUnitCapacity used the algorithm automatically construct the capacity map.

Parameters:

graph

the graph the algorithm will run on.

~NagamochiIbaraki

(

)

[inline]

Destructor.

---

Member Function Documentation

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)

NagamochiIbaraki& auxGraph

(

AuxGraph &

aux_graph

)

[inline]

Sets the aux graph used by algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated graph, of course.

Returns:

(*this)

NagamochiIbaraki& auxCapacityMap

(

AuxCapacityMap &

aux_capacity_map

)

[inline]

Sets the aux capacity map used by algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated graph, of course.

Returns:

(*this)

void init

(

)

[inline]

Initializes the internal data structures.

bool processNextPhase

(

)

[inline]

Processes the next phase in the algorithm. The function should be called at most countNodes(graph) - 1 times to get surely the min cut in the graph.

Returns:

True when the algorithm finished.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called

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();

Value minCut

(

)

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.

Value quickMinCut

(

NodeMap &

nodeMap

)

const [inline]

It sets the nodes of one of the two partitions to true in the given BoolNodeMap. The map contains a valid cut if the map have been set false previously.

Value minCut

(

NodeMap &

nodeMap

)

const [inline]

It sets the nodes of one of the two partitions to true and the other partition to false. The function first set all of the nodes to false and after it call the quickMinCut() member.

Value cutEdges

(

EdgeMap &

edgeMap

)

const [inline]

If an undirected edge is in a min cut then it will be set to true and the others will be set to false in the given map.