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 Types inherited from ogdf::RegistryBase< Key, Registry, Iterator >
using	iterator_type = Iterator

using	key_type = Key

using	registered_array_type = internal::RegisteredArrayBase< Registry >

using	registration_iterator_type = typename registration_list_type::iterator

using	registration_list_type = std::list< registered_array_type , OGDFAllocator< registered_array_type > >

using	registry_type = Registry

Public Member Functions
	ClusterGraph ()
	Creates a cluster graph associated with no graph. 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...

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

virtual	~ClusterGraph ()
	Destructor. More...

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

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 (const 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...

void	copyClusterTree (const ClusterGraph &C, const Graph &G, ClusterArray< cluster > &originalClusterTable, std::function< node(node)> nodeMap=[](node v) { return v;})
	Constructs a cluster tree. 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
cluster	chooseCluster (std::function< bool(cluster)> includeCluster=[](cluster) { return true;}, bool isFastTest=true) const
	Returns a random cluster. More...

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

bool	adjAvailable () const
	Gets the availability status of the adjacency entries. 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...

bool	representsConnectedCombEmbedding () const
	Checks the combinatorial cluster planar embedding. More...

void	consistencyCheck () const
	Asserts consistency of this cluster graph. More...

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

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

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

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

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

const Graph *	getGraph () const

Public Member Functions inherited from ogdf::Observer< Graph, GraphObserver >
	Observer ()=default
	Constructs instance of Observer class. More...

	Observer (const Observer &copy)=delete
	If you want to copy a subclass of Observer, call the default Observer() constructor and optionally also call reregister if it makes sense. More...

	Observer (Observer &&move)=delete
	If you want to move a subclass of Observer, call the default Observer() constructor and optionally also call reregister if it makes sense. More...

virtual	~Observer ()
	Destroys the instance, unregisters it from watched instance. More...

const Graph *	getObserved () const

Observer &	operator= (const Observer &copy)=delete

Observer &	operator= (Observer &&move)=delete

void	reregister (const Graph *obs)
	Associates observer instance with instance `obs`. More...

Public Member Functions inherited from ogdf::Observable< ClusterGraphObserver, ClusterGraph >
	Observable ()=default

	Observable (const Observable &copy)=delete
	If you want to copy a subclass of Observable, call the default Observable() constructor. More...

	Observable (Observable &&move)=delete
	If you want to move a subclass of Observable, call the default Observable() constructor. More...

virtual	~Observable ()

Observable &	operator= (const Observable &copy)=delete

Observable &	operator= (Observable &&move)=delete

Public Member Functions inherited from ogdf::RegistryBase< Key, Registry, Iterator >
	RegistryBase (const RegistryBase &copy)=delete

	RegistryBase (RegistryBase &&move) noexcept=delete

virtual	~RegistryBase () noexcept
	Destructor. Unregisters all associated arrays. More...

void	copyArrayEntries (int toIndex, int fromIndex)
	Copies the entry from `fromIndex` to `toIndex` in all registered arrays. More...

int	getArraySize () const
	Returns the current size of all registered arrays. More...

const registration_list_type &	getRegisteredArrays () const
	Returns a reference to the list of all registered arrays. More...

bool	isAutoShrink () const
	Returns whether the registry allows arrays to shrink when keys are removed. More...

void	keyAdded (Key key)
	Records the addition of a new key and resizes all registered arrays if necessary. More...

void	keyRemoved (Key key)
	Records the deletion of a key and resizes all registered arrays if auto shrink is enabled. More...

void	keysCleared ()
	Records that all keys have been cleared. If auto shrink is enabled, all arrays are cleared and resized to 0. More...

void	moveRegisterArray (registration_iterator_type it, registered_array_type *pArray) const
	Stores array `pArray` at position `it` in the list of registered arrays. More...

RegistryBase &	operator= (const RegistryBase &other)=delete

RegistryBase &	operator= (RegistryBase &&other) noexcept=delete

OGDF_NODISCARD registration_iterator_type	registerArray (registered_array_type *pArray) const
	Registers a new array with this registry. More...

void	reserveSpace (int new_keys)
	Resizes all arrays to make space of `new_keys` new keys. More...

void	resizeArrays ()
	Resizes all arrays to the size requested by calculateArraySize(). Only shrinks the arrays if auto shrink is enabled. More...

void	resizeArrays (int size)
	Resizes all arrays to `size`. Only shrinks the arrays if auto shrink is enabled. More...

void	resizeArrays (int size, bool shrink)
	Resizes all arrays to `size`. If `shrink` is `true`, the arrays may also shrink. More...

void	setAutoShrink (bool mAutoShrink)
	Specifies whether the registry allows arrays to shrink when keys are removed. More...

void	swapArrayEntries (int index1, int index2)
	Swaps the entries at `index1` and `index2` in all registered arrays. More...

void	unregisterArray (registration_iterator_type it) const noexcept
	Unregisters an array associated with this registry. More...

void	unregisterArrays () noexcept
	Unregister all associated arrays. More...

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

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

void	doClear ()
	Clears all cluster data. More...

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

cluster	doCreateCluster (const 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...

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

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

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

Functions inherited from GraphObserver (define how to cope with graph changes)
void	nodeDeleted (node v) override
	Implementation of inherited method: Updates data if node deleted. More...

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

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

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

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

void	registrationChanged (const Graph *newG) override
	Called after reregister() changed the observed instance. More...

Protected Member Functions inherited from ogdf::Observable< ClusterGraphObserver, ClusterGraph >
void	clearObservers ()

const ListPure< ClusterGraphObserver * > &	getObservers () const

Protected Member Functions inherited from ogdf::RegistryBase< Key, Registry, Iterator >
	RegistryBase ()=default

Protected Attributes
bool	m_depthUpToDate = false
	Status of cluster depth information. More...

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

std::unique_ptr< ClusterArray< int > >	m_lcaSearch
	Used to save last search run number for commoncluster. More...

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

std::unique_ptr< ClusterArray< cluster > >	m_vAncestor
	Used to save last search run number for commoncluster. More...

std::unique_ptr< ClusterArray< cluster > >	m_wAncestor
	Used to save last search run number for commoncluster. More...

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

void	checkPostOrder () const
	Check postorder information in cluster tree. More...

void	clearClusterTree (cluster c, List< node > &attached)

void	deepCopy (const ClusterGraph &C, Graph &G)
	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	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 = false

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

int	m_clusterIdCount = 0
	The index assigned to the next created cluster. More...

NodeArray< ListIterator< node > >	m_itMap

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

cluster	m_postOrderStart = nullptr
	The first cluster in postorder. More...

cluster	m_rootCluster = nullptr
	The root cluster. 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.
bool	isKeyAssociated (cluster key) const

int	calculateArraySize (int add) const

int	maxKeyIndex () const

cluster_iterator	begin () const

cluster_iterator	end () const

static int	keyToIndex (cluster key)

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 346 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 373 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 )

explicit

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() [1/2]

bool ogdf::ClusterGraph::adjAvailable ( ) const

inline

Gets the availability status of the adjacency entries.

Definition at line 725 of file ClusterGraph.h.

◆ adjAvailable() [2/2]

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

inline

Sets the availability status of the adjacency entries.

Definition at line 728 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 691 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 704 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 482 of file ClusterGraph.h.

◆ assignNode()

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

private

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

◆ begin()

cluster_iterator ogdf::ClusterGraph::begin ( ) const

inline

Definition at line 790 of file ClusterGraph.h.

◆ calculateArraySize()

int ogdf::ClusterGraph::calculateArraySize ( int add ) const

inline

Definition at line 786 of file ClusterGraph.h.

◆ checkPostOrder()

void ogdf::ClusterGraph::checkPostOrder ( ) const

private

Check postorder information in cluster tree.

◆ chooseCluster()

cluster ogdf::ClusterGraph::chooseCluster	(	std::function< bool(cluster)>	includeCluster = `[](cluster) { return true;}`,
		bool	isFastTest = `true`
	)		const

Returns a random cluster.

nullptr is returned if no feasible cluster exists.

See also: chooseIteratorFrom

◆ 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()

void ogdf::ClusterGraph::cleared ( )

inlineoverrideprotectedvirtual

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

Implements ogdf::GraphObserver.

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

◆ clusterOf()

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

inline

Returns the cluster to which a node belongs.

Definition at line 449 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 546 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 627 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 633 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 642 of file ClusterGraph.h.

◆ computeSubTreeDepth()

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

Computes depth of cluster tree hanging at c.

◆ consistencyCheck()

void ogdf::ClusterGraph::consistencyCheck ( ) const

Asserts consistency of this cluster graph.

◆ constGraph()

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

inline

Returns a reference to the underlying graph.

Definition at line 804 of file ClusterGraph.h.

◆ copyClusterTree()

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

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	(	const 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	(	const 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	(	const 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()

void ogdf::ClusterGraph::edgeAdded ( edge )

inlineoverrideprotectedvirtual

Implementation of inherited method: Updates data if edge added.

Implements ogdf::GraphObserver.

Definition at line 859 of file ClusterGraph.h.

◆ edgeDeleted()

void ogdf::ClusterGraph::edgeDeleted ( edge )

inlineoverrideprotectedvirtual

Implementation of inherited method: Updates data if edge deleted.

Implements ogdf::GraphObserver.

Definition at line 856 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 673 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 662 of file ClusterGraph.h.

◆ end()

cluster_iterator ogdf::ClusterGraph::end ( ) const

inline

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

◆ firstCluster()

cluster ogdf::ClusterGraph::firstCluster ( ) const

inline

Returns the first cluster in the list of all clusters.

Definition at line 467 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 473 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

◆ isKeyAssociated()

bool ogdf::ClusterGraph::isKeyAssociated ( cluster key ) const

inline

Definition at line 770 of file ClusterGraph.h.

◆ keyToIndex()

static int ogdf::ClusterGraph::keyToIndex ( cluster key )

inlinestatic

Definition at line 768 of file ClusterGraph.h.

◆ lastCluster()

cluster ogdf::ClusterGraph::lastCluster ( ) const

inline

Returns the last cluster in the list of all cluster.

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

◆ maxClusterIndex()

int ogdf::ClusterGraph::maxClusterIndex ( ) const

inline

Returns the maximal used cluster index.

Definition at line 446 of file ClusterGraph.h.

◆ maxKeyIndex()

int ogdf::ClusterGraph::maxKeyIndex ( ) const

inline

Definition at line 788 of file ClusterGraph.h.

◆ moveCluster()

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

Moves cluster c to a new parent newParent.

◆ 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()

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

inlineoverrideprotectedvirtual

Implementation of inherited method: Updates data if node added.

Implements ogdf::GraphObserver.

Definition at line 853 of file ClusterGraph.h.

◆ nodeDeleted()

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 443 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 801 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 886 of file ClusterGraph.h.

◆ registrationChanged()

void ogdf::ClusterGraph::registrationChanged ( const Graph * old )

overrideprotectedvirtual

Called after reregister() changed the observed instance.

Reimplemented from ogdf::Observer< Graph, GraphObserver >.

◆ reInit()

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

inline

Clear cluster info structure, reinitializes with underlying graph G.

Definition at line 537 of file ClusterGraph.h.

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

◆ representsCombEmbedding()

bool ogdf::ClusterGraph::representsCombEmbedding ( ) const

Checks the combinatorial cluster planar embedding.

Returns: true if the current embedding (given by the adjacency lists of the clusters) together with the combinatorial embedding of the underlying constGraph() represents a cluster planar combinatorial embedding

◆ representsConnectedCombEmbedding()

bool ogdf::ClusterGraph::representsConnectedCombEmbedding ( ) const

Checks the combinatorial cluster planar embedding.

This only works when the underlying Graph is connected and represents a planar embedding, so check constGraph().representsCombEmbedding() first. Otherwise, use the slower representsCombEmbedding().

Returns: true if the current embedding (given by the adjacency lists of the clusters) represents a cluster planar combinatorial embedding

◆ rootCluster()

cluster ogdf::ClusterGraph::rootCluster ( ) const

inline

Returns the root cluster.

Definition at line 440 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 601 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.

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

◆ m_adjAvailable

bool ogdf::ClusterGraph::m_adjAvailable = false

private

Definition at line 356 of file ClusterGraph.h.

◆ m_allowEmptyClusters

bool ogdf::ClusterGraph::m_allowEmptyClusters

private

Initial value:

=

true

True if the adjacency list for each cluster is available.

Definition at line 357 of file ClusterGraph.h.

◆ m_clusterIdCount

int ogdf::ClusterGraph::m_clusterIdCount = 0

private

The index assigned to the next created cluster.

Definition at line 351 of file ClusterGraph.h.

◆ m_depthUpToDate

bool ogdf::ClusterGraph::m_depthUpToDate = false

mutableprotected

Status of cluster depth information.

Definition at line 818 of file ClusterGraph.h.

◆ m_itMap

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

private

Definition at line 362 of file ClusterGraph.h.

◆ m_lcaNumber

int ogdf::ClusterGraph::m_lcaNumber = 0

mutableprotected

Used to save last search run number for commoncluster.

Definition at line 813 of file ClusterGraph.h.

◆ m_lcaSearch

std::unique_ptr<ClusterArray<int> > ogdf::ClusterGraph::m_lcaSearch

mutableprotected

Used to save last search run number for commoncluster.

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

◆ m_postOrderStart

cluster ogdf::ClusterGraph::m_postOrderStart = nullptr

mutableprivate

The first cluster in postorder.

Definition at line 353 of file ClusterGraph.h.

◆ m_rootCluster

cluster ogdf::ClusterGraph::m_rootCluster = nullptr

private

The root cluster.

Definition at line 354 of file ClusterGraph.h.

◆ m_updateDepth

bool ogdf::ClusterGraph::m_updateDepth = false

mutableprotected

Depth of clusters is always updated if set to true.

Definition at line 817 of file ClusterGraph.h.

◆ m_vAncestor

std::unique_ptr<ClusterArray<cluster> > ogdf::ClusterGraph::m_vAncestor

mutableprotected

Used to save last search run number for commoncluster.

Definition at line 814 of file ClusterGraph.h.

◆ m_wAncestor

std::unique_ptr<ClusterArray<cluster> > ogdf::ClusterGraph::m_wAncestor

mutableprotected

Used to save last search run number for commoncluster.

Definition at line 815 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

Registering arrays and observers

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() [1/2]

◆ adjAvailable() [2/2]

◆ adjEdges()

◆ adjEntries()

◆ allClusters()

◆ assignNode()

◆ begin()

◆ calculateArraySize()

◆ checkPostOrder()

◆ chooseCluster()

◆ clear()

◆ clearClusterTree() [1/2]

◆ clearClusterTree() [2/2]

◆ cleared()

◆ clusterDepth()

◆ clusterOf()

◆ collapse()

◆ commonCluster() [1/2]

◆ commonCluster() [2/2]

◆ commonClusterAncestorsPath()

◆ commonClusterLastAncestors()

◆ commonClusterPath()

◆ computeSubTreeDepth()

◆ consistencyCheck()

◆ constGraph()

◆ copyClusterTree()

◆ 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()

◆ end()

◆ fillEmptyClusters()

◆ firstCluster()

◆ firstPostOrderCluster()

◆ init()

◆ initGraph()

◆ isKeyAssociated()

◆ keyToIndex()

◆ lastCluster()

◆ leftMostCluster()

◆ makeAdjEntries()

◆ maxClusterIndex()

◆ maxKeyIndex()

◆ moveCluster()

◆ newCluster() [1/3]

◆ newCluster() [2/3]

◆ newCluster() [3/3]

◆ nodeAdded()

Open
Graph Drawing
Framework