Minimum cuts


Enumerations

enum  abstractMixedGraph::TOptNodeSplitting {
  abstractMixedGraph::MCC_UNIT_CAPACITIES = 0,
  abstractMixedGraph::MCC_MAP_DEMANDS = 1,
  abstractMixedGraph::MCC_MAP_UNDERLYING = 2
}
enum  abstractMixedGraph::TMethMCC {
  abstractMixedGraph::MCC_DEFAULT = -1,
  abstractMixedGraph::MCC_MAXFLOW = 0,
  abstractMixedGraph::MCC_PREFLOW_FIFO = 1,
  abstractMixedGraph::MCC_PREFLOW_HIGH = 2,
  abstractMixedGraph::MCC_IDENTIFICATION = 3
}

Functions

TCap abstractMixedGraph::NodeConnectivity (TNode source=NoNode, TNode target=NoNode, TOptNodeSplitting mode=MCC_MAP_DEMANDS) throw ()
TCap abstractMixedGraph::EdgeConnectivity (TNode source=NoNode, TNode target=NoNode) throw (ERRange)
TCap abstractMixedGraph::EdgeConnectivity (TMethMCC method, TNode source=NoNode, TNode target=NoNode) throw (ERRange)
TCap abstractMixedGraph::StrongNodeConnectivity (TNode source=NoNode, TNode target=NoNode, TOptNodeSplitting mode=MCC_MAP_DEMANDS) throw ()
TCap abstractMixedGraph::StrongEdgeConnectivity (TNode source=NoNode, TNode target=NoNode) throw (ERRange)
TCap abstractMixedGraph::StrongEdgeConnectivity (abstractMixedGraph::TMethMCC method, TNode source=NoNode, TNode target=NoNode) throw (ERRange)

Enumeration Type Documentation

enum TMethMCC [inherited]
 

Alternative methods for the minium capacity cut solver.

Enumerator:
MCC_DEFAULT  Apply the default method set in goblinController::methMST.
MCC_MAXFLOW  Apply an iterated nax-flow method.
MCC_PREFLOW_FIFO  Apply a FIFO push & relabel method.
MCC_PREFLOW_HIGH  Apply a highest order push & relabel method.
MCC_IDENTIFICATION  Apply a node identification method.

enum TOptNodeSplitting [inherited]
 

Options for the nodeSplitting constructor.

Enumerator:
MCC_UNIT_CAPACITIES  Assume unit node capacities and infinite arc capacities.
MCC_MAP_DEMANDS  Instead of taking unit node capacities, apply the node demands.
MCC_MAP_UNDERLYING  Ignore the arc orientations, do as if all arcs are undirected.

Function Documentation

TCap EdgeConnectivity (  TMethMCC  method,
TNode  source = NoNode,
TNode  target = NoNode
)  throw (ERRange) [inherited]
 

Compute a global minimum edge cut.

Parameters:
method A TMethMCC value specifying the applied method
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
Returns:
The edge connectivity number (the minimum number of separation edges)
If two nodes are specified, this procedure determines a minimum edge cut by computing a maximum flow for this node pair. Otherwise, the method parameter allows to to choose from various methods.

This determines a minimum edge cut by computing a series of n maximum st-flows. The optimal edge cut is exported by the node colour register where colour indices are interpreted as follows:

  • 0: Left-hand nodes (including source)
  • 1: Right-hand nodes (including target)

TCap EdgeConnectivity (  TNode  source = NoNode,
TNode  target = NoNode
)  throw (ERRange) [inherited]
 

Compute a global minimum edge cut.

Parameters:
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
Returns:
The minimum cut capacity
This is a shortcut for EdgeConnectivity(MCC_DEFAULT,source,target)

TCap NodeConnectivity (  TNode  source = NoNode,
TNode  target = NoNode,
TOptNodeSplitting  mode = MCC_MAP_DEMANDS
)  throw () [inherited]
 

Compute a global minimum node cut.

Parameters:
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
mode If MCC_UNIT_CAPACITIES, assume unit node capacities. If MCC_MAP_DEMANDS, apply the node demands
Returns:
The connectivity number (the minimum number of separation nodes)
Provided that all node demands are 1 or that mode==0, this determines a minimum node cut as in the standard terminology, by splitting the nodes and computing maximum st-flows for all node pairs. The optimal node cut is exported by the node colour register where colour indices are interpreted as follows:
  • 0: Cut nodes
  • 1: Left-hand nodes
  • 2: Right-hand nodes

TCap StrongEdgeConnectivity (  abstractMixedGraph::TMethMCC  method,
TNode  source = NoNode,
TNode  target = NoNode
)  throw (ERRange) [inherited]
 

Compute a minimum edge cut in the directed sense.

Parameters:
method Either MCC_MAXFLOW, MCC_PREFLOW_HIGH or MCC_PREFLOW_FIFO
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
Returns:
The minimum st-cut capacity
This is the public interface to all strong edge connectivity methods. It calls one of the MCC_StrongEdgeConnectivity() methods, depending on on the passed node indices.

TCap StrongEdgeConnectivity (  TNode  source = NoNode,
TNode  target = NoNode
)  throw (ERRange) [inherited]
 

Compute a minimum edge cut in the directed sense.

Parameters:
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
Returns:
The minimum cut capacity
This is a shortcut for StrongEdgeConnectivity(MCC_DEFAULT,source,target)

TCap StrongNodeConnectivity (  TNode  source = NoNode,
TNode  target = NoNode,
TOptNodeSplitting  mode = MCC_MAP_DEMANDS
)  throw () [inherited]
 

Compute a global minimum node cut in the directed sense.

Parameters:
source A predefined left-hand node or NoNode
target A predefined right-hand node or NoNode
mode If MCC_UNIT_CAPACITIES, assume unit node capacities. If MCC_MAP_DEMANDS, apply the node demands
Returns:
The strong connectivity number (the minimum number of separating nodes)
Provided that all node demands are 1 or that mode==0, this determines a minimum node cut as in the standard terminology. by splitting the nodes and computing maximum st-flows for all node pairs. The optimal node cut is exported by the node colour register where colour indices are interpreted as follows:
  • 0: Cut nodes
  • 1: Left-hand nodes
  • 2: Right-hand nodes For undirected graphs, the procedure behaves just as Connectivity().