Open
Graph Drawing
Framework

  v.2007.11
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files
Search for: 

ogdf::DynamicSPQRForest

ogdf::DynamicSPQRForest Class Reference

Dynamic SPQR-forest. More...

#include <DynamicSPQRForest.h>

Inheritance diagram for ogdf::DynamicSPQRForest:

ogdf::DynamicBCTree ogdf::BCTree ogdf::DynamicSPQRTree ogdf::DynamicPlanarSPQRTree

List of all members.

Public Types

enum  TNodeType { SComp, PComp, RComp }
 Enumeration type for characterizing the SPQR-tree-vertices. More...

Public Member Functions

 DynamicSPQRForest (Graph &G)
 A constructor.
node spqrproper (edge eH) const
 finds the proper representant of the SPQR-tree-vertex which a given real or virtual edge is belonging to.
edge twinEdge (edge eH) const
 returns the twin edge of a given edge of m_H, if it is virtual, or NULL, if it is real.
TNodeType typeOfTNode (node vT) const
 returns the type of the triconnected component represented by a given SPQR-tree-vertex.
const List< edge > & hEdgesSPQR (node vT) const
 returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex.
SList< node > & findPathSPQR (node sH, node tH) const
 finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.
edge virtualEdge (node vT, node wT) const
 returns the virtual edge which leads from one vertex of an SPQR-tree to another one.
edge updateInsertedEdge (edge eG)
 updates the whole data structure after a new edge has been inserted into the original graph.
node updateInsertedNode (edge eG, edge fG)
 updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

Protected Member Functions

void init ()
 Initialization.
void createSPQR (node vB) const
 creates the SPQR-tree for a given B-component of the BC-tree.
node uniteSPQR (node vB, node sT, node tT)
 unites two SPQR-tree-vertices (UNION part of UNION/FIND).
node findSPQR (node vT) const
 finds the proper representant of an SPQR-tree-vertex (FIND part of UNION/FIND).
node findNCASPQR (node sT, node tT) const
 finds the nearest common ancestor of sT and tT.
SList< node > & findPathSPQR (node sH, node tH, node &rT) const
 finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.
edge updateInsertedEdgeSPQR (node vB, edge eG)
 updates an SPQR-tree after a new edge has been inserted into the original graph.
node updateInsertedNodeSPQR (node vB, edge eG, edge fG)
 updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

Protected Attributes

Graph m_T
 A Graph structure containing all SPQR-trees.
NodeArray< node > m_bNode_SPQR
 The root vertices of the SPQR-trees.
NodeArray< int > m_bNode_numS
 The numbers of S-components.
NodeArray< int > m_bNode_numP
 The numbers of P-components.
NodeArray< int > m_bNode_numR
 The numbers of R-components.
NodeArray< TNodeType > m_tNode_type
 The types of the SPQR-tree-vertices.
NodeArray< node > m_tNode_owner
 The owners of the SPQR-tree-vertices in the UNION/FIND structure.
NodeArray< edge > m_tNode_hRefEdge
 The virtual edges leading to the parents of the SPQR-tree-vertices.
NodeArray< List< edge > > m_tNode_hEdges
 Lists of real and virtual edges belonging to SPQR-tree-vertices.
EdgeArray< ListIterator< edge > > m_hEdge_position
 The positions of real and virtual edges in their m_tNode_hEdges lists.
EdgeArray< node > m_hEdge_tNode
 The SPQR-tree-vertices which the real and virtual edges are belonging to.
EdgeArray< edge > m_hEdge_twinEdge
 The partners of virtual edges (NULL if real).
NodeArray< node > m_htogc
 Auxiliary array used by createSPQR().
NodeArray< bool > m_tNode_isMarked
 Auxiliary array used by findNCASPQR().

Detailed Description

Dynamic SPQR-forest.

This class is an extension of DynamicBCTree.
It provides a set of SPQR-trees for each B-component of a BC-tree. These SPQR-trees are dynamic, i.e. there are member functions for dynamic updates (edge insertion and node insertion).

Definition at line 70 of file DynamicSPQRForest.h.

Member Enumeration Documentation

enum ogdf::DynamicSPQRForest::TNodeType

Enumeration type for characterizing the SPQR-tree-vertices.

Enumerator:
SComp  denotes a vertex representing an S-component.
PComp  denotes a vertex representing a P-component.
RComp  denotes a vertex representing an R-component.

Definition at line 86 of file DynamicSPQRForest.h.

Constructor & Destructor Documentation

ogdf::DynamicSPQRForest::DynamicSPQRForest ( Graph &  G  )  [inline]

A constructor.

This constructor does only create the dynamic BC-tree rooted at the first edge of G. The data structure is prepared for dealing with SPQR-trees, but they will only be created on demand. Cf. member functions findPathSPQR() and updateInsertedEdge().

Parameters:
G is the original graph.

Definition at line 286 of file DynamicSPQRForest.h.

Member Function Documentation

void ogdf::DynamicSPQRForest::init (  )  [protected]

Initialization.

Reimplemented from ogdf::DynamicBCTree.

void ogdf::DynamicSPQRForest::createSPQR ( node  vB  )  const [protected]

creates the SPQR-tree for a given B-component of the BC-tree.

An SPQR-tree belonging to a B-component of the BC-tree is only created on demand, i.e. this member function is only called by findSPQRTree() and - under certain circumstances - by updateInsertedEdge().

Parameters:
vB is a vertex of the BC-tree representing a B-component.
Precondition:
vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.

The B-component represented by vB must contain at least 3 edges.

node ogdf::DynamicSPQRForest::uniteSPQR ( node  vB,
node  sT,
node  tT 
) [protected]

unites two SPQR-tree-vertices (UNION part of UNION/FIND).

Parameters:
vB is a vertex of the BC-tree representing a B-component.
sT is a vertex of the SPQR-tree belonging to vB.
tT is a vertex of the SPQR-tree belonging to vB.
Precondition:
vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.

sT and tT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

Returns:
the proper representant of the united SPQR-tree-vertex.

node ogdf::DynamicSPQRForest::findSPQR ( node  vT  )  const [protected]

finds the proper representant of an SPQR-tree-vertex (FIND part of UNION/FIND).

Parameters:
vT is any vertex of m_T.
Returns:
the owner of vT properly representing a triconnected component, i.e. the root of the UNION/FIND-tree of vT.

node ogdf::DynamicSPQRForest::findNCASPQR ( node  sT,
node  tT 
) const [protected]

finds the nearest common ancestor of sT and tT.

Parameters:
sT is a vertex of an SPQR-tree.
tT is a vertex of an SPQR-tree.
Precondition:
sT and tT must belong to the same SPQR-tree.

sT and tT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees.

Returns:
the proper representant of the nearest common ancestor of sT and tT.

SList<node>& ogdf::DynamicSPQRForest::findPathSPQR ( node  sH,
node  tH,
node &  rT 
) const [protected]

finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters:
sH is a vertex of m_H.
tH is a vertex of m_H.
rT is a reference! It is set to the very vertex of the found path which is nearest to the root vertex of the SPQR-tree.
Precondition:
sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree must exist!
Returns:
the path in the SPQR-tree as a linear list of vertices.
Postcondition:
The SList<node> instance is created by this function and has to be destructed by the caller!

edge ogdf::DynamicSPQRForest::updateInsertedEdgeSPQR ( node  vB,
edge  eG 
) [protected]

updates an SPQR-tree after a new edge has been inserted into the original graph.

Parameters:
vB is a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
eG is a new edge in the original graph.
Precondition:
vB has to be the proper representant of its B-component, i.e. it has to be the root vertex of its respective UNION/FIND-tree.

Both the source and the target vertices of eG must belong to the same B-component represented by vB.

Returns:
the new edge of the original graph.

node ogdf::DynamicSPQRForest::updateInsertedNodeSPQR ( node  vB,
edge  eG,
edge  fG 
) [protected]

updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

Parameters:
vB is a BC-tree-vertex representing a B-component. The SPQR-tree, which is to be updated is identified by it.
eG is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fG is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation.
Precondition:
The split edge must belong to the B-component which is represented by vB.
Returns:
the new vertex of the original graph.

node ogdf::DynamicSPQRForest::spqrproper ( edge  eH  )  const [inline]

finds the proper representant of the SPQR-tree-vertex which a given real or virtual edge is belonging to.

This member function has to be used carefully (see Precondition)!

Parameters:
eH is an edge of m_H.
Precondition:
The respective SPQR-tree belonging to the B-component represented by the BC-tree-vertex bcproper(eH) must exist! Notice, that this condition is fulfilled, if eH is a member of a list gained by the hEdgesSPQR() member function, because that member function needs an SPQR-tree-vertex as parameter, which might have been found (and eventually created) by the findPathSPQR() member function.
Returns:
the proper representant of the SPQR-tree-vertex which eH is belonging to.

Definition at line 303 of file DynamicSPQRForest.h.

edge ogdf::DynamicSPQRForest::twinEdge ( edge  eH  )  const [inline]

returns the twin edge of a given edge of m_H, if it is virtual, or NULL, if it is real.

Parameters:
eH is an edge of m_H.
Returns:
the twin edge of eH, if it is virtual, or NULL, if it is real.

Definition at line 311 of file DynamicSPQRForest.h.

TNodeType ogdf::DynamicSPQRForest::typeOfTNode ( node  vT  )  const [inline]

returns the type of the triconnected component represented by a given SPQR-tree-vertex.

Parameters:
vT is a vertex of an SPQR-tree.
Precondition:
vT has to be the proper representant of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.
Returns:
the type of the triconnected component represented by vT.

Definition at line 323 of file DynamicSPQRForest.h.

const List<edge>& ogdf::DynamicSPQRForest::hEdgesSPQR ( node  vT  )  const [inline]

returns a linear list of the edges in m_H belonging to the triconnected component represented by a given SPQR-tree-vertex.

Parameters:
vT is a vertex of an SPQR-tree.
Precondition:
vT has to be the proper representant of its triconnected component, i.e. it has to be the root vertex of its respective UNION/FIND-tree. This condition is particularly fulfilled if vT is a member of a list gained by the findPathSPQR() member function.
Returns:
a linear list of the edges in m_H belonging to the triconnected component represented by vT.

Definition at line 335 of file DynamicSPQRForest.h.

SList<node>& ogdf::DynamicSPQRForest::findPathSPQR ( node  sH,
node  tH 
) const

finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.

Parameters:
sH is a vertex of m_H.
tH is a vertex of m_H.
Precondition:
sH and tH must belong to the same B-component, i.e. to the same SPQR-tree. This SPQR-tree does not need to exist. If it it does not exist, it will be created.
Returns:
the path in the SPQR-tree as a linear list of vertices.
Postcondition:
The SList<node> instance is created by this function and has to be destructed by the caller!

edge ogdf::DynamicSPQRForest::virtualEdge ( node  vT,
node  wT 
) const

returns the virtual edge which leads from one vertex of an SPQR-tree to another one.

Parameters:
vT is a vertex of an SPQR-tree.
wT is a vertex of an SPQR-tree.
Precondition:
vT and wT must belong to the same SPQR-tree and must be adjacent.

vT and wT have to be proper representants of their triconnected components, i.e. they have to be the root vertices of their respective UNION/FIND-trees. This condition is particularly fulfilled if vT and wT are members of a list gained by the findPathSPQR() member function.

Returns:
the virtual edge in m_H which belongs to wT and leads to vT.

edge ogdf::DynamicSPQRForest::updateInsertedEdge ( edge  eG  )  [virtual]

updates the whole data structure after a new edge has been inserted into the original graph.

This member function generally updates both BC- and SPQR-trees. If any SPQR-tree of the B-components of the insertion path through the BC-tree exists, the SPQR-tree data structure of the resulting B-component will be valid afterwards. If none of the SPQR-trees does exist in advance, then only the BC-tree is updated and no SPQR-tree is created.

Parameters:
eG is a new edge in the original graph.
Returns:
the new edge of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

node ogdf::DynamicSPQRForest::updateInsertedNode ( edge  eG,
edge  fG 
) [virtual]

updates the whole data structure after a new vertex has been inserted into the original graph by splitting an edge into eG and fG.

This member function updates the BC-tree at first. If the SPQR-tree of the B-component which the split edge is belonging to does exist, then it is updated, too. If it does not exist, it is not created.

Parameters:
eG is the incoming edge of the newly inserted vertex which has been generated by a Graph::split() operation.
fG is the outgoing edge of the newly inserted vertex which has been generated by a Graph::split() operation.
Returns:
the new vertex of the original graph.

Reimplemented from ogdf::DynamicBCTree.

Reimplemented in ogdf::DynamicSPQRTree.

Member Data Documentation

Graph ogdf::DynamicSPQRForest::m_T [mutable, protected]

A Graph structure containing all SPQR-trees.

Definition at line 93 of file DynamicSPQRForest.h.

NodeArray<node> ogdf::DynamicSPQRForest::m_bNode_SPQR [mutable, protected]

The root vertices of the SPQR-trees.

For each vertex of the BC-tree representing a B-component, this array contains the root vertex of the respective SPQR-tree, or NULL, if the SPQR-tree does not exist.

Definition at line 102 of file DynamicSPQRForest.h.

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numS [mutable, protected]

The numbers of S-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of S-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 111 of file DynamicSPQRForest.h.

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numP [mutable, protected]

The numbers of P-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of P-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 120 of file DynamicSPQRForest.h.

NodeArray<int> ogdf::DynamicSPQRForest::m_bNode_numR [mutable, protected]

The numbers of R-components.

For each vertex of the BC-tree representing a B-component, this array contains the number of R-components of the respective SPQR-tree. If the SPQR-tree does not exist, then the array member is undefined.

Definition at line 129 of file DynamicSPQRForest.h.

NodeArray<TNodeType> ogdf::DynamicSPQRForest::m_tNode_type [mutable, protected]

The types of the SPQR-tree-vertices.

Definition at line 134 of file DynamicSPQRForest.h.

NodeArray<node> ogdf::DynamicSPQRForest::m_tNode_owner [mutable, protected]

The owners of the SPQR-tree-vertices in the UNION/FIND structure.

Definition at line 139 of file DynamicSPQRForest.h.

NodeArray<edge> ogdf::DynamicSPQRForest::m_tNode_hRefEdge [mutable, protected]

The virtual edges leading to the parents of the SPQR-tree-vertices.

Definition at line 144 of file DynamicSPQRForest.h.

NodeArray<List<edge> > ogdf::DynamicSPQRForest::m_tNode_hEdges [mutable, protected]

Lists of real and virtual edges belonging to SPQR-tree-vertices.

Definition at line 149 of file DynamicSPQRForest.h.

EdgeArray<ListIterator<edge> > ogdf::DynamicSPQRForest::m_hEdge_position [mutable, protected]

The positions of real and virtual edges in their m_tNode_hEdges lists.

Definition at line 155 of file DynamicSPQRForest.h.

EdgeArray<node> ogdf::DynamicSPQRForest::m_hEdge_tNode [mutable, protected]

The SPQR-tree-vertices which the real and virtual edges are belonging to.

Definition at line 160 of file DynamicSPQRForest.h.

EdgeArray<edge> ogdf::DynamicSPQRForest::m_hEdge_twinEdge [mutable, protected]

The partners of virtual edges (NULL if real).

Definition at line 164 of file DynamicSPQRForest.h.

NodeArray<node> ogdf::DynamicSPQRForest::m_htogc [mutable, protected]

Auxiliary array used by createSPQR().

Definition at line 169 of file DynamicSPQRForest.h.

NodeArray<bool> ogdf::DynamicSPQRForest::m_tNode_isMarked [mutable, protected]

Auxiliary array used by findNCASPQR().

Definition at line 173 of file DynamicSPQRForest.h.

The documentation for this class was generated from the following file:
© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:09 2007 by doxygen 1.5.4.