ogdf::ClusterGraph Class Reference

Representation of clustered graphs. More...

#include <ClusterGraph.h>

Inheritance diagram for ogdf::ClusterGraph:

List of all members.

Public Member Functions

ClusterGraph ()

Creates a cluster graph associated with no graph.

ClusterGraph (const Graph &G)

Creates a cluster graph associated with graph G.

ClusterGraph (const ClusterGraph &C)

Copy constructor.

ClusterGraph (const ClusterGraph &C, Graph &G)

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

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

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

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.

virtual ~ClusterGraph ()

int maxClusterIndex () const

Returns the maximal used cluster index.

void clear ()

Clears all cluster data.

void semiClear ()

Clears all data but does not delete root cluster.

void init (const Graph &G)

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

operator const Graph & () const

Conversion to const Graph reference.

ClusterGraph & operator= (const ClusterGraph &C)

Assignment operator.

void clearClusterTree (cluster C)

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

const Graph & getGraph () const

Returns a reference to the underlying graph.

cluster newCluster (cluster parent, int id=-1)

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

cluster createEmptyCluster (const cluster parent=0, int clusterId=-1)

Creates an empty cluster with index clusterId and parent parent.

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

Creates a new cluster containing the nodes given by nodes.

void delCluster (cluster c)

Deletes cluster c.

cluster rootCluster () const

Returns the root cluster.

cluster clusterOf (node v) const

Returns the cluster to which a node belongs.

int numberOfClusters () const

Returns number of clusters.

int clusterIdCount () const

Returns upper bound for cluster indices.

int clusterArrayTableSize () const

Returns table size of cluster arrays associated with this graph.

void moveCluster (cluster c, cluster newParent)

Moves cluster c to a new parent newParent.

void reassignNode (node v, cluster c)

Reassigns node v to cluster \ c.

void reInit (Graph &G)

Clear cluster info structure, reinitializes with underlying graph G.

void setUpdateDepth (bool b) const

Turns automatic update of node depth values on or off.

void pullUpSubTree (cluster c)

Updates depth information in subtree after delCluster.

int treeDepth () const

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

void computeSubTreeDepth (cluster c) const

Computes depth of cluster tree hanging at c.

int & clusterDepth (cluster c) const

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

cluster commonCluster (SList< node > &nodes)

Returns lowest common cluster of nodes in list nodes.

cluster commonCluster (node v, node w) const

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

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.

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

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

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.

ListIterator< ClusterArrayBase * > registerArray (ClusterArrayBase *pClusterArray) const

Registers a cluster array.

void unregisterArray (ListIterator< ClusterArrayBase * > it) const

Unregisters a cluster array.

ListIterator
< ClusterGraphObserver * > registerObserver (ClusterGraphObserver *pObserver) const

Registers a ClusterGraphObserver.

void unregisterObserver (ListIterator< ClusterGraphObserver * > it) const

Unregisters a ClusterGraphObserver.

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

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

bool emptyOnNodeDelete (cluster c)

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

bool emptyOnClusterDelete (cluster c)

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

cluster firstCluster () const

Returns the first cluster in the list of all clusters.

cluster lastCluster () const

Returns the last cluster in the list of all cluster.

cluster firstPostOrderCluster () const

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

template<class CLUSTERLIST>

void allNodes (CLUSTERLIST &clusters) const

Returns the list of all clusters in clusters.

template<class NODELIST>

void collaps (NODELIST &nodes, Graph &G)

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

template<class EDGELIST>

void adjEdges (cluster c, EDGELIST &edges) const

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

template<class ADJLIST>

void adjEntries (cluster c, ADJLIST &entries) const

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

template<class LISTITERATOR>

void makeAdjEntries (cluster c, LISTITERATOR start)

Computes the adjacency entry list for cluster c.

void writeGML (const char *fileName)

Writes the cluster graph in GML format to file fileName.

void writeGML (ostream &os)

Writes the cluster graph in GML format to output stream os.

bool consistencyCheck ()

Checks the consistency of the data structure.

bool representsCombEmbedding ()

Checks the combinatorial cluster planar embedding.

void adjAvailable (bool val)

Sets the availability status of the adjacency entries.

Protected Member Functions

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)

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

Copies lowest common ancestor info to copy pf clustered graph.

void updatePostOrder (cluster c, cluster oldParent, cluster newParent)

Adjusts the post order structure for moved clusters.

cluster postOrderPredecessor (cluster c) const

Computes new predecessor for SUBTREE at moved cluster c.

cluster leftMostCluster (cluster c) const

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

virtual void nodeDeleted (node v)

Implementation of inherited method: Updates data if node deleted.

virtual void nodeAdded (node v)

Implementation of inherited method: Updates data if node added.

virtual void edgeDeleted (edge)

Implementation of inherited method: Updates data if edge deleted.

virtual void edgeAdded (edge)

Implementation of inherited method: Updates data if edge added.

virtual void reInit ()

Currently does nothing.

virtual void cleared ()

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

Protected Attributes

ClusterArray< int > * m_lcaSearch

Used to save last search run number for commoncluster.

int m_lcaNumber

Used to save last search run number for commoncluster.

ClusterArray< cluster > * m_vAncestor

Used to save last search run number for commoncluster.

ClusterArray< cluster > * m_wAncestor

Used to save last search run number for commoncluster.

bool m_updateDepth

Depth of clusters is always updated if set to true.

bool m_depthUpToDate

Status of cluster depth information.

Private Member Functions

void assignNode (node v, cluster C)

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

void unassignNode (node v)

Unassigns node v from its cluster.

void removeNodeAssignment (node v)

void shallowCopy (const ClusterGraph &C)

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 clearClusterTree (cluster c, List< node > &attached)

void initGraph (const Graph &G)

void reinitGraph (const Graph &G)

Reinitializes instance with graph G.

cluster newCluster (int id)

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

cluster newCluster ()

Creates new cluster.

void postOrder () const

Create postorder information in cluster tree.

void checkPostOrder () const

Check postorder information in cluster tree.

void postOrder (cluster c, SListPure< cluster > &S) const

void reinitArrays ()

void writeCluster (ostream &os, NodeArray< int > &nId, ClusterArray< int > &cId, int &nextId, cluster c, String ttt)

Recursively write the cluster structure in GML.

void writeGraphWinCluster (ostream &os, NodeArray< int > &nId, NodeArray< String > &nStr, ClusterArray< int > &cId, ClusterArray< String > &cStr, int &nextId, cluster c, String ttt)

Recursively write the cluster structure in GraphWin GML.

Private Attributes

GraphList< ClusterElement > m_clusters

The list of all clusters.

const Graph * m_pGraph

The associated graph.

int m_nClusters

The number of clusters.

int m_clusterIdCount

The index assigned to the next created cluster.

int m_clusterArrayTableSize

The current table size of cluster arrays.

cluster m_postOrderStart

The first cluster in postorder.

cluster m_rootCluster

The root cluster.

bool m_adjAvailable

bool m_allowEmptyClusters

True if the adjacency list for each cluster is available.

NodeArray< cluster > m_nodeMap

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

NodeArray< ListIterator< node > > m_itMap

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

ListPure< ClusterArrayBase * > m_regClusterArrays

The registered cluster arrays.

ListPure< ClusterGraphObserver * > m_regObservers

The registered graph observers.

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 256 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

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

Returns the maximal used cluster index.

Definition at line 327 of file ClusterGraph.h.

void ogdf::ClusterGraph::clear ( )

Clears all cluster data.

void ogdf::ClusterGraph::semiClear ( )

Clears all data but does not delete root cluster.

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

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

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

Conversion to const Graph reference.

Definition at line 339 of file ClusterGraph.h.

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

Assignment operator.

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

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

const Graph& ogdf::ClusterGraph::getGraph ( ) const [inline]

Returns a reference to the underlying graph.

Reimplemented from ogdf::GraphObserver.

Definition at line 348 of file ClusterGraph.h.

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

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

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

Creates an empty cluster with index clusterId and parent parent.

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

Creates a new cluster containing the nodes given by nodes.

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:

	nodes	are the nodes that will be reassigned to the new cluster.
	parent	is the parent of the cluster.

Returns:: the created cluster.

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::rootCluster ( ) const [inline]

Returns the root cluster.

Definition at line 375 of file ClusterGraph.h.

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

Returns the cluster to which a node belongs.

Definition at line 378 of file ClusterGraph.h.

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

Returns number of clusters.

Definition at line 384 of file ClusterGraph.h.

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

Returns upper bound for cluster indices.

Definition at line 386 of file ClusterGraph.h.

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

Returns table size of cluster arrays associated with this graph.

Definition at line 389 of file ClusterGraph.h.

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

Moves cluster c to a new parent newParent.

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

Reassigns node v to cluster \ c.

void ogdf::ClusterGraph::reInit ( Graph & G ) [inline]

Clear cluster info structure, reinitializes with underlying graph G.

Definition at line 400 of file ClusterGraph.h.

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

Turns automatic update of node depth values on or off.

Definition at line 409 of file ClusterGraph.h.

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

Updates depth information in subtree after delCluster.

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

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

Definition at line 422 of file ClusterGraph.h.

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

Computes depth of cluster tree hanging at c.

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

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

Definition at line 442 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::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.

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.

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

Registers a cluster array.

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

Unregisters a cluster array.

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

Registers a ClusterGraphObserver.

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

Unregisters a ClusterGraphObserver.

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::emptyOnNodeDelete ( cluster c ) [inline]

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

Definition at line 520 of file ClusterGraph.h.

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

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

Definition at line 527 of file ClusterGraph.h.

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

Returns the first cluster in the list of all clusters.

Definition at line 534 of file ClusterGraph.h.

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

Returns the last cluster in the list of all cluster.

Definition at line 536 of file ClusterGraph.h.

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

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

Definition at line 538 of file ClusterGraph.h.

template<class CLUSTERLIST>

void ogdf::ClusterGraph::allNodes ( CLUSTERLIST & clusters ) const [inline]

Returns the list of all clusters in clusters.

Definition at line 545 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 553 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 591 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 603 of file ClusterGraph.h.

template<class LISTITERATOR>

void ogdf::ClusterGraph::makeAdjEntries	(	cluster	c,
		LISTITERATOR	start
	)			`[inline]`

Computes the adjacency entry list for cluster c.

Definition at line 615 of file ClusterGraph.h.

void ogdf::ClusterGraph::writeGML ( const char * fileName )

Writes the cluster graph in GML format to file fileName.

void ogdf::ClusterGraph::writeGML ( ostream & os )

Writes the cluster graph in GML format to output stream os.

bool ogdf::ClusterGraph::consistencyCheck ( )

Checks the consistency of the data structure.

bool ogdf::ClusterGraph::representsCombEmbedding ( )

Checks the combinatorial cluster planar embedding.

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

Sets the availability status of the adjacency entries.

Definition at line 644 of file ClusterGraph.h.

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.

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

Copies lowest common ancestor info to copy pf clustered graph.

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

Adjusts the post order structure for moved clusters.

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

Computes new predecessor for SUBTREE at moved cluster c.

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

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

virtual void ogdf::ClusterGraph::nodeDeleted ( node v ) [inline, protected, virtual]

Implementation of inherited method: Updates data if node deleted.

Implements ogdf::GraphObserver.

Definition at line 684 of file ClusterGraph.h.

virtual void ogdf::ClusterGraph::nodeAdded ( node v ) [inline, protected, virtual]

Implementation of inherited method: Updates data if node added.

Implements ogdf::GraphObserver.

Definition at line 708 of file ClusterGraph.h.

virtual void ogdf::ClusterGraph::edgeDeleted ( edge ) [inline, protected, virtual]

Implementation of inherited method: Updates data if edge deleted.

Implements ogdf::GraphObserver.

Definition at line 713 of file ClusterGraph.h.

virtual void ogdf::Clus


Public Member Functions
	ClusterGraph ()
	Creates a cluster graph associated with no graph.
	ClusterGraph (const Graph &G)
	Creates a cluster graph associated with graph G.
	ClusterGraph (const ClusterGraph &C)
	Copy constructor.
	ClusterGraph (const ClusterGraph &C, Graph &G)
	Constructs a clustered graph that is a copy of clustered graph C.
	ClusterGraph (const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
	Constructs a clustered graph that is a copy of clustered graph C.
	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.
virtual	~ClusterGraph ()
int	maxClusterIndex () const
	Returns the maximal used cluster index.
void	clear ()
	Clears all cluster data.
void	semiClear ()
	Clears all data but does not delete root cluster.
void	init (const Graph &G)
	Clears all cluster data and then reinitializes the instance with underlying graph G.
	operator const Graph & () const
	Conversion to const Graph reference.
ClusterGraph &	operator= (const ClusterGraph &C)
	Assignment operator.
void	clearClusterTree (cluster C)
	Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself.
const Graph &	getGraph () const
	Returns a reference to the underlying graph.
cluster	newCluster (cluster parent, int id=-1)
	Inserts a new cluster; makes it a child of the cluster parent.
cluster	createEmptyCluster (const cluster parent=0, int clusterId=-1)
	Creates an empty cluster with index clusterId and parent parent.
cluster	createCluster (SList< node > &nodes, const cluster parent=0)
	Creates a new cluster containing the nodes given by nodes.
void	delCluster (cluster c)
	Deletes cluster c.
cluster	rootCluster () const
	Returns the root cluster.
cluster	clusterOf (node v) const
	Returns the cluster to which a node belongs.
int	numberOfClusters () const
	Returns number of clusters.
int	clusterIdCount () const
	Returns upper bound for cluster indices.
int	clusterArrayTableSize () const
	Returns table size of cluster arrays associated with this graph.
void	moveCluster (cluster c, cluster newParent)
	Moves cluster c to a new parent newParent.
void	reassignNode (node v, cluster c)
	Reassigns node v to cluster \ c.
void	reInit (Graph &G)
	Clear cluster info structure, reinitializes with underlying graph G.
void	setUpdateDepth (bool b) const
	Turns automatic update of node depth values on or off.
void	pullUpSubTree (cluster c)
	Updates depth information in subtree after delCluster.
int	treeDepth () const
	Computes depth of cluster tree, running time O(C).
void	computeSubTreeDepth (cluster c) const
	Computes depth of cluster tree hanging at c.
int &	clusterDepth (cluster c) const
	Returns depth of cluster c in cluster tree, starting with root depth 1.
cluster	commonCluster (SList< node > &nodes)
	Returns lowest common cluster of nodes in list nodes.
cluster	commonCluster (node v, node w) const
	Returns the lowest common cluster of v and w in the cluster tree.
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.
cluster	commonClusterPath (node v, node w, List< cluster > &eL) const
	Returns lca of v and w and stores corresponding path in eL.
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.
ListIterator< ClusterArrayBase * >	registerArray (ClusterArrayBase *pClusterArray) const
	Registers a cluster array.
void	unregisterArray (ListIterator< ClusterArrayBase * > it) const
	Unregisters a cluster array.
ListIterator < ClusterGraphObserver * >	registerObserver (ClusterGraphObserver *pObserver) const
	Registers a ClusterGraphObserver.
void	unregisterObserver (ListIterator< ClusterGraphObserver * > it) const
	Unregisters a ClusterGraphObserver.
void	emptyClusters (SList< cluster > &emptyCluster, SList< cluster > *checkCluster=0)
	Returns the list of clusters that are empty or only contain empty clusters.
bool	emptyOnNodeDelete (cluster c)
	Returns true if cluster c has only one node and no children.
bool	emptyOnClusterDelete (cluster c)
	Returns true if cluster c has only one child and no nodes.
cluster	firstCluster () const
	Returns the first cluster in the list of all clusters.
cluster	lastCluster () const
	Returns the last cluster in the list of all cluster.
cluster	firstPostOrderCluster () const
	Returns the first cluster in the list of post ordered clusters.
template<class CLUSTERLIST>
void	allNodes (CLUSTERLIST &clusters) const
	Returns the list of all clusters in clusters.
template<class NODELIST>
void	collaps (NODELIST &nodes, Graph &G)
	Collapses all nodes in the list nodes to the first node; multi-edges are removed.
template<class EDGELIST>
void	adjEdges (cluster c, EDGELIST &edges) const
	Returns the list of all edges adjacent to cluster c in edges.
template<class ADJLIST>
void	adjEntries (cluster c, ADJLIST &entries) const
	Returns the list of all adjacency entries adjacent to cluster c in entries.
template<class LISTITERATOR>
void	makeAdjEntries (cluster c, LISTITERATOR start)
	Computes the adjacency entry list for cluster c.
void	writeGML (const char *fileName)
	Writes the cluster graph in GML format to file fileName.
void	writeGML (ostream &os)
	Writes the cluster graph in GML format to output stream os.
bool	consistencyCheck ()
	Checks the consistency of the data structure.
bool	representsCombEmbedding ()
	Checks the combinatorial cluster planar embedding.
void	adjAvailable (bool val)
	Sets the availability status of the adjacency entries.
Protected Member Functions
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)
void	copyLCA (const ClusterGraph &C, ClusterArray< cluster > *clusterCopy=0)
	Copies lowest common ancestor info to copy pf clustered graph.
void	updatePostOrder (cluster c, cluster oldParent, cluster newParent)
	Adjusts the post order structure for moved clusters.
cluster	postOrderPredecessor (cluster c) const
	Computes new predecessor for SUBTREE at moved cluster c.
cluster	leftMostCluster (cluster c) const
	Leftmost cluster in subtree rooted at c, gets predecessor of subtree.
virtual void	nodeDeleted (node v)
	Implementation of inherited method: Updates data if node deleted.
virtual void	nodeAdded (node v)
	Implementation of inherited method: Updates data if node added.
virtual void	edgeDeleted (edge)
	Implementation of inherited method: Updates data if edge deleted.
virtual void	edgeAdded (edge)
	Implementation of inherited method: Updates data if edge added.
virtual void	reInit ()
	Currently does nothing.
virtual void	cleared ()
	Clears cluster data without deleting root when underlying graphs' clear method is called.
Protected Attributes
ClusterArray< int > *	m_lcaSearch
	Used to save last search run number for commoncluster.
int	m_lcaNumber
	Used to save last search run number for commoncluster.
ClusterArray< cluster > *	m_vAncestor
	Used to save last search run number for commoncluster.
ClusterArray< cluster > *	m_wAncestor
	Used to save last search run number for commoncluster.
bool	m_updateDepth
	Depth of clusters is always updated if set to true.
bool	m_depthUpToDate
	Status of cluster depth information.
Private Member Functions
void	assignNode (node v, cluster C)
	Assigns node v to cluster c (v not yet assigned!).
void	unassignNode (node v)
	Unassigns node v from its cluster.
void	removeNodeAssignment (node v)
void	shallowCopy (const ClusterGraph &C)
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	clearClusterTree (cluster c, List< node > &attached)
void	initGraph (const Graph &G)
void	reinitGraph (const Graph &G)
	Reinitializes instance with graph G.
cluster	newCluster (int id)
	Creates new cluster with given id, precondition: id not used.
cluster	newCluster ()
	Creates new cluster.
void	postOrder () const
	Create postorder information in cluster tree.
void	checkPostOrder () const
	Check postorder information in cluster tree.
void	postOrder (cluster c, SListPure< cluster > &S) const
void	reinitArrays ()
void	writeCluster (ostream &os, NodeArray< int > &nId, ClusterArray< int > &cId, int &nextId, cluster c, String ttt)
	Recursively write the cluster structure in GML.
void	writeGraphWinCluster (ostream &os, NodeArray< int > &nId, NodeArray< String > &nStr, ClusterArray< int > &cId, ClusterArray< String > &cStr, int &nextId, cluster c, String ttt)
	Recursively write the cluster structure in GraphWin GML.
Private Attributes
GraphList< ClusterElement >	m_clusters
	The list of all clusters.
const Graph *	m_pGraph
	The associated graph.
int	m_nClusters
	The number of clusters.
int	m_clusterIdCount
	The index assigned to the next created cluster.
int	m_clusterArrayTableSize
	The current table size of cluster arrays.
cluster	m_postOrderStart
	The first cluster in postorder.
cluster	m_rootCluster
	The root cluster.
bool	m_adjAvailable
bool	m_allowEmptyClusters
	True if the adjacency list for each cluster is available.
NodeArray< cluster >	m_nodeMap
	Defines if empty clusters are deleted immediately if generated by operations.
NodeArray< ListIterator< node > >	m_itMap
	Stories for every node its position within the children list of its cluster.
ListPure< ClusterArrayBase * >	m_regClusterArrays
	The registered cluster arrays.
ListPure< ClusterGraphObserver * >	m_regObservers
	The registered graph observers.

OpenGraph DrawingFramework

ogdf::ClusterGraph Class Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Open
Graph Drawing
Framework