#include <lemon/min_cut.h>
Inherited by MinCut::DefHeap, MinCut::DefNeutralCapacity, and MinCut::DefStandardHeap.
Inheritance diagram for MinCut:
The complexity of the algorithm is but with Fibonacci heap it can be decreased to
. When capacity map is neutral then it uses BucketHeap which results
time complexity.
Public Member Functions | |
MinCut (const Graph &graph, const CapacityMap &capacity) | |
Constructor. | |
MinCut (const Graph &graph) | |
Constructor. | |
~MinCut () | |
Destructor. | |
MinCut & | heap (Heap &heap, HeapCrossRef &crossRef) |
Sets the heap and the cross reference used by algorithm. | |
MinCut & | auxGraph (AuxGraph &aux_graph) |
Sets the aux graph. | |
MinCut & | 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 () |
Initializes the internal data structures. | |
bool | processNextPhase () |
Processes the next phase. | |
void | start () |
Executes the algorithm. | |
void | run () |
Runs MinCut algorithm. | |
Query Functions | |
The result of the MinCut 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::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. | |
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. | |
Graph::Node | _first_node |
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. | |
Classes | |
struct | DefHeap |
Named parameter for setting heap and cross reference type More... | |
struct | DefNeutralCapacity |
Named parameter for setting the capacity type to constMap<UEdge, int, 1>() More... | |
struct | DefStandardHeap |
Named parameter for setting heap and cross reference type with automatic allocation More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
MinCut | ( | const Graph & | graph, | |
const CapacityMap & | capacity | |||
) | [inline] |
graph | the graph the algorithm will run on. | |
capacity | the capacity map used by the algorithm. |
This constructor can be used only when the Traits class defines how can we instantiate a local capacity map. If the DefNeutralCapacity used the algorithm automatically construct the capacity map.
graph | the graph the algorithm will run on. |
~MinCut | ( | ) | [inline] |
Destructor.
MinCut& heap | ( | Heap & | heap, | |
HeapCrossRef & | crossRef | |||
) | [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)
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.
(*this)
MinCut& 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.
(*this)
void init | ( | ) | [inline] |
Initializes the internal data structures.
bool processNextPhase | ( | ) | [inline] |
Processes the next phase in the algorithm. The function should be called countNodes(graph) - 1 times to get surely the min cut in the graph. The
void start | ( | ) | [inline] |
void run | ( | ) | [inline] |
This method runs the Min cut algorithm
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.