Connectivity components

Enumerations
enum	{   abstractMixedGraph::CONN_CUT_NODE = 0,   abstractMixedGraph::CONN_LEFT_HAND = 1,   abstractMixedGraph::CONN_RIGHT_HAND = 2 }
enum	abstractMixedGraph::TRetDFS {   abstractMixedGraph::DFS_DISCONNECTED = 0,   abstractMixedGraph::DFS_BICONNECTED = 1,   abstractMixedGraph::DFS_MULTIPLE_BLOCKS = 2,   abstractMixedGraph::DFS_ALMOST_BICONNECTED = 3 }
Functions
bool	abstractMixedGraph::Connected () throw ()
virtual bool	abstractMixedGraph::Connected (TCap k) throw ()
TRetDFS	abstractMixedGraph::CutNodes (TArc rootArc=NoArc, TNode *order=NULL, TArc *lowArc=NULL) throw ()
bool	abstractMixedGraph::Biconnected () throw ()
bool	abstractMixedGraph::STNumbering (TArc rootArc=NoArc, TNode source=NoNode, TNode target=NoNode) throw (ERRejected)
virtual bool	abstractMixedGraph::EdgeConnected (TCap k) throw ()
bool	abstractMixedGraph::StronglyConnected () throw ()
virtual bool	abstractMixedGraph::StronglyConnected (TCap k) throw ()
virtual bool	abstractMixedGraph::StronglyEdgeConnected (TCap k) throw ()

---

Enumeration Type Documentation

anonymous enum [inherited]

Colour indices used to specify node and edge cuts. Enumerator: CONN_CUT_NODE  Specifies a cut node. CONN_LEFT_HAND  Specifies a left-hand node. CONN_RIGHT_HAND  Specifies a right-hand node.

enum TRetDFS [inherited]

The formal return of the DFS method CutNodes(). Enumerator: DFS_DISCONNECTED  The graph is not even 1-connected. DFS_BICONNECTED  The graph is biconnected. DFS_MULTIPLE_BLOCKS  The graph is connected, but not biconnected. DFS_ALMOST_BICONNECTED  The graph is not biconnected, but can be made made biconnected by adding a single edge

---

Function Documentation

bool Biconnected (   )  throw () [inherited]

2-edge connectivity test Return values: true  The graph is 2-edge connected Assigns node colours such that equally coloured nodes are in the same 2-edge connected component. Edge colours and predecessor labels are as for CutNodes()

bool Connected (  TCap  k  )  throw () [virtual, inherited]

Test for k-connectivity. Parameters: k  The desired degree of connectivity Return values: true  The graph is k-connected

bool Connected (   )  throw () [inherited]

Connectivity test. Return values: true  The graph is connected Assigns node colours such that equally coloured nodes are in the same connected component. The predecessor labels encode a DFS tree / forest

abstractMixedGraph::TRetDFS CutNodes (  TArc  rootArc = NoArc, TNode *  order = NULL, TArc *  lowArc = NULL )  throw () [inherited]

Multiple purpose DFS method, 2-connectivity test. Parameters: rootArc  The arc considered first in the DFS. If the graph is 2-connected, its the only tree arc adjacent with the root node order[]  Pre-ordinal numbers (nodes are numbered increasingly when reached the first time) lowArc[]  For any node v, a non-tree arc connecting a descendent of v with the lowest ancestor of v Return values: true  The graph is 2-connected This method exports a maximal predecessor tree / forest. If the graph is not connected, each connected component is scanned. If the graph is not 2-connected, the nodes coloured 0 are the cut nodes, and the other colour classes define the non-trivial 2-blocks. Edge colours are assigned such that equally coloured edge denote edges in the same 2-connected component. The procedure is capable to export additional information by the arrays order[] and lowArc[]

bool EdgeConnected (  TCap  k  )  throw () [virtual, inherited]

Test for k-edge connectivity. Parameters: k  The desired degree of connectivity Return values: true  If the graph is k-edge connected

bool STNumbering (  TArc  rootArc = NoArc, TNode  source = NoNode, TNode  target = NoNode )  throw (ERRejected) [inherited]

Bipolar numbering and open ear decomposition. Parameters: source  The node with the minimum ordinal number 0 (optional parameter) target  The node with the maximum ordinal number n-1 (optional parameter) rootArc  If specified, the end node of this arc becomes the target, and the start node becomes the source (optional parameter) Return values: true  The graph could be decomposed Exports the ordinal numbers by the node colours register and an open ear decomposition by the edge colours register. The input graph must be 2-connected or, at least, adding an arc between the selected source and target node must make the graph 2-connected

bool StronglyConnected (  TCap  k  )  throw () [virtual, inherited]

Test for strong k-connectivity. Parameters: k  The desired degree of connectivity Return values: true  If the graph is strongly k-connected

bool StronglyConnected (   )  throw () [inherited]

Test for strong connectivity. Return values: true  If the graph is strongly connected Perform a reverse and a forward DFS. Assigns node colours such that equally coloured nodes are in the same strong component. The predecessor labels represent a forest spanning the strong components

bool StronglyEdgeConnected (  TCap  k  )  throw () [virtual, inherited]

Test for strong k-edge connectivity. Parameters: k  The desired degree of connectivity Return values: true  If the graph is strongly k-edge connected