Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::ClusterGraph Class Reference

Representation of clustered graphs. More...

#include <ogdf/cluster/ClusterGraph.h>

+ Inheritance diagram for ogdf::ClusterGraph:

Public Member Functions

 ClusterGraph ()
 Creates a cluster graph associated with no graph. More...
 
 ClusterGraph (const Graph &G)
 Creates a cluster graph associated with graph G. More...
 
 ClusterGraph (const ClusterGraph &C)
 Copy constructor. More...
 
 ClusterGraph (const ClusterGraph &C, Graph &G)
 Constructs a clustered graph that is a copy of clustered graph C. More...
 
 ClusterGraph (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
 Constructs a clustered graph that is a copy of clustered graph C. More...
 
 ClusterGraph (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
 Constructs a clustered graph that is a copy of clustered graph C. More...
 
virtual ~ClusterGraph ()
 
void adjAvailable (bool val)
 Sets the availability status of the adjacency entries. More...
 
template<class EDGELIST >
void adjEdges (cluster c, EDGELIST &edges) const
 Returns the list of all edges adjacent to cluster c in edges. More...
 
template<class ADJLIST >
void adjEntries (cluster c, ADJLIST &entries) const
 Returns the list of all adjacency entries adjacent to cluster c in entries. More...
 
template<class CLUSTERLIST >
void allClusters (CLUSTERLIST &clusters) const
 Returns the list of all clusters in clusters. More...
 
void clear ()
 Clears all cluster data. More...
 
void clearClusterTree (cluster C)
 Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself. More...
 
int clusterArrayTableSize () const
 Returns table size of cluster arrays associated with this graph. More...
 
int & clusterDepth (cluster c) const
 Returns depth of cluster c in cluster tree, starting with root depth 1. More...
 
int clusterIdCount () const
 Returns upper bound for cluster indices. More...
 
cluster clusterOf (node v) const
 Returns the cluster to which a node belongs. More...
 
template<class NODELIST >
void collaps (NODELIST &nodes, Graph &G)
 Collapses all nodes in the list nodes to the first node; multi-edges are removed. More...
 
cluster commonCluster (SList< node > &nodes)
 Returns lowest common cluster of nodes in list nodes. More...
 
cluster commonCluster (node v, node w) const
 Returns the lowest common cluster of v and w in the cluster tree. More...
 
cluster commonClusterAncestorsPath (node v, node w, cluster &c1, cluster &c2, List< cluster > &eL) const
 Returns lca of v and w, stores corresponding path in eL and ancestors in c1, c2. More...
 
cluster commonClusterLastAncestors (node v, node w, cluster &c1, cluster &c2) const
 Returns the lowest common cluster lca and the highest ancestors on the path to lca. More...
 
cluster commonClusterPath (node v, node w, List< cluster > &eL) const
 Returns lca of v and w and stores corresponding path in eL. More...
 
void computeSubTreeDepth (cluster c) const
 Computes depth of cluster tree hanging at c. More...
 
bool consistencyCheck ()
 Checks the consistency of the data structure. More...
 
const GraphconstGraph () const
 Returns a reference to the underlying graph. More...
 
cluster createCluster (SList< node > &nodes, const cluster parent=0)
 Creates a new cluster containing the nodes given by nodes; makes it a child of the cluster parent. More...
 
cluster createEmptyCluster (const cluster parent=0, int clusterId=-1)
 Creates an empty cluster with index clusterId and parent parent. More...
 
void delCluster (cluster c)
 Deletes cluster c. More...
 
void emptyClusters (SList< cluster > &emptyCluster, SList< cluster > *checkCluster=0)
 Returns the list of clusters that are empty or only contain empty clusters. More...
 
bool emptyOnClusterDelete (cluster c)
 Returns true if cluster c has only one child and no nodes. More...
 
bool emptyOnNodeDelete (cluster c)
 Returns true if cluster c has only one node and no children. More...
 
cluster firstCluster () const
 Returns the first cluster in the list of all clusters. More...
 
cluster firstPostOrderCluster () const
 Returns the first cluster in the list of post ordered clusters. More...
 
void init (const Graph &G)
 Clears all cluster data and then reinitializes the instance with underlying graph G. More...
 
cluster lastCluster () const
 Returns the last cluster in the list of all cluster. More...
 
template<class LISTITERATOR >
void makeAdjEntries (cluster c, LISTITERATOR start)
 Computes the adjacency entry list for cluster c. More...
 
int maxClusterIndex () const
 Returns the maximal used cluster index. More...
 
void moveCluster (cluster c, cluster newParent)
 Moves cluster c to a new parent newParent. More...
 
cluster newCluster (cluster parent, int id=-1)
 Inserts a new cluster; makes it a child of the cluster parent. More...
 
int numberOfClusters () const
 Returns number of clusters. More...
 
 operator const Graph & () const
 Conversion to const Graph reference. More...
 
ClusterGraphoperator= (const ClusterGraph &C)
 Assignment operator. More...
 
void pullUpSubTree (cluster c)
 Updates depth information in subtree after delCluster. More...
 
void reassignNode (node v, cluster c)
 Reassigns node v to cluster \ c. More...
 
ListIterator< ClusterArrayBase * > registerArray (ClusterArrayBase *pClusterArray) const
 Registers a cluster array. More...
 
ListIterator< ClusterGraphObserver * > registerObserver (ClusterGraphObserver *pObserver) const
 Registers a ClusterGraphObserver. More...
 
void reInit (Graph &G)
 Clear cluster info structure, reinitializes with underlying graph G. More...
 
bool representsCombEmbedding ()
 Checks the combinatorial cluster planar embedding. More...
 
cluster rootCluster () const
 Returns the root cluster. More...
 
void semiClear ()
 Clears all data but does not delete root cluster. More...
 
void setUpdateDepth (bool b) const
 Turns automatic update of node depth values on or off. More...
 
int treeDepth () const
 Computes depth of cluster tree, running time O(C). More...
 
void unregisterArray (ListIterator< ClusterArrayBase * > it) const
 Unregisters a cluster array. More...
 
void unregisterObserver (ListIterator< ClusterGraphObserver * > it) const
 Unregisters a ClusterGraphObserver. More...
 
- Public Member Functions inherited from ogdf::GraphObserver
 GraphObserver ()
 Constructs instance of GraphObserver class. More...
 
 GraphObserver (const Graph *G)
 Constructs instance of GraphObserver class. More...
 
virtual ~GraphObserver ()
 Destroys the instance, unregisters it from watched graph. More...
 
const GraphgetGraph () const
 
void reregister (const Graph *pG)
 Associates observer instance with graph G. More...
 

Protected Member Functions

virtual void cleared ()
 Clears cluster data without deleting root when underlying graphs' clear method is called. More...
 
void copyLCA (const ClusterGraph &C, ClusterArray< cluster > *clusterCopy=0)
 Copies lowest common ancestor info to copy of clustered graph. More...
 
cluster doCreateCluster (SList< node > &nodes, const cluster parent, int clusterId=-1)
 
cluster doCreateCluster (SList< node > &nodes, SList< cluster > &emptyCluster, const cluster parent, int clusterId=-1)
 
virtual void edgeAdded (edge)
 Implementation of inherited method: Updates data if edge added. More...
 
virtual void edgeDeleted (edge)
 Implementation of inherited method: Updates data if edge deleted. More...
 
cluster leftMostCluster (cluster c) const
 Leftmost cluster in subtree rooted at c, gets predecessor of subtree. More...
 
virtual void nodeAdded (node v)
 Implementation of inherited method: Updates data if node added. More...
 
virtual void nodeDeleted (node v)
 Implementation of inherited method: Updates data if node deleted. More...
 
cluster postOrderPredecessor (cluster c) const
 Computes new predecessor for SUBTREE at moved cluster c. More...
 
virtual void reInit ()
 Currently does nothing. More...
 
void updatePostOrder (cluster c, cluster oldParent, cluster newParent)
 Adjusts the post order structure for moved clusters. More...
 

Protected Attributes

bool m_depthUpToDate
 Status of cluster depth information. More...
 
int m_lcaNumber
 Used to save last search run number for commoncluster. More...
 
ClusterArray< int > * m_lcaSearch
 Used to save last search run number for commoncluster. More...
 
bool m_updateDepth
 Depth of clusters is always updated if set to true. More...
 
ClusterArray< cluster > * m_vAncestor
 Used to save last search run number for commoncluster. More...
 
ClusterArray< cluster > * m_wAncestor
 Used to save last search run number for commoncluster. More...
 
- Protected Attributes inherited from ogdf::GraphObserver
ListIterator< GraphObserver * > m_itGList
 watched graph More...
 
const Graphm_pGraph
 

Private Member Functions

void assignNode (node v, cluster C)
 Assigns node v to cluster c (v not yet assigned!). More...
 
void checkPostOrder () const
 Check postorder information in cluster tree. More...
 
void clearClusterTree (cluster c, List< node > &attached)
 
void deepCopy (const ClusterGraph &C, Graph &G)
 
void deepCopy (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
 
void deepCopy (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
 
void initGraph (const Graph &G)
 
cluster newCluster (int id)
 Creates new cluster with given id, precondition: id not used. More...
 
cluster newCluster ()
 Creates new cluster. More...
 
void postOrder () const
 Create postorder information in cluster tree. More...
 
void postOrder (cluster c, SListPure< cluster > &S) const
 
void reinitArrays ()
 
void reinitGraph (const Graph &G)
 Reinitializes instance with graph G. More...
 
void removeNodeAssignment (node v)
 
void shallowCopy (const ClusterGraph &C)
 
void unassignNode (node v)
 Unassigns node v from its cluster. More...
 

Private Attributes

bool m_adjAvailable
 
bool m_allowEmptyClusters
 True if the adjacency list for each cluster is available. More...
 
int m_clusterArrayTableSize
 The current table size of cluster arrays. More...
 
int m_clusterIdCount
 The index assigned to the next created cluster. More...
 
GraphList< ClusterElementm_clusters
 The list of all clusters. More...
 
NodeArray< ListIterator< node > > m_itMap
 Stories for every node its position within the children list of its cluster. More...
 
int m_nClusters
 The number of clusters. More...
 
NodeArray< clusterm_nodeMap
 Defines if empty clusters are deleted immediately if generated by operations. More...
 
const Graphm_pGraph
 The associated graph. More...
 
cluster m_postOrderStart
 The first cluster in postorder. More...
 
ListPure< ClusterArrayBase * > m_regClusterArrays
 The registered cluster arrays. More...
 
ListPure< ClusterGraphObserver * > m_regObservers
 The registered graph observers. More...
 
cluster m_rootCluster
 The root cluster. More...
 

Detailed Description

Representation of clustered graphs.

This class is derived from GraphObserver and handles hierarchical clustering of the nodes in a graph, providing additional functionality.

Definition at line 257 of file ClusterGraph.h.

Constructor & Destructor Documentation

ogdf::ClusterGraph::ClusterGraph ( )

Creates a cluster graph associated with no graph.

ogdf::ClusterGraph::ClusterGraph ( const Graph G)

Creates a cluster graph associated with graph G.

All nodes in G are assigned to the root cluster.

ogdf::ClusterGraph::ClusterGraph ( const ClusterGraph C)

Copy constructor.

ogdf::ClusterGraph::ClusterGraph ( const ClusterGraph C,
Graph G 
)

Constructs a clustered graph that is a copy of clustered graph C.

The underlying graph G is made a copy of C.getGraph().

ogdf::ClusterGraph::ClusterGraph ( const ClusterGraph C,
Graph G,
ClusterArray< cluster > &  originalClusterTable,
NodeArray< node > &  originalNodeTable 
)

Constructs a clustered graph that is a copy of clustered graph C.

The underlying graph G is made a copy of C.getGraph(). Stores the new copies of the original nodes and clusters in the arrays originalNodeTable and originalClusterTable.

ogdf::ClusterGraph::ClusterGraph ( const ClusterGraph C,
Graph G,
ClusterArray< cluster > &  originalClusterTable,
NodeArray< node > &  originalNodeTable,
EdgeArray< edge > &  edgeCopy 
)

Constructs a clustered graph that is a copy of clustered graph C.

The underlying graph G is made a copy of C.getGraph(). Stores the new copies of the original nodes, edges, and clusters in the arrays originalNodeTable, edgeCopy, and originalClusterTable.

virtual ogdf::ClusterGraph::~ClusterGraph ( )
virtual

Member Function Documentation

void ogdf::ClusterGraph::adjAvailable ( bool  val)
inline

Sets the availability status of the adjacency entries.

Definition at line 623 of file ClusterGraph.h.

template<class EDGELIST >
void ogdf::ClusterGraph::adjEdges ( cluster  c,
EDGELIST &  edges 
) const
inline

Returns the list of all edges adjacent to cluster c in edges.

Definition at line 579 of file ClusterGraph.h.

template<class ADJLIST >
void ogdf::ClusterGraph::adjEntries ( cluster  c,
ADJLIST &  entries 
) const
inline

Returns the list of all adjacency entries adjacent to cluster c in entries.

Definition at line 591 of file ClusterGraph.h.

template<class CLUSTERLIST >
void ogdf::ClusterGraph::allClusters ( CLUSTERLIST &  clusters) const
inline

Returns the list of all clusters in clusters.

Definition at line 533 of file ClusterGraph.h.

void ogdf::ClusterGraph::assignNode ( node  v,
cluster  C 
)
private

Assigns node v to cluster c (v not yet assigned!).

void ogdf::ClusterGraph::checkPostOrder ( ) const
private

Check postorder information in cluster tree.

void ogdf::ClusterGraph::clear ( )

Clears all cluster data.

void ogdf::ClusterGraph::clearClusterTree ( cluster  C)

Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself.

void ogdf::ClusterGraph::clearClusterTree ( cluster  c,
List< node > &  attached 
)
private
virtual void ogdf::ClusterGraph::cleared ( )
inlineprotectedvirtual

Clears cluster data without deleting root when underlying graphs' clear method is called.

Implements ogdf::GraphObserver.

Definition at line 698 of file ClusterGraph.h.

int ogdf::ClusterGraph::clusterArrayTableSize ( ) const
inline

Returns table size of cluster arrays associated with this graph.

Definition at line 390 of file ClusterGraph.h.

int& ogdf::ClusterGraph::clusterDepth ( cluster  c) const
inline

Returns depth of cluster c in cluster tree, starting with root depth 1.

Definition at line 443 of file ClusterGraph.h.

int ogdf::ClusterGraph::clusterIdCount ( ) const
inline

Returns upper bound for cluster indices.

Definition at line 387 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::clusterOf ( node  v) const
inline

Returns the cluster to which a node belongs.

Definition at line 379 of file ClusterGraph.h.

template<class NODELIST >
void ogdf::ClusterGraph::collaps ( NODELIST &  nodes,
Graph G 
)
inline

Collapses all nodes in the list nodes to the first node; multi-edges are removed.

Definition at line 541 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::commonCluster ( SList< node > &  nodes)

Returns lowest common cluster of nodes in list nodes.

cluster ogdf::ClusterGraph::commonCluster ( node  v,
node  w 
) const

Returns the lowest common cluster of v and w in the cluster tree.

Precondition
v and w are nodes in the graph.
cluster ogdf::ClusterGraph::commonClusterAncestorsPath ( node  v,
node  w,
cluster c1,
cluster c2,
List< cluster > &  eL 
) const

Returns lca of v and w, stores corresponding path in eL and ancestors in c1, c2.

cluster ogdf::ClusterGraph::commonClusterLastAncestors ( node  v,
node  w,
cluster c1,
cluster c2 
) const

Returns the lowest common cluster lca and the highest ancestors on the path to lca.

cluster ogdf::ClusterGraph::commonClusterPath ( node  v,
node  w,
List< cluster > &  eL 
) const

Returns lca of v and w and stores corresponding path in eL.

void ogdf::ClusterGraph::computeSubTreeDepth ( cluster  c) const

Computes depth of cluster tree hanging at c.

bool ogdf::ClusterGraph::consistencyCheck ( )

Checks the consistency of the data structure.

const Graph& ogdf::ClusterGraph::constGraph ( ) const
inline

Returns a reference to the underlying graph.

Definition at line 349 of file ClusterGraph.h.

void ogdf::ClusterGraph::copyLCA ( const ClusterGraph C,
ClusterArray< cluster > *  clusterCopy = 0 
)
protected

Copies lowest common ancestor info to copy of clustered graph.

cluster ogdf::ClusterGraph::createCluster ( SList< node > &  nodes,
const cluster  parent = 0 
)

Creates a new cluster containing the nodes given by nodes; makes it a child of the cluster parent.

The nodes are reassigned to the new cluster. If you turn off m_allowEmptyclusters, an emptied cluster is deleted except if all nodes are put into the same cluster.

Parameters
nodesare the nodes that will be reassigned to the new cluster.
parentis the parent of the new cluster.
Returns
the created cluster.
cluster ogdf::ClusterGraph::createEmptyCluster ( const cluster  parent = 0,
int  clusterId = -1 
)

Creates an empty cluster with index clusterId and parent parent.

void ogdf::ClusterGraph::deepCopy ( const ClusterGraph C,
Graph G 
)
private

Perform a deep copy on C, C's underlying graph is copied into G.

void ogdf::ClusterGraph::deepCopy ( const ClusterGraph C,
Graph G,
ClusterArray< cluster > &  originalClusterTable,
NodeArray< node > &  originalNodeTable 
)
private

Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalNodeTable.

void ogdf::ClusterGraph::deepCopy ( const ClusterGraph C,
Graph G,
ClusterArray< cluster > &  originalClusterTable,
NodeArray< node > &  originalNodeTable,
EdgeArray< edge > &  edgeCopy 
)
private

Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalNodeTable and edges in edgeCopy.

void ogdf::ClusterGraph::delCluster ( cluster  c)

Deletes cluster c.

All subclusters become children of parent cluster of c.

Precondition
c is not the root cluster.
cluster ogdf::ClusterGraph::doCreateCluster ( SList< node > &  nodes,
const cluster  parent,
int  clusterId = -1 
)
protected

Creates new cluster containing nodes in parameter list with index clusterid.

cluster ogdf::ClusterGraph::doCreateCluster ( SList< node > &  nodes,
SList< cluster > &  emptyCluster,
const cluster  parent,
int  clusterId = -1 
)
protected

Creates new cluster containing nodes in parameter list and stores resulting empty clusters in list, cluster has index clusterid.

virtual void ogdf::ClusterGraph::edgeAdded ( edge  )
inlineprotectedvirtual

Implementation of inherited method: Updates data if edge added.

Implements ogdf::GraphObserver.

Definition at line 694 of file ClusterGraph.h.

virtual void ogdf::ClusterGraph::edgeDeleted ( edge  )
inlineprotectedvirtual

Implementation of inherited method: Updates data if edge deleted.

Implements ogdf::GraphObserver.

Definition at line 692 of file ClusterGraph.h.

void ogdf::ClusterGraph::emptyClusters ( SList< cluster > &  emptyCluster,
SList< cluster > *  checkCluster = 0 
)

Returns the list of clusters that are empty or only contain empty clusters.

The list is constructed in an order that allows deletion and reinsertion. We never set rootcluster to be one of the empty clusters!! if checkClusters is given, only list elements are checked to allow efficient checking in the case that you know which clusters were recently changed (e.g. node reass.)

bool ogdf::ClusterGraph::emptyOnClusterDelete ( cluster  c)
inline

Returns true if cluster c has only one child and no nodes.

Definition at line 515 of file ClusterGraph.h.

bool ogdf::ClusterGraph::emptyOnNodeDelete ( cluster  c)
inline

Returns true if cluster c has only one node and no children.

Definition at line 508 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::firstCluster ( ) const
inline

Returns the first cluster in the list of all clusters.

Definition at line 522 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::firstPostOrderCluster ( ) const
inline

Returns the first cluster in the list of post ordered clusters.

Definition at line 526 of file ClusterGraph.h.

void ogdf::ClusterGraph::init ( const Graph G)

Clears all cluster data and then reinitializes the instance with underlying graph G.

void ogdf::ClusterGraph::initGraph ( const Graph G)
private
cluster ogdf::ClusterGraph::lastCluster ( ) const
inline

Returns the last cluster in the list of all cluster.

Definition at line 524 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::leftMostCluster ( cluster  c) const
protected

Leftmost cluster in subtree rooted at c, gets predecessor of subtree.

template<class LISTITERATOR >
void ogdf::ClusterGraph::makeAdjEntries ( cluster  c,
LISTITERATOR  start 
)
inline

Computes the adjacency entry list for cluster c.

Definition at line 603 of file ClusterGraph.h.

int ogdf::ClusterGraph::maxClusterIndex ( ) const
inline

Returns the maximal used cluster index.

Definition at line 328 of file ClusterGraph.h.

void ogdf::ClusterGraph::moveCluster ( cluster  c,
cluster  newParent 
)

Moves cluster c to a new parent newParent.

cluster ogdf::ClusterGraph::newCluster ( cluster  parent,
int  id = -1 
)

Inserts a new cluster; makes it a child of the cluster parent.

cluster ogdf::ClusterGraph::newCluster ( int  id)
private

Creates new cluster with given id, precondition: id not used.

cluster ogdf::ClusterGraph::newCluster ( )
private

Creates new cluster.

virtual void ogdf::ClusterGraph::nodeAdded ( node  v)
inlineprotectedvirtual

Implementation of inherited method: Updates data if node added.

Implements ogdf::GraphObserver.

Definition at line 687 of file ClusterGraph.h.

virtual void ogdf::ClusterGraph::nodeDeleted ( node  v)
inlineprotectedvirtual

Implementation of inherited method: Updates data if node deleted.

Implements ogdf::GraphObserver.

Definition at line 663 of file ClusterGraph.h.

int ogdf::ClusterGraph::numberOfClusters ( ) const
inline

Returns number of clusters.

Definition at line 385 of file ClusterGraph.h.

ogdf::ClusterGraph::operator const Graph & ( ) const
inline

Conversion to const Graph reference.

Definition at line 340 of file ClusterGraph.h.

ClusterGraph& ogdf::ClusterGraph::operator= ( const ClusterGraph C)

Assignment operator.

void ogdf::ClusterGraph::postOrder ( ) const
private

Create postorder information in cluster tree.

void ogdf::ClusterGraph::postOrder ( cluster  c,
SListPure< cluster > &  S 
) const
private
cluster ogdf::ClusterGraph::postOrderPredecessor ( cluster  c) const
protected

Computes new predecessor for SUBTREE at moved cluster c.

void ogdf::ClusterGraph::pullUpSubTree ( cluster  c)

Updates depth information in subtree after delCluster.

void ogdf::ClusterGraph::reassignNode ( node  v,
cluster  c 
)

Reassigns node v to cluster \ c.

ListIterator<ClusterArrayBase*> ogdf::ClusterGraph::registerArray ( ClusterArrayBase pClusterArray) const

Registers a cluster array.

ListIterator<ClusterGraphObserver*> ogdf::ClusterGraph::registerObserver ( ClusterGraphObserver pObserver) const

Registers a ClusterGraphObserver.

void ogdf::ClusterGraph::reInit ( Graph G)
inline

Clear cluster info structure, reinitializes with underlying graph G.

Definition at line 401 of file ClusterGraph.h.

virtual void ogdf::ClusterGraph::reInit ( )
inlineprotectedvirtual

Currently does nothing.

Implements ogdf::GraphObserver.

Definition at line 696 of file ClusterGraph.h.

void ogdf::ClusterGraph::reinitArrays ( )
private
void ogdf::ClusterGraph::reinitGraph ( const Graph G)
private

Reinitializes instance with graph G.

void ogdf::ClusterGraph::removeNodeAssignment ( node  v)
inlineprivate

Remove the assignment entries for nodes. Checks if node is currently not assigned.

Definition at line 714 of file ClusterGraph.h.

bool ogdf::ClusterGraph::representsCombEmbedding ( )

Checks the combinatorial cluster planar embedding.

cluster ogdf::ClusterGraph::rootCluster ( ) const
inline

Returns the root cluster.

Definition at line 376 of file ClusterGraph.h.

void ogdf::ClusterGraph::semiClear ( )

Clears all data but does not delete root cluster.

void ogdf::ClusterGraph::setUpdateDepth ( bool  b) const
inline

Turns automatic update of node depth values on or off.

Definition at line 410 of file ClusterGraph.h.

void ogdf::ClusterGraph::shallowCopy ( const ClusterGraph C)
private

Performs a copy of the cluster structure of C, the underlying graph stays the same.

int ogdf::ClusterGraph::treeDepth ( ) const
inline

Computes depth of cluster tree, running time O(C).

Definition at line 423 of file ClusterGraph.h.

void ogdf::ClusterGraph::unassignNode ( node  v)
private

Unassigns node v from its cluster.

void ogdf::ClusterGraph::unregisterArray ( ListIterator< ClusterArrayBase * >  it) const

Unregisters a cluster array.

void ogdf::ClusterGraph::unregisterObserver ( ListIterator< ClusterGraphObserver * >  it) const

Unregisters a ClusterGraphObserver.

void ogdf::ClusterGraph::updatePostOrder ( cluster  c,
cluster  oldParent,
cluster  newParent 
)
protected

Adjusts the post order structure for moved clusters.

Member Data Documentation

bool ogdf::ClusterGraph::m_adjAvailable
private

Definition at line 270 of file ClusterGraph.h.

bool ogdf::ClusterGraph::m_allowEmptyClusters
private

True if the adjacency list for each cluster is available.

Definition at line 271 of file ClusterGraph.h.

int ogdf::ClusterGraph::m_clusterArrayTableSize
private

The current table size of cluster arrays.

Definition at line 265 of file ClusterGraph.h.

int ogdf::ClusterGraph::m_clusterIdCount
private

The index assigned to the next created cluster.

Definition at line 264 of file ClusterGraph.h.

GraphList<ClusterElement> ogdf::ClusterGraph::m_clusters
private

The list of all clusters.

Definition at line 259 of file ClusterGraph.h.

bool ogdf::ClusterGraph::m_depthUpToDate
mutableprotected

Status of cluster depth information.

Definition at line 646 of file ClusterGraph.h.

NodeArray<ListIterator<node> > ogdf::ClusterGraph::m_itMap
private

Stories for every node its position within the children list of its cluster.

Definition at line 275 of file ClusterGraph.h.

int ogdf::ClusterGraph::m_lcaNumber
mutableprotected

Used to save last search run number for commoncluster.

Definition at line 637 of file ClusterGraph.h.

ClusterArray<int>* ogdf::ClusterGraph::m_lcaSearch
mutableprotected

Used to save last search run number for commoncluster.

Definition at line 636 of file ClusterGraph.h.

int ogdf::ClusterGraph::m_nClusters
private

The number of clusters.

Definition at line 263 of file ClusterGraph.h.

NodeArray<cluster> ogdf::ClusterGraph::m_nodeMap
private

Defines if empty clusters are deleted immediately if generated by operations.

Stores the cluster of each node.

Definition at line 273 of file ClusterGraph.h.

const Graph* ogdf::ClusterGraph::m_pGraph
private

The associated graph.

Definition at line 261 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::m_postOrderStart
mutableprivate

The first cluster in postorder.

Definition at line 267 of file ClusterGraph.h.

ListPure<ClusterArrayBase*> ogdf::ClusterGraph::m_regClusterArrays
mutableprivate

The registered cluster arrays.

Definition at line 277 of file ClusterGraph.h.

ListPure<ClusterGraphObserver*> ogdf::ClusterGraph::m_regObservers
mutableprivate

The registered graph observers.

Definition at line 278 of file ClusterGraph.h.

cluster ogdf::ClusterGraph::m_rootCluster
private

The root cluster.

Definition at line 268 of file ClusterGraph.h.

bool ogdf::ClusterGraph::m_updateDepth
mutableprotected

Depth of clusters is always updated if set to true.

Definition at line 645 of file ClusterGraph.h.

ClusterArray<cluster>* ogdf::ClusterGraph::m_vAncestor
mutableprotected

Used to save last search run number for commoncluster.

Definition at line 638 of file ClusterGraph.h.

ClusterArray<cluster>* ogdf::ClusterGraph::m_wAncestor
mutableprotected

Used to save last search run number for commoncluster.

Definition at line 639 of file ClusterGraph.h.


The documentation for this class was generated from the following file: