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.

Public Member Functions
	ClusterGraph ()
	Creates a cluster graph associated with no graph.

	ClusterGraph (const ClusterGraph &C)
	Copy constructor.

	ClusterGraph (const ClusterGraph &C, Graph &G)
	Copies the underlying graph of `C` into `G` and constructs a copy of `C` associated with `G`.

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

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

	ClusterGraph (const Graph &G)
	Creates a cluster graph associated with graph `G`.

virtual	~ClusterGraph ()
	Destructor.

Access methods
cluster	rootCluster () const
	Returns the root cluster.

int	numberOfClusters () const
	Returns the number of clusters.

int	maxClusterIndex () const
	Returns the maximal used cluster index.

int	clusterArrayTableSize () const
	Returns the table size of cluster arrays associated with this graph.

cluster	clusterOf (node v) const
	Returns the cluster to which a node belongs.

int &	clusterDepth (cluster c) const
	Returns depth of cluster c in cluster tree, starting with root depth 1.

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	allClusters (CLUSTERLIST &clusterList) const
	Returns the list of all clusters in `clusterList`.

Modification methods
void	clear ()
	Removes all clusters except for the root cluster.

void	init (const Graph &G)
	Clears all cluster data and then reinitializes the instance with underlying graph `G`.

void	clearClusterTree (cluster C)
	Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself.

cluster	newCluster (cluster parent, int id=-1)
	Inserts a new cluster; makes it a child of the cluster `parent`.

cluster	createEmptyCluster (const cluster parent=nullptr, int clusterId=-1)
	Creates an empty cluster with index `clusterId` and parent `parent`.

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

void	delCluster (cluster c)
	Deletes cluster `c`.

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

template<class NODELIST >
void	collapse (NODELIST &nodes, Graph &G)
	Collapses all nodes in the list `nodes` to the first node; multi-edges are removed.

Cluster tree queries
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`.

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

void	emptyClusters (SList< cluster > &emptyCluster, SList< cluster > *checkCluster=nullptr)
	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.

Adjacent edges
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	adjAvailable (bool val)
	Sets the availability status of the adjacency entries.

Miscellaneous
bool	representsCombEmbedding () const
	Checks the combinatorial cluster planar embedding.

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.

void	unregisterArray (ListIterator< ClusterArrayBase * > it) const
	Unregisters a cluster array.

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

ListIterator< ClusterGraphObserver * >	registerObserver (ClusterGraphObserver *pObserver) const
	Registers a cluster graph observer.

void	unregisterObserver (ListIterator< ClusterGraphObserver * > it) const
	Unregisters a cluster graph observer.

Operators and conversion
	operator const Graph & () const
	Conversion to const Graph reference (to underlying graph).

const Graph &	constGraph () const
	Returns a reference to the underlying graph.

ClusterGraph &	operator= (const ClusterGraph &C)
	Assignment operator.

Public Member Functions inherited from ogdf::GraphObserver
	GraphObserver ()
	Constructs instance of GraphObserver class.

	GraphObserver (const Graph *G)
	Constructs instance of GraphObserver class.

virtual	~GraphObserver ()
	Destroys the instance, unregisters it from watched graph.

const Graph *	getGraph () const

void	reregister (const Graph *pG)
	Associates observer instance with graph `G`.

Public Attributes
Graph object containers
These containers maintain the nodes and edges of the graph, and provide node and edge iterators.
internal::GraphObjectContainer< ClusterElement >	clusters
	The container containing all cluster objects.

Protected Member Functions
void	copyLCA (const ClusterGraph &C)
	Copies lowest common ancestor info to copy of clustered graph.

void	doClear ()
	Clears all cluster data.

cluster	doCreateCluster (SList< node > &nodes, const cluster parent, int clusterId=-1)
	Creates new cluster containing nodes in parameter list with index `clusterId`.

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

cluster	leftMostCluster (cluster c) const
	Leftmost cluster in subtree rooted at c, gets predecessor of subtree.

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

void	updatePostOrder (cluster c, cluster oldParent, cluster newParent)
	Adjusts the post order structure for moved clusters.

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.

virtual void	nodeAdded (node v) override
	Implementation of inherited method: Updates data if node added.

virtual void	edgeDeleted (edge) override
	Implementation of inherited method: Updates data if edge deleted.

virtual void	edgeAdded (edge) override
	Implementation of inherited method: Updates data if edge added.

virtual void	cleared () override
	Clears cluster data without deleting root when underlying graphs' clear method is called.

Protected Attributes
bool	m_depthUpToDate
	Status of cluster depth information.

int	m_lcaNumber
	Used to save last search run number for commoncluster.

ClusterArray< int > *	m_lcaSearch
	Used to save last search run number for commoncluster.

bool	m_updateDepth
	Depth of clusters is always updated if set to true.

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.

Protected Attributes inherited from ogdf::GraphObserver
ListIterator< GraphObserver * >	m_itGList
	watched graph

const Graph *	m_pGraph

Private Member Functions
void	assignNode (node v, cluster C)
	Assigns node `v` to cluster `C` (`v` not yet assigned!).

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.

void	deepCopy (const ClusterGraph &C, Graph &G)
	Perform a deep copy on `C`, `C's` underlying graph is copied into `G`.

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

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

template<typename T >
void	fillEmptyClusters (SList< cluster > &emptyCluster, const T &clusterList) const
	Fills `emptyCluster` with empty, non-root clusters from `clusterList`.

void	initGraph (const Graph &G)

cluster	newCluster ()
	Creates new cluster.

cluster	newCluster (int id)
	Creates new cluster with given id, precondition: id not used.

void	postOrder () const
	Create postorder information in cluster tree.

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

void	recurseClearClusterTreeOnChildren (cluster c, List< node > &attached)
	Clears children of a cluster, used by recursive clearClusterTree.

void	reinitArrays ()

void	reinitGraph (const Graph &G)
	Reinitializes instance with graph `G`.

void	removeNodeAssignment (node v)
	Remove the assignment entries for nodes. Checks if node `v` is currently not assigned.

void	shallowCopy (const ClusterGraph &C)
	Performs a copy of the cluster structure of `C`, the underlying graph stays the same.

void	unassignNode (node v)
	Unassigns node `v` from its cluster.

Private Attributes
bool	m_adjAvailable

bool	m_allowEmptyClusters
	True if the adjacency list for each cluster is available.

int	m_clusterArrayTableSize
	The current table size of cluster arrays.

int	m_clusterIdCount
	The index assigned to the next created cluster.

NodeArray< ListIterator< node > >	m_itMap

std::mutex	m_mutexRegArrays
	The critical section for protecting shared acces to register/unregister methods.

NodeArray< cluster >	m_nodeMap
	Defines if empty clusters are deleted immediately if generated by operations.

const Graph *	m_pGraph
	The associated graph.

cluster	m_postOrderStart
	The first cluster in postorder.

ListPure< ClusterArrayBase * >	m_regClusterArrays
	The registered cluster arrays.

ListPure< ClusterGraphObserver * >	m_regObservers
	The registered graph observers.

cluster	m_rootCluster
	The root cluster.

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

Member Typedef Documentation

◆ cluster_iterator

using ogdf::ClusterGraph::cluster_iterator = internal::GraphIterator<cluster>

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

Definition at line 320 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 659 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 625 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 638 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 432 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 766 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 396 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 404 of file ClusterGraph.h.

◆ clusterOf()

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

inline

Returns the cluster to which a node belongs.

Definition at line 399 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 491 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 561 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 567 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 576 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 708 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

nodes	are the nodes that will be reassigned to the new cluster.
parent	is 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 763 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 760 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 607 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 596 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 777 of file ClusterGraph.h.

◆ firstCluster()

cluster ogdf::ClusterGraph::firstCluster ( ) const

inline

Returns the first cluster in the list of all clusters.

Definition at line 417 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 423 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 420 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 649 of file ClusterGraph.h.

◆ maxClusterIndex()

int ogdf::ClusterGraph::maxClusterIndex ( ) const

inline

Returns the maximal used cluster index.

Definition at line 393 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 757 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 390 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 705 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 788 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()

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

inline

Clear cluster info structure, reinitializes with underlying graph G.

Definition at line 487 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 808 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 387 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 535 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 331 of file ClusterGraph.h.

◆ m_adjAvailable

bool ogdf::ClusterGraph::m_adjAvailable

private

Definition at line 297 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 298 of file ClusterGraph.h.

◆ m_clusterArrayTableSize

int ogdf::ClusterGraph::m_clusterArrayTableSize

private

The current table size of cluster arrays.

Definition at line 292 of file ClusterGraph.h.

◆ m_clusterIdCount

int ogdf::ClusterGraph::m_clusterIdCount

private

The index assigned to the next created cluster.

Definition at line 291 of file ClusterGraph.h.

◆ m_depthUpToDate

bool ogdf::ClusterGraph::m_depthUpToDate

mutableprotected

Status of cluster depth information.

Definition at line 722 of file ClusterGraph.h.

◆ m_itMap

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

private

Definition at line 302 of file ClusterGraph.h.

◆ m_lcaNumber

int ogdf::ClusterGraph::m_lcaNumber

mutableprotected

Used to save last search run number for commoncluster.

Definition at line 717 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 716 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 308 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 300 of file ClusterGraph.h.

◆ m_pGraph

const Graph* ogdf::ClusterGraph::m_pGraph

private

The associated graph.

Definition at line 289 of file ClusterGraph.h.

◆ m_postOrderStart

cluster ogdf::ClusterGraph::m_postOrderStart

mutableprivate

The first cluster in postorder.

Definition at line 294 of file ClusterGraph.h.

◆ m_regClusterArrays

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

mutableprivate

The registered cluster arrays.

Definition at line 304 of file ClusterGraph.h.

◆ m_regObservers

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

mutableprivate

The registered graph observers.

Definition at line 305 of file ClusterGraph.h.

◆ m_rootCluster

cluster ogdf::ClusterGraph::m_rootCluster

private

The root cluster.

Definition at line 295 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 721 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 718 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 719 of file ClusterGraph.h.

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

include/ogdf/cluster/ClusterGraph.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ cluster_iterator

Constructor & Destructor Documentation

◆ ClusterGraph() [1/6]

◆ ClusterGraph() [2/6]

◆ ClusterGraph() [3/6]

◆ ClusterGraph() [4/6]

◆ ClusterGraph() [5/6]

◆ ClusterGraph() [6/6]

◆ ~ClusterGraph()

Member Function Documentation

◆ adjAvailable()

◆ adjEdges()

◆ adjEntries()

◆ allClusters()

◆ assignNode()

◆ clear()

◆ clearClusterTree() [1/2]

◆ clearClusterTree() [2/2]

◆ cleared()

◆ clusterArrayTableSize()

◆ clusterDepth()

◆ clusterOf()

◆ collapse()

◆ commonCluster() [1/2]

◆ commonCluster() [2/2]

◆ commonClusterAncestorsPath()

◆ commonClusterLastAncestors()

◆ commonClusterPath()

◆ computeSubTreeDepth()

◆ constGraph()

◆ constructClusterTree()

◆ copyLCA()

◆ createCluster()

◆ createEmptyCluster()

◆ deepCopy() [1/3]

◆ deepCopy() [2/3]

◆ deepCopy() [3/3]

◆ delCluster()

◆ doClear()

◆ doCreateCluster() [1/2]

◆ doCreateCluster() [2/2]

◆ edgeAdded()

◆ edgeDeleted()

◆ emptyClusters()

◆ emptyOnClusterDelete()

◆ emptyOnNodeDelete()

◆ fillEmptyClusters()

◆ firstCluster()

◆ firstPostOrderCluster()

◆ init()

◆ initGraph()

◆ lastCluster()

◆ leftMostCluster()

◆ makeAdjEntries()

◆ maxClusterIndex()

◆ moveCluster()

◆ moveRegisterArray()

◆ newCluster() [1/3]

◆ newCluster() [2/3]

◆ newCluster() [3/3]

◆ nodeAdded()

◆ nodeDeleted()

◆ numberOfClusters()

◆ operator const Graph &()

◆ operator=()

◆ postOrder() [1/2]

◆ postOrder() [2/2]

◆ postOrderPredecessor()

◆ pullUpSubTree()

◆ reassignNode()

Open
Graph Drawing
Framework