Predecessor labels


Functions

TArc * abstractMixedGraph::InitPredecessors () throw ()
TArc * abstractMixedGraph::GetPredecessors () const throw ()
TArc * abstractMixedGraph::RawPredecessors () throw ()
TArc abstractMixedGraph::Pred (TNode v) const throw (ERRange)
void abstractMixedGraph::SetPred (TNode v, TArc thisPred) throw (ERRange,ERRejected)
void abstractMixedGraph::ReleasePredecessors () throw ()
TNode abstractMixedGraph::ExtractTrees () throw ()
TNode abstractMixedGraph::ExtractPath (TNode u, TNode v) throw ()
TNode abstractMixedGraph::ExtractCycles () throw ()
TNode abstractMixedGraph::Extract1Matching () throw ()
TNode abstractMixedGraph::ExtractEdgeCover () throw ()

Function Documentation

TNode Extract1Matching (   )  throw () [inherited]
 

Check if the current subgraph forms a 1-matching and convert it to the predecessor labels.

Returns:
The matching cardinality or NoNode
This examines the subgraph. If adjacent subgraph edges are found, NoNode is returned. Otherwise, for every subgraph edge, two antiparallel predecessor arca are generated.

TNode ExtractCycles (   )  throw () [inherited]
 

Check if the current subgraph forms a 2-factor and convert it to the predecessor labels.

Returns:
The number of cycles or NoNode
This examines all subgraph arcs. All nodes must be incident with exactly two subgraph edges. If not, NoNode is returned. Otherwise ExtractPath() is called once for every cycle to do the actual conversion.

TNode ExtractEdgeCover (   )  throw () [inherited]
 

Extract an edge cover from a 1-matching subgraph and save it to the predecessor labels.

Returns:
The edge cover cardinality or NoNode
This examines the subgraph. If adjacent subgraph edges are found, NoNode is returned. Otherwise, for every subgraph edge, two antiparallel predecessor arca are generated. For the unmatched nodes, arbitrary predecessor arcs are assigned or, if there are isolated nodes, NoNode is returned.

TNode ExtractPath (  TNode  u,
TNode  v
)  throw () [inherited]
 

Convert a subgraph path to the predecessor labels.

Parameters:
u A node index in the range [0,1..,n-1]
v A node index in the range [0,1..,n-1]
Returns:
The uv-path length or NoNode
This searches the subgraph component of the node u which is assumed to form a uv-path or, if u==v, a cycle. In the regular case, the predecessor labels are partially assigned with a subgraph path or cycle, directed from u to v. If the sugraph component is not a simple path, the procedure does or does not return prematurely with NoNode.

TNode ExtractTrees (   )  throw () [inherited]
 

Check if the current subgraph forms a forest and convert it to the predecessor labels.

Returns:
The number of connected subgraph components or NoNode
This examines all subgraph arcs. If the subgraph contains cycles, NoNode is returned. Otherwise, for every subgraph component a rooted tree is exported to the predecessor labels.

TArc * GetPredecessors (   )  const throw () [inherited]
 

Get access to the node predecessor labels.

Returns:
A pointer to the array of predecessor labels or NULL
Other than InitPredecessors() and RawPredecessors(), this operation does not allocate predecessor labels if those do not exist.

TArc * InitPredecessors (   )  throw () [inherited]
 

Initialize the node predecessor labels.

Returns:
A pointer to the array of predecessor labels
If not already present, the node predecessor label data structure is allocated. In any case, all predecessor labels are set to NoArc.

TArc Pred (  TNode  v  )  const throw (ERRange) [inherited]
 

Retrieve a predecessor label of a given node.

Parameters:
v A node index in the range [0,1..,n-1]
Returns:
An arc index ranged [0,1,..,2*mAct-1] or NoArc
This operation is little efficient if it is called for several nodes due to the attribute lookup operations which occur.

TArc * RawPredecessors (   )  throw () [inherited]
 

Ensure existence of the node predecessor labels.

Returns:
A pointer to the array of predecessor labels
If not already present, the node predecessor label data structure is allocated. Other than InitPredecessors(), this does not initialize the array element values.

void ReleasePredecessors (   )  throw () [inherited]
 

Release the node predecessor labels from memory.

This implicitly sets all node predecessor labels to NoArc.

void SetPred (  TNode  v,
TArc  thisPred
)  throw (ERRange,ERRejected) [inherited]
 

Assign a predecessor label to a given node.

Parameters:
v A node index in the range [0,1..,n-1]
thisPred An arc index ranged [0,1,..,2*mAct-1] or NoArc
If not already present and if thisPred != NoArc, the node predecessor label data structure is allocated. In any case, thisPred is assigned as the predecessor label of v.

This operation is little efficient if it is called for several nodes due to the attribute lookup operations which occur.