Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ClusterGraph Class Reference

Representation of clustered graphs. More...

#include <ogdf/cluster/ClusterGraph.h>

+ Inheritance diagram for ogdf::ClusterGraph:

Public Types

Iterators

These types are used for graph object iterators, which are returned by graph object containers like nodes and edges.

using cluster_iterator = internal::GraphIterator< cluster >
 Provides a bidirectional iterator to a cluster in a clustered graph. More...
 

Public Member Functions

Access methods
cluster rootCluster () const
 Returns the root cluster. More...
 
int numberOfClusters () const
 Returns the number of clusters. More...
 
int maxClusterIndex () const
 Returns the maximal used cluster index. More...
 
int clusterArrayTableSize () const
 Returns the table size of cluster arrays associated with this graph. More...
 
cluster clusterOf (node v) const
 Returns the cluster to which a node belongs. More...
 
int & clusterDepth (cluster c) const
 Returns depth of cluster c in cluster tree, starting with root depth 1. More...
 
cluster firstCluster () const
 Returns the first cluster in the list of all clusters. More...
 
cluster lastCluster () const
 Returns the last cluster in the list of all cluster. More...
 
cluster firstPostOrderCluster () const
 Returns the first cluster in the list of post ordered clusters. More...
 
template<class CLUSTERLIST >
void allClusters (CLUSTERLIST &clusterList) const
 Returns the list of all clusters in clusterList. More...
 
Modification methods
void clear ()
 Removes all clusters except for the root cluster. More...
 
void init (const Graph &G)
 Clears all cluster data and then reinitializes the instance with underlying graph G. More...
 
void clearClusterTree (cluster C)
 Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself. More...
 
cluster newCluster (cluster parent, int id=-1)
 Inserts a new cluster; makes it a child of the cluster parent. More...
 
cluster createEmptyCluster (const cluster parent=nullptr, int clusterId=-1)
 Creates an empty cluster with index clusterId and parent parent. More...
 
cluster createCluster (SList< node > &nodes, const cluster parent=nullptr)
 Creates a new cluster containing the nodes given by nodes; makes it a child of the cluster parent. More...
 
void delCluster (cluster c)
 Deletes cluster c. More...
 
void moveCluster (cluster c, cluster newParent)
 Moves cluster c to a new parent newParent. More...
 
void reassignNode (node v, cluster c)
 Reassigns node v to cluster c. More...
 
void reInit (Graph &G)
 Clear cluster info structure, reinitializes with underlying graph G. More...
 
template<class NODELIST >
void collapse (NODELIST &nodes, Graph &G)
 Collapses all nodes in the list nodes to the first node; multi-edges are removed. More...
 
Cluster tree queries
void setUpdateDepth (bool b) const
 Turns automatic update of node depth values on or off. More...
 
void pullUpSubTree (cluster c)
 Updates depth information in subtree after delCluster. More...
 
int treeDepth () const
 Computes depth of cluster tree, running time O(C). More...
 
void computeSubTreeDepth (cluster c) const
 Computes depth of cluster tree hanging at c. 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 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...
 
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...
 
void emptyClusters (SList< cluster > &emptyCluster, SList< cluster > *checkCluster=nullptr)
 Returns the list of clusters that are empty or only contain empty clusters. More...
 
bool emptyOnNodeDelete (cluster c)
 Returns true if cluster c has only one node and no children. More...
 
bool emptyOnClusterDelete (cluster c)
 Returns true if cluster c has only one child and no nodes. More...
 
Adjacent edges
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 LISTITERATOR >
void makeAdjEntries (cluster c, LISTITERATOR start)
 Computes the adjacency entry list for cluster c. More...
 
void adjAvailable (bool val)
 Sets the availability status of the adjacency entries. More...
 
Miscellaneous
bool representsCombEmbedding () const
 Checks the combinatorial cluster planar embedding. More...
 
Registering arrays and observers

These methods are used by ClusterArray or ClusterGraphObserver.

There should be no need to use them directly in user code.

ListIterator< ClusterArrayBase * > registerArray (ClusterArrayBase *pClusterArray) const
 Registers a cluster array. More...
 
void unregisterArray (ListIterator< ClusterArrayBase * > it) const
 Unregisters a cluster array. More...
 
void moveRegisterArray (ListIterator< ClusterArrayBase * > it, ClusterArrayBase *pClusterArray) const
 Move the registration it of a cluster array to pClusterArray (used with move semantics for cluster arrays). More...
 
ListIterator< ClusterGraphObserver * > registerObserver (ClusterGraphObserver *pObserver) const
 Registers a cluster graph observer. More...
 
void unregisterObserver (ListIterator< ClusterGraphObserver * > it) const
 Unregisters a cluster graph observer. 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

Functions inherited from GraphObserver (define how to cope with graph changes)
virtual void nodeDeleted (node v) override
 Implementation of inherited method: Updates data if node deleted. More...
 
virtual void nodeAdded (node v) override
 Implementation of inherited method: Updates data if node added. More...
 
virtual void edgeDeleted (edge) override
 Implementation of inherited method: Updates data if edge deleted. More...
 
virtual void edgeAdded (edge) override
 Implementation of inherited method: Updates data if edge added. More...
 
virtual void reInit () override
 Currently does nothing. More...
 
virtual void cleared () override
 Clears cluster data without deleting root when underlying graphs' clear method is called. More...
 

Private Member Functions

void assignNode (node v, cluster C)
 Assigns node v to cluster C (v not yet assigned!). More...
 
void clearClusterTree (cluster c, List< node > &attached)
 
void constructClusterTree (const ClusterGraph &C, const Graph &G, ClusterArray< cluster > &originalClusterTable, std::function< node(node)> nodeMap=[](node v) { return v;})
 Constructs a cluster tree. More...
 
void deepCopy (const ClusterGraph &C, Graph &G)
 Perform a deep copy on C, C's underlying graph is copied into G. More...
 
void deepCopy (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
 Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalNodeTable. More...
 
void deepCopy (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
 Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalNodeTable and edges in edgeCopy. More...
 
template<typename T >
void fillEmptyClusters (SList< cluster > &emptyCluster, const T &clusterList) const
 Fills emptyCluster with empty, non-root clusters from clusterList. More...
 
void initGraph (const Graph &G)
 
cluster newCluster ()
 Creates new cluster. More...
 
cluster newCluster (int id)
 Creates new cluster with given id, precondition: id not used. More...
 
void postOrder () const
 Create postorder information in cluster tree. More...
 
void postOrder (cluster c, SListPure< cluster > &S) const
 
void recurseClearClusterTreeOnChildren (cluster c, List< node > &attached)
 Clears children of a cluster, used by recursive clearClusterTree. More...
 
void reinitArrays ()
 
void reinitGraph (const Graph &G)
 Reinitializes instance with graph G. More...
 
void removeNodeAssignment (node v)
 Remove the assignment entries for nodes. Checks if node v is currently not assigned. More...
 
void shallowCopy (const ClusterGraph &C)
 Performs a copy of the cluster structure of C, the underlying graph stays the same. More...
 
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...
 
NodeArray< ListIterator< node > > m_itMap
 
std::mutex m_mutexRegArrays
 The critical section for protecting shared acces to register/unregister methods. 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...
 

Graph object containers

These containers maintain the nodes and edges of the graph, and provide node and edge iterators.

internal::GraphObjectContainer< ClusterElementclusters
 The container containing all cluster objects. More...
 
 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)
 Copies the underlying graph of C into G and constructs a copy of C associated with G. More...
 
 ClusterGraph (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
 Copies the underlying graph of C into G and constructs a copy of C associated with G. More...
 
 ClusterGraph (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
 Copies the underlying graph of C into G and constructs a copy of C associated with G. More...
 
virtual ~ClusterGraph ()
 Destructor. More...
 

Operators and conversion

ClusterArray< int > * m_lcaSearch
 Used to save last search run number for commoncluster. More...
 
int m_lcaNumber
 Used to save last search run number for commoncluster. 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...
 
bool m_updateDepth
 Depth of clusters is always updated if set to true. More...
 
bool m_depthUpToDate
 Status of cluster depth information. More...
 
 operator const Graph & () const
 Conversion to const Graph reference (to underlying graph). More...
 
const GraphconstGraph () const
 Returns a reference to the underlying graph. More...
 
ClusterGraphoperator= (const ClusterGraph &C)
 Assignment operator. More...
 
cluster doCreateCluster (SList< node > &nodes, const cluster parent, int clusterId=-1)
 Creates new cluster containing nodes in parameter list with index clusterId. More...
 
cluster doCreateCluster (SList< node > &nodes, SList< cluster > &emptyCluster, const cluster parent, int clusterId=-1)
 Creates new cluster containing nodes in parameter list and stores resulting empty clusters in list, cluster has index clusterId. More...
 
void doClear ()
 Clears all cluster data. More...
 
void copyLCA (const ClusterGraph &C)
 Copies lowest common ancestor info to copy of clustered graph. More...
 
void updatePostOrder (cluster c, cluster oldParent, cluster newParent)
 Adjusts the post order structure for moved clusters. More...
 
cluster postOrderPredecessor (cluster c) const
 Computes new predecessor for subtree at moved cluster c (nullptr if c is the root). More...
 
cluster leftMostCluster (cluster c) const
 Leftmost cluster in subtree rooted at c, gets predecessor of subtree. More...
 

Additional Inherited Members

- Protected Attributes inherited from ogdf::GraphObserver
ListIterator< GraphObserver * > m_itGList
 watched graph More...
 
const Graphm_pGraph
 

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 291 of file ClusterGraph.h.

Member Typedef Documentation

◆ cluster_iterator

Provides a bidirectional iterator to a cluster in a clustered graph.

Definition at line 325 of file ClusterGraph.h.

Constructor & Destructor Documentation

◆ ClusterGraph() [1/6]

ogdf::ClusterGraph::ClusterGraph ( )

Creates a cluster graph associated with no graph.

After using this constructor, you will have to initialize it with a graph before you can use it, see init().

◆ ClusterGraph() [2/6]

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

Creates a cluster graph associated with graph G.

All nodes in G are assigned to the root cluster.

◆ ClusterGraph() [3/6]

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

Copy constructor.

The copy constructor only creates a copy of the cluster tree structure, not of the underlying graph. Consequently, this cluster graph and C will be associated with the same graph instance.

◆ ClusterGraph() [4/6]

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

Copies the underlying graph of C into G and constructs a copy of C associated with G.

The created cluster tree is a copy of C except for the associated nodes, which are the newly created copies in G.

◆ ClusterGraph() [5/6]

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

Copies the underlying graph of C into G and constructs a copy of C associated with G.

The created cluster tree is a copy of C except for the associated nodes, which are the newly created copies in G. Stores the new copies of the original nodes and clusters in the arrays originalNodeTable and originalClusterTable.

◆ ClusterGraph() [6/6]

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

Copies the underlying graph of C into G and constructs a copy of C associated with G.

The created cluster tree is a copy of C except for the associated nodes, which are the newly created copies in G. Stores the new copies of the original nodes, edges, and clusters in the arrays originalNodeTable, edgeCopy, and originalClusterTable.

◆ ~ClusterGraph()

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

Destructor.

Member Function Documentation

◆ adjAvailable()

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

Sets the availability status of the adjacency entries.

Definition at line 683 of file ClusterGraph.h.

◆ adjEdges()

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 647 of file ClusterGraph.h.

◆ adjEntries()

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 660 of file ClusterGraph.h.

◆ allClusters()

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

Returns the list of all clusters in clusterList.

Definition at line 445 of file ClusterGraph.h.

◆ assignNode()

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

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

◆ clear()

void ogdf::ClusterGraph::clear ( )

Removes all clusters except for the root cluster.

◆ clearClusterTree() [1/2]

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

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

◆ clearClusterTree() [2/2]

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

◆ cleared()

virtual void ogdf::ClusterGraph::cleared ( )
inlineoverrideprotectedvirtual

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

Implements ogdf::GraphObserver.

Definition at line 798 of file ClusterGraph.h.

◆ clusterArrayTableSize()

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

Returns the table size of cluster arrays associated with this graph.

Definition at line 409 of file ClusterGraph.h.

◆ clusterDepth()

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

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

Definition at line 419 of file ClusterGraph.h.

◆ clusterOf()

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

Returns the cluster to which a node belongs.

Definition at line 412 of file ClusterGraph.h.

◆ collapse()

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

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

Definition at line 505 of file ClusterGraph.h.

◆ commonCluster() [1/2]

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

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

Precondition
v and w are nodes in the graph.

Definition at line 574 of file ClusterGraph.h.

◆ commonCluster() [2/2]

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

Returns lowest common cluster of nodes in list nodes.

◆ commonClusterAncestorsPath()

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.

◆ commonClusterLastAncestors()

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

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

Definition at line 580 of file ClusterGraph.h.

◆ commonClusterPath()

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

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

The list eL is directed from v to w.

Definition at line 594 of file ClusterGraph.h.

◆ computeSubTreeDepth()

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

Computes depth of cluster tree hanging at c.

◆ constGraph()

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

Returns a reference to the underlying graph.

Definition at line 733 of file ClusterGraph.h.

◆ constructClusterTree()

void ogdf::ClusterGraph::constructClusterTree ( const ClusterGraph C,
const Graph G,
ClusterArray< cluster > &  originalClusterTable,
std::function< node(node)>  nodeMap = [](node v) { return v;} 
)
private

Constructs a cluster tree.

◆ copyLCA()

void ogdf::ClusterGraph::copyLCA ( const ClusterGraph C)
protected

Copies lowest common ancestor info to copy of clustered graph.

◆ createCluster()

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

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.

◆ createEmptyCluster()

cluster ogdf::ClusterGraph::createEmptyCluster ( const cluster  parent = nullptr,
int  clusterId = -1 
)

Creates an empty cluster with index clusterId and parent parent.

◆ deepCopy() [1/3]

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

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

◆ deepCopy() [2/3]

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.

◆ deepCopy() [3/3]

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.

◆ delCluster()

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.

◆ doClear()

void ogdf::ClusterGraph::doClear ( )
protected

Clears all cluster data.

◆ doCreateCluster() [1/2]

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.

◆ doCreateCluster() [2/2]

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.

◆ edgeAdded()

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

Implementation of inherited method: Updates data if edge added.

Implements ogdf::GraphObserver.

Definition at line 792 of file ClusterGraph.h.

◆ edgeDeleted()

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

Implementation of inherited method: Updates data if edge deleted.

Implements ogdf::GraphObserver.

Definition at line 789 of file ClusterGraph.h.

◆ emptyClusters()

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

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.)

◆ emptyOnClusterDelete()

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

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

Definition at line 631 of file ClusterGraph.h.

◆ emptyOnNodeDelete()

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

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

Definition at line 622 of file ClusterGraph.h.

◆ fillEmptyClusters()

template<typename T >
void ogdf::ClusterGraph::fillEmptyClusters ( SList< cluster > &  emptyCluster,
const T &  clusterList 
) const
inlineprivate

Fills emptyCluster with empty, non-root clusters from clusterList.

Definition at line 809 of file ClusterGraph.h.

◆ firstCluster()

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

Returns the first cluster in the list of all clusters.

Definition at line 432 of file ClusterGraph.h.

◆ firstPostOrderCluster()

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

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

Definition at line 438 of file ClusterGraph.h.

◆ init()

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

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

◆ initGraph()

void ogdf::ClusterGraph::initGraph ( const Graph G)
private

◆ lastCluster()

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

Returns the last cluster in the list of all cluster.

Definition at line 435 of file ClusterGraph.h.

◆ leftMostCluster()

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

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

◆ makeAdjEntries()

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

Computes the adjacency entry list for cluster c.

Definition at line 671 of file ClusterGraph.h.

◆ maxClusterIndex()

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

Returns the maximal used cluster index.

Definition at line 406 of file ClusterGraph.h.

◆ moveCluster()

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

Moves cluster c to a new parent newParent.

◆ moveRegisterArray()

void ogdf::ClusterGraph::moveRegisterArray ( ListIterator< ClusterArrayBase * >  it,
ClusterArrayBase pClusterArray 
) const

Move the registration it of a cluster array to pClusterArray (used with move semantics for cluster arrays).

◆ newCluster() [1/3]

cluster ogdf::ClusterGraph::newCluster ( )
private

Creates new cluster.

◆ newCluster() [2/3]

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

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

◆ newCluster() [3/3]

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

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

◆ nodeAdded()

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

Implementation of inherited method: Updates data if node added.

Implements ogdf::GraphObserver.

Definition at line 784 of file ClusterGraph.h.

◆ nodeDeleted()

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

Implementation of inherited method: Updates data if node deleted.

Implements ogdf::GraphObserver.

◆ numberOfClusters()

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

Returns the number of clusters.

Definition at line 403 of file ClusterGraph.h.

◆ operator const Graph &()

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

Conversion to const Graph reference (to underlying graph).

Definition at line 730 of file ClusterGraph.h.

◆ operator=()

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

Assignment operator.

◆ postOrder() [1/2]

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

Create postorder information in cluster tree.

◆ postOrder() [2/2]

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

◆ postOrderPredecessor()

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

Computes new predecessor for subtree at moved cluster c (nullptr if c is the root).

◆ pullUpSubTree()

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

Updates depth information in subtree after delCluster.

◆ reassignNode()

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

Reassigns node v to cluster c.

◆ recurseClearClusterTreeOnChildren()

void ogdf::ClusterGraph::recurseClearClusterTreeOnChildren ( cluster  c,
List< node > &  attached 
)
inlineprivate

Clears children of a cluster, used by recursive clearClusterTree.

Definition at line 822 of file ClusterGraph.h.

◆ registerArray()

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

Registers a cluster array.

◆ registerObserver()

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

Registers a cluster graph observer.

◆ reInit() [1/2]

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

Currently does nothing.

Implements ogdf::GraphObserver.

Definition at line 795 of file ClusterGraph.h.

◆ reInit() [2/2]

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

Clear cluster info structure, reinitializes with underlying graph G.

Definition at line 499 of file ClusterGraph.h.

◆ reinitArrays()

void ogdf::ClusterGraph::reinitArrays ( )
private

◆ reinitGraph()

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

Reinitializes instance with graph G.

◆ removeNodeAssignment()

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

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

Definition at line 844 of file ClusterGraph.h.

◆ representsCombEmbedding()

bool ogdf::ClusterGraph::representsCombEmbedding ( ) const

Checks the combinatorial cluster planar embedding.

◆ rootCluster()

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

Returns the root cluster.

Definition at line 400 of file ClusterGraph.h.

◆ setUpdateDepth()

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

Turns automatic update of node depth values on or off.

Definition at line 550 of file ClusterGraph.h.

◆ shallowCopy()

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

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

◆ treeDepth()

int ogdf::ClusterGraph::treeDepth ( ) const

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

◆ unassignNode()

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

Unassigns node v from its cluster.

◆ unregisterArray()

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

Unregisters a cluster array.

◆ unregisterObserver()

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

Unregisters a cluster graph observer.

◆ updatePostOrder()

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

Adjusts the post order structure for moved clusters.

Member Data Documentation

◆ clusters

internal::GraphObjectContainer<ClusterElement> ogdf::ClusterGraph::clusters

The container containing all cluster objects.

Definition at line 336 of file ClusterGraph.h.

◆ m_adjAvailable

bool ogdf::ClusterGraph::m_adjAvailable
private

Definition at line 301 of file ClusterGraph.h.

◆ m_allowEmptyClusters

bool ogdf::ClusterGraph::m_allowEmptyClusters
private

True if the adjacency list for each cluster is available.

Definition at line 302 of file ClusterGraph.h.

◆ m_clusterArrayTableSize

int ogdf::ClusterGraph::m_clusterArrayTableSize
private

The current table size of cluster arrays.

Definition at line 296 of file ClusterGraph.h.

◆ m_clusterIdCount

int ogdf::ClusterGraph::m_clusterIdCount
private

The index assigned to the next created cluster.

Definition at line 295 of file ClusterGraph.h.

◆ m_depthUpToDate

bool ogdf::ClusterGraph::m_depthUpToDate
mutableprotected

Status of cluster depth information.

Definition at line 747 of file ClusterGraph.h.

◆ m_itMap

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

Definition at line 306 of file ClusterGraph.h.

◆ m_lcaNumber

int ogdf::ClusterGraph::m_lcaNumber
mutableprotected

Used to save last search run number for commoncluster.

Definition at line 742 of file ClusterGraph.h.

◆ m_lcaSearch

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

Used to save last search run number for commoncluster.

Definition at line 741 of file ClusterGraph.h.

◆ m_mutexRegArrays

std::mutex ogdf::ClusterGraph::m_mutexRegArrays
mutableprivate

The critical section for protecting shared acces to register/unregister methods.

Definition at line 312 of file ClusterGraph.h.

◆ m_nodeMap

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

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

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

Definition at line 304 of file ClusterGraph.h.

◆ m_pGraph

const Graph* ogdf::ClusterGraph::m_pGraph
private

The associated graph.

Definition at line 293 of file ClusterGraph.h.

◆ m_postOrderStart

cluster ogdf::ClusterGraph::m_postOrderStart
mutableprivate

The first cluster in postorder.

Definition at line 298 of file ClusterGraph.h.

◆ m_regClusterArrays

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

The registered cluster arrays.

Definition at line 308 of file ClusterGraph.h.

◆ m_regObservers

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

The registered graph observers.

Definition at line 309 of file ClusterGraph.h.

◆ m_rootCluster

cluster ogdf::ClusterGraph::m_rootCluster
private

The root cluster.

Definition at line 299 of file ClusterGraph.h.

◆ m_updateDepth

bool ogdf::ClusterGraph::m_updateDepth
mutableprotected

Depth of clusters is always updated if set to true.

Definition at line 746 of file ClusterGraph.h.

◆ m_vAncestor

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

Used to save last search run number for commoncluster.

Definition at line 743 of file ClusterGraph.h.

◆ m_wAncestor

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

Used to save last search run number for commoncluster.

Definition at line 744 of file ClusterGraph.h.


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