Node partitions


Functions

virtual void abstractMixedGraph::InitPartition () throw ()
virtual void abstractMixedGraph::Bud (TNode v) throw (ERRange)
virtual void abstractMixedGraph::Merge (TNode u, TNode v) throw (ERRange)
virtual TNode abstractMixedGraph::Find (TNode v) throw (ERRange)
virtual void abstractMixedGraph::ReleasePartition () throw ()

Function Documentation

void Bud (  TNode  v  )  throw (ERRange) [virtual, inherited]
 

Start a single node set.

Parameters:
v A node index ranged [0,1,..,n-1]
After this operation, it is Find(v)==v.

Reimplemented in abstractBalancedFNW.

TNode Find (  TNode  v  )  throw (ERRange) [virtual, inherited]
 

Retrieve the set containing a given node.

Parameters:
v A node index ranged [0,1,..,n-1]
Returns:
A node index ranged [0,1,..,n-1] or NoNode
This returns the index of an arbitrary but fixed node in the same set, the so-called canonical element in this set. Only when sets are merged, the canonical element changes.

In order to check if two nodes x,y are in the same set, it is sufficient to evaluate Find(x)==Find(y) and Find(u)!=NoNode. If the context parameter methDSU is set, Find() does not only lookup the canonical element, but also performs some path compression to reduce the future lookup times.

Reimplemented in abstractBalancedFNW.

void InitPartition (   )  throw () [virtual, inherited]
 

Initialize the disjoint node set structure.

If not already present, the disjoint node set structure is allocated. After this operation, it is Find(v)==NoNode for every node v.

Reimplemented in abstractBalancedFNW.

void Merge (  TNode  u,
TNode  v
)  throw (ERRange) [virtual, inherited]
 

Merge two disjoint node sets represented by arbitrary members.

Parameters:
u A node index ranged [0,1,..,n-1]
v A node index ranged [0,1,..,n-1]
After this operation, it is Find(u)==Find(v).

Reimplemented in abstractBalancedFNW.

void ReleasePartition (   )  throw () [virtual, inherited]
 

Release the disjoint set structure.

After this operation, it is Find(v)==v for every node v, and the disjoint node set structure is deallocated.

Reimplemented in abstractBalancedFNW.