131 const ClusterGraph* graphOf()
const {
return m_pClusterGraph; }
139 int depth()
const {
return m_depth; }
161 clusterNodes.
clear();
162 getClusterInducedNodes(clusterNodes);
219#define forall_cluster_adj(adj, c) \
220 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
221 ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
222 ogdf_loop_var = ogdf_loop_var.succ())
226#define forall_cluster_rev_adj(adj, c) \
227 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->lastAdj(); \
228 ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
229 ogdf_loop_var = ogdf_loop_var.pred())
233#define forall_cluster_adj_edges(e, c) \
234 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
235 ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var, (e)); \
236 ogdf_loop_var = ogdf_loop_var.succ())
268#define forall_clusters(c, C) for ((c) = (C).firstCluster(); (c); (c) = (c)->succ())
272#define forall_postOrderClusters(c, C) \
273 for ((c) = (C).firstPostOrderCluster(); (c); (c) = (c)->pSucc())
277class ClusterArrayBase;
307#ifndef OGDF_MEMORY_POOL_NTS
409 if (!m_depthUpToDate) {
410 computeSubTreeDepth(rootCluster());
424 if (!m_postOrderStart) {
427 return m_postOrderStart;
431 template<
class CLUSTERLIST>
490 template<
class NODELIST>
493 m_adjAvailable =
false;
495 m_postOrderStart =
nullptr;
496 node v = nodes.popFrontRet();
497 while (!nodes.empty()) {
498 node w = nodes.popFrontRet();
500 while (adj !=
nullptr) {
505 }
else if (e->
source() == w) {
518 c->m_entries.del(m_itMap[w]);
520 removeNodeAssignment(w);
540 m_depthUpToDate =
false;
563 return commonClusterLastAncestors(v, w,
c1,
c2);
569 return commonClusterAncestorsPath(v, w,
c1,
c2,
eL);
578 return commonClusterAncestorsPath(v, w,
c1,
c2,
eL);
624 template<
class EDGELIST>
628 if (m_adjAvailable) {
637 template<
class ADJLIST>
640 if (m_adjAvailable) {
642 entries.pushBack(adj);
648 template<
class LISTITERATOR>
705 operator const Graph&()
const {
return *m_pGraph; }
781 if (
cc->cCount() +
cc->nCount() == 0 &&
cc != rootCluster()) {
789 m_adjAvailable =
false;
798 std::function<
node(
node)> nodeMap = [](
node v) {
return v; });
812 c2->nodes.del(m_itMap[v]);
813 m_nodeMap[v] =
nullptr;
Abstract base class for structures on graphs, that need to be informed about graph changes (e....
Declaration and implementation of NodeArray class.
Declaration of singly linked lists and iterators.
Class for adjacency list elements.
adjEntry succ() const
Returns the successor in the adjacency list.
edge theEdge() const
Returns the edge associated with this adjacency entry.
Abstract base class for cluster arrays.
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
void getClusterInducedNodes(NodeArray< bool > &clusterNode, int &num)
cluster m_parent
The parent of this cluster.
void getClusterNodes(List< node > &clusterNodes)
Returns the list of nodes in the cluster, i.e., all nodes in the subtree rooted at this cluster.
ListConstIterator< adjEntry > lastAdj() const
Returns the last adjacency entry in the list of outgoing edges.
ListConstIterator< ClusterElement * > crBegin() const
Returns the last element in the list of child clusters.
int m_depth
The depth of this cluster in the cluster tree.
int depth() const
Returns the depth of the cluster in the cluster tree.
List< adjEntry > & getAdjEntries()
Provides access to the encapsulated list of adjacency entries (for friends of ClusterElement).
int cCount()
Returns the number of child clusters.
ListContainer< node, ClusterElement > nodes
The container containing the nodes lying (directly) in this cluster.
static int compare(const ClusterElement &x, const ClusterElement &y)
Standard Comparer (uses cluster indices).
cluster pPred() const
Returns the postorder predecessor of the cluster in the list of all clusters.
ListContainer< cluster, ClusterElement > children
The container containing the child clusters (children in the cluster tree) of this cluster.
int m_id
The index of this cluster.
List< node > & getNodes()
Provides access to the encapsulated list of nodes (for friends of ClusterElement).
int index() const
Returns the (unique) index of the cluster.
ListIterator< cluster > m_it
The position of this cluster within the children list of its parent.
cluster parent()
Returns the parent of the cluster.
ListContainer< adjEntry, ClusterElement > adjEntries
The container containing the sorted list of adjacency entries of edges leaving this cluster.
int getClusterNodes(NodeArray< bool > &clusterNode)
Sets the entry for each node v to true if v is a member of the subgraph induced by the ClusterElement...
cluster pred() const
Returns the predecessor of the cluster in the list of all clusters.
cluster m_pNext
The postorder successor of this cluster.
ClusterElement(int id)
Creates a new cluster element.
cluster pSucc() const
Returns the postorder successor of the cluster in the list of all clusters.
int nCount()
Returns the number of child nodes.
void getClusterInducedNodes(List< node > &clusterNodes)
Traverses the inclusion tree and adds nodes to clusterNodes.
cluster m_pPrev
The postorder predecessor of this cluster.
cluster succ() const
Returns the successor of the cluster in the list of all clusters.
ListConstIterator< ClusterElement * > cBegin() const
Returns the first element in the list of child clusters.
ListConstIterator< adjEntry > firstAdj() const
Returns the first adjacency entry in the list of outgoing edges.
ListConstIterator< node > nBegin() const
Returns the first element in list of child nodes.
List< cluster > & getChildren()
Provides access to the encapsulated list of children (for friends of ClusterElement).
Representation of clustered graphs.
void pullUpSubTree(cluster c)
Updates depth information in subtree after delCluster.
int m_clusterIdCount
The index assigned to the next created cluster.
void unregisterObserver(ListIterator< ClusterGraphObserver * > it) const
Unregisters a cluster graph observer.
cluster newCluster(cluster parent, int id=-1)
Inserts a new cluster; makes it a child of the cluster parent.
NodeArray< ListIterator< node > > m_itMap
void unregisterArray(ListIterator< ClusterArrayBase * > it) const
Unregisters a cluster array.
bool m_updateDepth
Depth of clusters is always updated if set to true.
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,...
void shallowCopy(const ClusterGraph &C)
Performs a copy of the cluster structure of C, the underlying graph stays the same.
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 setUpdateDepth(bool b) const
Turns automatic update of node depth values on or off.
cluster firstPostOrderCluster() const
Returns the first cluster in the list of post ordered clusters.
ClusterGraph & operator=(const ClusterGraph &C)
Assignment operator.
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 moveRegisterArray(ListIterator< ClusterArrayBase * > it, ClusterArrayBase *pClusterArray) const
Move the registration it of a cluster array to pClusterArray (used with move semantics for cluster ar...
ListPure< ClusterArrayBase * > m_regClusterArrays
The registered cluster arrays.
cluster commonCluster(node v, node w) const
Returns the lowest common cluster of v and w in the cluster tree.
cluster m_postOrderStart
The first cluster in postorder.
cluster commonCluster(SList< node > &nodes)
Returns lowest common cluster of nodes in list nodes.
void adjEdges(cluster c, EDGELIST &edges) const
Returns the list of all edges adjacent to cluster c in edges.
ListIterator< ClusterArrayBase * > registerArray(ClusterArrayBase *pClusterArray) const
Registers a cluster array.
ClusterArray< cluster > * m_wAncestor
Used to save last search run number for commoncluster.
void initGraph(const Graph &G)
void adjAvailable(bool val)
Sets the availability status of the adjacency entries.
ListIterator< ClusterGraphObserver * > registerObserver(ClusterGraphObserver *pObserver) const
Registers a cluster graph observer.
void emptyClusters(SList< cluster > &emptyCluster, SList< cluster > *checkCluster=nullptr)
Returns the list of clusters that are empty or only contain empty clusters.
void computeSubTreeDepth(cluster c) const
Computes depth of cluster tree hanging at c.
void reassignNode(node v, cluster c)
Reassigns node v to cluster c.
cluster firstCluster() const
Returns the first cluster in the list of all clusters.
void copyLCA(const ClusterGraph &C)
Copies lowest common ancestor info to copy of clustered graph.
bool m_allowEmptyClusters
True if the adjacency list for each cluster is available.
ClusterArray< int > * m_lcaSearch
Used to save last search run number for commoncluster.
cluster postOrderPredecessor(cluster c) const
Computes new predecessor for subtree at moved cluster c (nullptr if c is the root).
void allClusters(CLUSTERLIST &clusterList) const
Returns the list of all clusters in clusterList.
int & clusterDepth(cluster c) const
Returns depth of cluster c in cluster tree, starting with root depth 1.
int maxClusterIndex() const
Returns the maximal used cluster index.
ClusterGraph(const ClusterGraph &C, Graph &G)
Copies the underlying graph of C into G and constructs a copy of C associated with G.
bool emptyOnClusterDelete(cluster c)
Returns true if cluster c has only one child and no nodes.
cluster clusterOf(node v) const
Returns the cluster to which a node belongs.
virtual void edgeDeleted(edge) override
Implementation of inherited method: Updates data if edge deleted.
cluster rootCluster() const
Returns the root cluster.
bool m_depthUpToDate
Status of cluster depth information.
void reInit(Graph &G)
Clear cluster info structure, reinitializes with underlying graph G.
void updatePostOrder(cluster c, cluster oldParent, cluster newParent)
Adjusts the post order structure for moved clusters.
int clusterArrayTableSize() const
Returns the table size of cluster arrays associated with this graph.
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.
cluster leftMostCluster(cluster c) const
Leftmost cluster in subtree rooted at c, gets predecessor of subtree.
void unassignNode(node v)
Unassigns node v from its cluster.
void deepCopy(const ClusterGraph &C, Graph &G)
Perform a deep copy on C, C's underlying graph is copied into G.
ClusterGraph(const Graph &G)
Creates a cluster graph associated with graph G.
void makeAdjEntries(cluster c, LISTITERATOR start)
Computes the adjacency entry list for cluster c.
void postOrder() const
Create postorder information in cluster tree.
cluster createEmptyCluster(const cluster parent=nullptr, int clusterId=-1)
Creates an empty cluster with index clusterId and parent parent.
void removeNodeAssignment(node v)
Remove the assignment entries for nodes. Checks if node v is currently not assigned.
void reinitGraph(const Graph &G)
Reinitializes instance with graph G.
NodeArray< cluster > m_nodeMap
Defines if empty clusters are deleted immediately if generated by operations.
bool emptyOnNodeDelete(cluster c)
Returns true if cluster c has only one node and no children.
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.
cluster newCluster()
Creates new cluster.
int m_lcaNumber
Used to save last search run number for commoncluster.
void adjEntries(cluster c, ADJLIST &entries) const
Returns the list of all adjacency entries adjacent to cluster c in entries.
virtual void nodeAdded(node v) override
Implementation of inherited method: Updates data if node added.
virtual void nodeDeleted(node v) override
Implementation of inherited method: Updates data if node deleted.
void doClear()
Clears all cluster data.
const Graph & constGraph() const
Returns a reference to the underlying graph.
std::mutex m_mutexRegArrays
The critical section for protecting shared acces to register/unregister methods.
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.
int numberOfClusters() const
Returns the number of clusters.
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 collapse(NODELIST &nodes, Graph &G)
Collapses all nodes in the list nodes to the first node; multi-edges are removed.
void delCluster(cluster c)
Deletes cluster c.
virtual ~ClusterGraph()
Destructor.
void init(const Graph &G)
Clears all cluster data and then reinitializes the instance with underlying graph G.
virtual void edgeAdded(edge) override
Implementation of inherited method: Updates data if edge added.
const Graph * m_pGraph
The associated graph.
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.
ListPure< ClusterGraphObserver * > m_regObservers
The registered graph observers.
cluster m_rootCluster
The root cluster.
bool representsCombEmbedding() const
Checks the combinatorial cluster planar embedding.
cluster commonClusterPath(node v, node w, List< cluster > &eL) const
Returns lca of v and w and stores corresponding path in eL.
void clearClusterTree(cluster C)
Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself.
void moveCluster(cluster c, cluster newParent)
Moves cluster c to a new parent newParent.
void fillEmptyClusters(SList< cluster > &emptyCluster, const T &clusterList) const
Fills emptyCluster with empty, non-root clusters from clusterList.
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 originalN...
cluster newCluster(int id)
Creates new cluster with given id, precondition: id not used.
ClusterGraph()
Creates a cluster graph associated with no graph.
ClusterArray< cluster > * m_vAncestor
Used to save last search run number for commoncluster.
cluster lastCluster() const
Returns the last cluster in the list of all cluster.
int m_clusterArrayTableSize
The current table size of cluster arrays.
internal::GraphObjectContainer< ClusterElement > clusters
The container containing all cluster objects.
ClusterGraph(const ClusterGraph &C)
Copy constructor.
void clearClusterTree(cluster c, List< node > &attached)
void clear()
Removes all clusters except for the root cluster.
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 originalN...
cluster doCreateCluster(SList< node > &nodes, const cluster parent, int clusterId=-1)
Creates new cluster containing nodes in parameter list with index clusterId.
void assignNode(node v, cluster C)
Assigns node v to cluster C (v not yet assigned!).
virtual void cleared() override
Clears cluster data without deleting root when underlying graphs' clear method is called.
int treeDepth() const
Computes depth of cluster tree, running time O(C).
Abstract base class for cluster graph observers.
Dynamic arrays indexed with edges.
Class for the representation of edges.
node target() const
Returns the target node of the edge.
node source() const
Returns the source node of the edge.
Data type for general directed graphs (adjacency list representation).
Abstract Base class for graph observers.
iterator begin() const
Returns an iterator to the first element in the container.
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
int size() const
Returns the number of elements in the container.
Doubly linked lists (maintaining the length of the list).
void clear()
Removes all elements from the list.
Encapsulates a pointer to a list element.
bool valid() const
Returns true iff the iterator points to an element.
Dynamic arrays indexed with nodes.
Class for the representation of nodes.
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Singly linked lists (maintaining the length of the list).
The base class for objects used by (hyper)graphs.
Lists of graph objects (like nodes, edges, etc.).
T * head() const
Returns the first element in the list.
T * tail() const
Returns the last element in the list.
int size() const
Returns the size of the list.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
#define forall_cluster_adj_edges(e, c)
Iterates over all outgoing edges.
bool test_forall_adj_edges_of_cluster(ListConstIterator< adjEntry > &it, edge &e)
bool test_forall_adj_entries_of_cluster(ListConstIterator< adjEntry > &it, adjEntry &adj)
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.