nodeSplitting Class Reference
[Graph derivation]

Split all nodes of a given mixed graph object. More...

#include <sparseDigraph.h>

Inheritance diagram for nodeSplitting:

sparseDiGraph abstractDiGraph abstractMixedGraph managedObject goblinRootObject

Public Member Functions

 nodeSplitting (abstractMixedGraph &_G, TOption options=0) throw ()
void MapEdgeCut () throw ()

Detailed Description

Split all nodes of a given mixed graph object.

In this digraph, every node of the original graph is replaced by a node pair and a directed arc connecting these two nodes. The original arcs end up at the mapped start nodes and start at the mapped end nodes. Additionally, the original arcs are oriented by applying the same rules as in the completeOrientation constructor.

Constructor & Destructor Documentation

nodeSplitting (  abstractMixedGraph &  _G,
TOption  options = 0
)  throw ()
 

Parameters:
_G The original mixed graph
options A combination of TOptNodeSplitting values

Member Function Documentation

void MapEdgeCut (   )  throw ()
 

Map back an edge cut to the original graph.

This sets the node colours of the original graph depending on the colours of the respective node pair in the node splitting object. In the case of unit node capacities (not using the MCC_MAP_DEMANDS option), a minimum cut of the node splitting is transformed to a minimum node cut of the original graph (such that left-hand nodes and right-hand nodes are non-adjacent.