Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ExtendedNestingGraph Class Reference

#include <ogdf/layered/ExtendedNestingGraph.h>

+ Inheritance diagram for ogdf::ExtendedNestingGraph:

Public Types

enum  NodeType { NodeType::Node, NodeType::ClusterTop, NodeType::ClusterBottom, NodeType::Dummy, NodeType::ClusterTopBottom }
 
- Public Types inherited from ogdf::Graph
enum  EdgeType { EdgeType::association = 0, EdgeType::generalization = 1, EdgeType::dependency = 2 }
 The type of edges (only used in derived classes). More...
 
enum  NodeType { NodeType::vertex = 0, NodeType::dummy = 1, NodeType::generalizationMerger = 2, NodeType::generalizationExpander = 3, NodeType::highDegreeExpander = 4, NodeType::lowDegreeExpander = 5, NodeType::associationClass = 6 }
 The type of nodes. More...
 
using node_iterator = internal::GraphIterator< node >
 Provides a bidirectional iterator to a node in a graph. More...
 
using edge_iterator = internal::GraphIterator< edge >
 Provides a bidirectional iterator to an edge in a graph. More...
 
using adjEntry_iterator = internal::GraphIterator< adjEntry >
 Provides a bidirectional iterator to an entry in an adjacency list. More...
 

Public Member Functions

 ExtendedNestingGraph (const ClusterGraph &CG)
 
int aeLevel (node v) const
 
node bottom (cluster cOrig) const
 
int bottomRank (cluster c) const
 
const List< edge > & chain (edge e) const
 
node copy (node v) const
 
const ClusterGraphCopygetClusterGraph () const
 
const ClusterGraphgetOriginalClusterGraph () const
 
bool isLongEdgeDummy (node v) const
 
bool isReversed (edge e) const
 
bool isVirtual (cluster c) const
 
const ENGLayerlayer (int i) const
 
const LHTreeNodelayerHierarchyTree (int i) const
 
int numberOfLayers () const
 
edge origEdge (edge e) const
 
cluster originalCluster (node v) const
 
node origNode (node v) const
 
cluster parent (cluster c) const
 
cluster parent (node v) const
 
void permute ()
 
int pos (node v) const
 
int rank (node v) const
 
RCCrossings reduceCrossings (int i, bool dirTopDown)
 
void removeTopBottomEdges ()
 
void restorePos ()
 
void storeCurrentPos ()
 
node top (cluster cOrig) const
 
int topRank (cluster c) const
 
NodeType type (node v) const
 
bool verticalSegment (edge e) const
 
- Public Member Functions inherited from ogdf::Graph
bool empty () const
 Returns true iff the graph is empty, i.e., contains no nodes. More...
 
int numberOfNodes () const
 Returns the number of nodes in the graph. More...
 
int numberOfEdges () const
 Returns the number of edges in the graph. More...
 
int maxNodeIndex () const
 Returns the largest used node index. More...
 
int maxEdgeIndex () const
 Returns the largest used edge index. More...
 
int maxAdjEntryIndex () const
 Returns the largest used adjEntry index. More...
 
int nodeArrayTableSize () const
 Returns the table size of node arrays associated with this graph. More...
 
int edgeArrayTableSize () const
 Returns the table size of edge arrays associated with this graph. More...
 
int adjEntryArrayTableSize () const
 Returns the table size of adjEntry arrays associated with this graph. More...
 
node firstNode () const
 Returns the first node in the list of all nodes. More...
 
node lastNode () const
 Returns the last node in the list of all nodes. More...
 
edge firstEdge () const
 Returns the first edge in the list of all edges. More...
 
edge lastEdge () const
 Returns the last edge in the list of all edges. More...
 
node chooseNode (std::function< bool(node)> includeNode=[](node) { return true;}, bool isFastTest=true) const
 Returns a random node. More...
 
edge chooseEdge (std::function< bool(edge)> includeEdge=[](edge) { return true;}, bool isFastTest=true) const
 Returns a random edge. More...
 
template<class CONTAINER >
void allNodes (CONTAINER &nodeContainer) const
 Returns a container with all nodes of the graph. More...
 
template<class CONTAINER >
void allEdges (CONTAINER &edgeContainer) const
 Returns a container with all edges of the graph. More...
 
node newNode ()
 Creates a new node and returns it. More...
 
node newNode (int index)
 Creates a new node with predefined index and returns it. More...
 
edge newEdge (node v, node w)
 Creates a new edge (v,w) and returns it. More...
 
edge newEdge (node v, node w, int index)
 Creates a new edge (v,w) with predefined index and returns it. More...
 
edge newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=Direction::after)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
edge newEdge (node v, adjEntry adjTgt)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
edge newEdge (adjEntry adjSrc, node w)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
virtual void delNode (node v)
 Removes node v and all incident edges from the graph. More...
 
virtual void delEdge (edge e)
 Removes edge e from the graph. More...
 
virtual void clear ()
 Removes all nodes and all edges from the graph. More...
 
void insert (const Graph &G, NodeArray< node > &nodeMap)
 Inserts Graph G as a subgraph into this Graph. More...
 
void insert (const Graph &G)
 Inserts Graph G as a subgraph into this Graph. More...
 
virtual edge split (edge e)
 Splits edge e into two edges introducing a new node. More...
 
void unsplit (node u)
 Undoes a split operation. More...
 
virtual void unsplit (edge eIn, edge eOut)
 Undoes a split operation. More...
 
node splitNode (adjEntry adjStartLeft, adjEntry adjStartRight)
 Splits a node while preserving the order of adjacency entries. More...
 
node contract (edge e, bool keepSelfLoops=false)
 Contracts edge e while preserving the order of adjacency entries. More...
 
void move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt)
 Moves edge e to a different adjacency list. More...
 
void moveTarget (edge e, node w)
 Moves the target node of edge e to node w. More...
 
void moveTarget (edge e, adjEntry adjTgt, Direction dir)
 Moves the target node of edge e to a specific position in an adjacency list. More...
 
void moveSource (edge e, node w)
 Moves the source node of edge e to node w. More...
 
void moveSource (edge e, adjEntry adjSrc, Direction dir)
 Moves the source node of edge e to a specific position in an adjacency list. More...
 
edge searchEdge (node v, node w, bool directed=false) const
 Searches and returns an edge connecting nodes v and w in time O( min(deg(v ), deg(w ))). More...
 
void reverseEdge (edge e)
 Reverses the edge e, i.e., exchanges source and target node. More...
 
void reverseAllEdges ()
 Reverses all edges in the graph. More...
 
template<class NODELIST >
void collapse (NODELIST &nodesToCollapse)
 Collapses all nodes in the list nodesToCollapse to the first node in the list. More...
 
template<class ADJ_ENTRY_LIST >
void sort (node v, const ADJ_ENTRY_LIST &newOrder)
 Sorts the adjacency list of node v according to newOrder. More...
 
void reverseAdjEdges (node v)
 Reverses the adjacency list of v. More...
 
void moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos)
 Moves adjacency entry adjMove before or after adjPos. More...
 
void moveAdjAfter (adjEntry adjMove, adjEntry adjAfter)
 Moves adjacency entry adjMove after adjAfter. More...
 
void moveAdjBefore (adjEntry adjMove, adjEntry adjBefore)
 Moves adjacency entry adjMove before adjBefore. More...
 
void reverseAdjEdges ()
 Reverses all adjacency lists. More...
 
void swapAdjEdges (adjEntry adj1, adjEntry adj2)
 Exchanges two entries in an adjacency list. More...
 
int genus () const
 Returns the genus of the graph's embedding. More...
 
bool representsCombEmbedding () const
 Returns true iff the graph represents a combinatorial embedding. More...
 
ListIterator< NodeArrayBase * > registerArray (NodeArrayBase *pNodeArray) const
 Registers a node array. More...
 
ListIterator< EdgeArrayBase * > registerArray (EdgeArrayBase *pEdgeArray) const
 Registers an edge array. More...
 
ListIterator< AdjEntryArrayBase * > registerArray (AdjEntryArrayBase *pAdjArray) const
 Registers an adjEntry array. More...
 
ListIterator< GraphObserver * > registerStructure (GraphObserver *pStructure) const
 Registers a graph observer (e.g. a ClusterGraph). More...
 
void unregisterArray (ListIterator< NodeArrayBase * > it) const
 Unregisters a node array. More...
 
void unregisterArray (ListIterator< EdgeArrayBase * > it) const
 Unregisters an edge array. More...
 
void unregisterArray (ListIterator< AdjEntryArrayBase * > it) const
 Unregisters an adjEntry array. More...
 
void unregisterStructure (ListIterator< GraphObserver * > it) const
 Unregisters a graph observer. More...
 
template<class ArrayBase >
void moveRegisterArray (ListIterator< ArrayBase * > it, ArrayBase *pArray) const
 Move the registration it of an graph element array to pArray (used with move semantics for graph element arrays). More...
 
void resetEdgeIdCount (int maxId)
 Resets the edge id count to maxId. More...
 
 Graph ()
 Constructs an empty graph. More...
 
 Graph (const Graph &G)
 Constructs a graph that is a copy of G. More...
 
virtual ~Graph ()
 Destructor. More...
 
Graphoperator= (const Graph &G)
 Assignment operator. More...
 

Protected Member Functions

edge addEdge (node u, node v, bool addAlways=false)
 
void assignAeLevel (cluster c, int &count)
 
void assignPos (const LHTreeNode *vNode, int &count)
 
LHTreeNodelca (LHTreeNode *uNode, LHTreeNode *vNode, LHTreeNode **uChild, LHTreeNode **vChild) const
 
cluster lca (node u, node v) const
 
void moveDown (node v, const SListPure< node > &successors, NodeArray< int > &level)
 
bool reachable (node v, node u, SListPure< node > &successors)
 
RCCrossings reduceCrossings (LHTreeNode *cNode, bool dirTopDown)
 
bool tryEdge (node u, node v, Graph &G, NodeArray< int > &level)
 
- Protected Member Functions inherited from ogdf::Graph
void construct (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 
void assign (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 
void constructInitByNodes (const Graph &G, const List< node > &nodeList, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 Constructs a copy of the subgraph of G induced by nodeList. More...
 
void constructInitByActiveNodes (const List< node > &nodeList, const NodeArray< bool > &activeNodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 
void constructInitByCC (const CCsInfo &info, int cc, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 Constructs a copy of connected component cc in info. More...
 

Private Member Functions

void buildLayers ()
 
void computeRanking ()
 
void createDummyNodes ()
 
void createVirtualClusters ()
 
void createVirtualClusters (cluster c, NodeArray< node > &vCopy, ClusterArray< node > &cCopy)
 
void removeAuxNodes ()
 

Private Attributes

NodeArray< int > m_aeLevel
 
NodeArray< bool > m_aeVisited
 
NodeArray< int > m_auxDeg
 
ClusterArray< nodem_bottomNode
 
ClusterArray< int > m_bottomRank
 
ClusterGraphCopy m_CGC
 copy of original cluster graph More...
 
NodeArray< nodem_copy
 
EdgeArray< List< edge > > m_copyEdge
 
Array< ENGLayerm_layer
 
ClusterArray< clusterm_mark
 
SListPure< clusterm_markedClusters
 
SListPure< clusterm_markedClustersTree
 
ClusterArray< LHTreeNode * > m_markTree
 
int m_numLayers
 
EdgeArray< edgem_origEdge
 
NodeArray< nodem_origNode
 
NodeArray< int > m_pos
 
NodeArray< int > m_rank
 
cluster m_secondPath
 
node m_secondPathTo
 
ClusterArray< nodem_topNode
 
ClusterArray< int > m_topRank
 
NodeArray< NodeTypem_type
 
EdgeArray< bool > m_vertical
 

Additional Inherited Members

- Public Attributes inherited from ogdf::Graph
internal::GraphObjectContainer< NodeElementnodes
 The container containing all node objects. More...
 
internal::GraphObjectContainer< EdgeElementedges
 The container containing all edge objects. More...
 

Detailed Description

Definition at line 284 of file ExtendedNestingGraph.h.

Member Enumeration Documentation

◆ NodeType

Enumerator
Node 
ClusterTop 
ClusterBottom 
Dummy 
ClusterTopBottom 

Definition at line 288 of file ExtendedNestingGraph.h.

Constructor & Destructor Documentation

◆ ExtendedNestingGraph()

ogdf::ExtendedNestingGraph::ExtendedNestingGraph ( const ClusterGraph CG)
explicit

Member Function Documentation

◆ addEdge()

edge ogdf::ExtendedNestingGraph::addEdge ( node  u,
node  v,
bool  addAlways = false 
)
protected

◆ aeLevel()

int ogdf::ExtendedNestingGraph::aeLevel ( node  v) const
inline

Definition at line 338 of file ExtendedNestingGraph.h.

◆ assignAeLevel()

void ogdf::ExtendedNestingGraph::assignAeLevel ( cluster  c,
int &  count 
)
protected

◆ assignPos()

void ogdf::ExtendedNestingGraph::assignPos ( const LHTreeNode vNode,
int &  count 
)
protected

◆ bottom()

node ogdf::ExtendedNestingGraph::bottom ( cluster  cOrig) const
inline

Definition at line 297 of file ExtendedNestingGraph.h.

◆ bottomRank()

int ogdf::ExtendedNestingGraph::bottomRank ( cluster  c) const
inline

Definition at line 300 of file ExtendedNestingGraph.h.

◆ buildLayers()

void ogdf::ExtendedNestingGraph::buildLayers ( )
private

◆ chain()

const List<edge>& ogdf::ExtendedNestingGraph::chain ( edge  e) const
inline

Definition at line 312 of file ExtendedNestingGraph.h.

◆ computeRanking()

void ogdf::ExtendedNestingGraph::computeRanking ( )
private

◆ copy()

node ogdf::ExtendedNestingGraph::copy ( node  v) const
inline

Definition at line 295 of file ExtendedNestingGraph.h.

◆ createDummyNodes()

void ogdf::ExtendedNestingGraph::createDummyNodes ( )
private

◆ createVirtualClusters() [1/2]

void ogdf::ExtendedNestingGraph::createVirtualClusters ( )
private

◆ createVirtualClusters() [2/2]

void ogdf::ExtendedNestingGraph::createVirtualClusters ( cluster  c,
NodeArray< node > &  vCopy,
ClusterArray< node > &  cCopy 
)
private

◆ getClusterGraph()

const ClusterGraphCopy& ogdf::ExtendedNestingGraph::getClusterGraph ( ) const
inline

Definition at line 292 of file ExtendedNestingGraph.h.

◆ getOriginalClusterGraph()

const ClusterGraph& ogdf::ExtendedNestingGraph::getOriginalClusterGraph ( ) const
inline

Definition at line 293 of file ExtendedNestingGraph.h.

◆ isLongEdgeDummy()

bool ogdf::ExtendedNestingGraph::isLongEdgeDummy ( node  v) const
inline

Definition at line 319 of file ExtendedNestingGraph.h.

◆ isReversed()

bool ogdf::ExtendedNestingGraph::isReversed ( edge  e) const
inline

Definition at line 315 of file ExtendedNestingGraph.h.

◆ isVirtual()

bool ogdf::ExtendedNestingGraph::isVirtual ( cluster  c) const
inline

Definition at line 310 of file ExtendedNestingGraph.h.

◆ layer()

const ENGLayer& ogdf::ExtendedNestingGraph::layer ( int  i) const
inline

Definition at line 329 of file ExtendedNestingGraph.h.

◆ layerHierarchyTree()

const LHTreeNode* ogdf::ExtendedNestingGraph::layerHierarchyTree ( int  i) const
inline

Definition at line 328 of file ExtendedNestingGraph.h.

◆ lca() [1/2]

LHTreeNode* ogdf::ExtendedNestingGraph::lca ( LHTreeNode uNode,
LHTreeNode vNode,
LHTreeNode **  uChild,
LHTreeNode **  vChild 
) const
protected

◆ lca() [2/2]

cluster ogdf::ExtendedNestingGraph::lca ( node  u,
node  v 
) const
protected

◆ moveDown()

void ogdf::ExtendedNestingGraph::moveDown ( node  v,
const SListPure< node > &  successors,
NodeArray< int > &  level 
)
protected

◆ numberOfLayers()

int ogdf::ExtendedNestingGraph::numberOfLayers ( ) const
inline

Definition at line 325 of file ExtendedNestingGraph.h.

◆ origEdge()

edge ogdf::ExtendedNestingGraph::origEdge ( edge  e) const
inline

Definition at line 305 of file ExtendedNestingGraph.h.

◆ originalCluster()

cluster ogdf::ExtendedNestingGraph::originalCluster ( node  v) const
inline

Definition at line 307 of file ExtendedNestingGraph.h.

◆ origNode()

node ogdf::ExtendedNestingGraph::origNode ( node  v) const
inline

Definition at line 304 of file ExtendedNestingGraph.h.

◆ parent() [1/2]

cluster ogdf::ExtendedNestingGraph::parent ( cluster  c) const
inline

Definition at line 309 of file ExtendedNestingGraph.h.

◆ parent() [2/2]

cluster ogdf::ExtendedNestingGraph::parent ( node  v) const
inline

Definition at line 308 of file ExtendedNestingGraph.h.

◆ permute()

void ogdf::ExtendedNestingGraph::permute ( )

◆ pos()

int ogdf::ExtendedNestingGraph::pos ( node  v) const
inline

Definition at line 327 of file ExtendedNestingGraph.h.

◆ rank()

int ogdf::ExtendedNestingGraph::rank ( node  v) const
inline

Definition at line 326 of file ExtendedNestingGraph.h.

◆ reachable()

bool ogdf::ExtendedNestingGraph::reachable ( node  v,
node  u,
SListPure< node > &  successors 
)
protected

◆ reduceCrossings() [1/2]

RCCrossings ogdf::ExtendedNestingGraph::reduceCrossings ( int  i,
bool  dirTopDown 
)

◆ reduceCrossings() [2/2]

RCCrossings ogdf::ExtendedNestingGraph::reduceCrossings ( LHTreeNode cNode,
bool  dirTopDown 
)
protected

◆ removeAuxNodes()

void ogdf::ExtendedNestingGraph::removeAuxNodes ( )
private

◆ removeTopBottomEdges()

void ogdf::ExtendedNestingGraph::removeTopBottomEdges ( )

◆ restorePos()

void ogdf::ExtendedNestingGraph::restorePos ( )

◆ storeCurrentPos()

void ogdf::ExtendedNestingGraph::storeCurrentPos ( )

◆ top()

node ogdf::ExtendedNestingGraph::top ( cluster  cOrig) const
inline

Definition at line 296 of file ExtendedNestingGraph.h.

◆ topRank()

int ogdf::ExtendedNestingGraph::topRank ( cluster  c) const
inline

Definition at line 299 of file ExtendedNestingGraph.h.

◆ tryEdge()

bool ogdf::ExtendedNestingGraph::tryEdge ( node  u,
node  v,
Graph G,
NodeArray< int > &  level 
)
protected

◆ type()

NodeType ogdf::ExtendedNestingGraph::type ( node  v) const
inline

Definition at line 303 of file ExtendedNestingGraph.h.

◆ verticalSegment()

bool ogdf::ExtendedNestingGraph::verticalSegment ( edge  e) const
inline

Definition at line 323 of file ExtendedNestingGraph.h.

Member Data Documentation

◆ m_aeLevel

NodeArray<int> ogdf::ExtendedNestingGraph::m_aeLevel
private

Definition at line 406 of file ExtendedNestingGraph.h.

◆ m_aeVisited

NodeArray<bool> ogdf::ExtendedNestingGraph::m_aeVisited
private

Definition at line 407 of file ExtendedNestingGraph.h.

◆ m_auxDeg

NodeArray<int> ogdf::ExtendedNestingGraph::m_auxDeg
private

Definition at line 408 of file ExtendedNestingGraph.h.

◆ m_bottomNode

ClusterArray<node> ogdf::ExtendedNestingGraph::m_bottomNode
private

Definition at line 382 of file ExtendedNestingGraph.h.

◆ m_bottomRank

ClusterArray<int> ogdf::ExtendedNestingGraph::m_bottomRank
private

Definition at line 384 of file ExtendedNestingGraph.h.

◆ m_CGC

ClusterGraphCopy ogdf::ExtendedNestingGraph::m_CGC
private

copy of original cluster graph

Definition at line 373 of file ExtendedNestingGraph.h.

◆ m_copy

NodeArray<node> ogdf::ExtendedNestingGraph::m_copy
private

Definition at line 377 of file ExtendedNestingGraph.h.

◆ m_copyEdge

EdgeArray<List<edge> > ogdf::ExtendedNestingGraph::m_copyEdge
private

Definition at line 390 of file ExtendedNestingGraph.h.

◆ m_layer

Array<ENGLayer> ogdf::ExtendedNestingGraph::m_layer
private

Definition at line 398 of file ExtendedNestingGraph.h.

◆ m_mark

ClusterArray<cluster> ogdf::ExtendedNestingGraph::m_mark
mutableprivate

Definition at line 411 of file ExtendedNestingGraph.h.

◆ m_markedClusters

SListPure<cluster> ogdf::ExtendedNestingGraph::m_markedClusters
mutableprivate

Definition at line 412 of file ExtendedNestingGraph.h.

◆ m_markedClustersTree

SListPure<cluster> ogdf::ExtendedNestingGraph::m_markedClustersTree
mutableprivate

Definition at line 415 of file ExtendedNestingGraph.h.

◆ m_markTree

ClusterArray<LHTreeNode*> ogdf::ExtendedNestingGraph::m_markTree
mutableprivate

Definition at line 416 of file ExtendedNestingGraph.h.

◆ m_numLayers

int ogdf::ExtendedNestingGraph::m_numLayers
private

Definition at line 395 of file ExtendedNestingGraph.h.

◆ m_origEdge

EdgeArray<edge> ogdf::ExtendedNestingGraph::m_origEdge
private

Definition at line 391 of file ExtendedNestingGraph.h.

◆ m_origNode

NodeArray<node> ogdf::ExtendedNestingGraph::m_origNode
private

Definition at line 378 of file ExtendedNestingGraph.h.

◆ m_pos

NodeArray<int> ogdf::ExtendedNestingGraph::m_pos
private

Definition at line 400 of file ExtendedNestingGraph.h.

◆ m_rank

NodeArray<int> ogdf::ExtendedNestingGraph::m_rank
private

Definition at line 394 of file ExtendedNestingGraph.h.

◆ m_secondPath

cluster ogdf::ExtendedNestingGraph::m_secondPath
mutableprivate

Definition at line 413 of file ExtendedNestingGraph.h.

◆ m_secondPathTo

node ogdf::ExtendedNestingGraph::m_secondPathTo
mutableprivate

Definition at line 414 of file ExtendedNestingGraph.h.

◆ m_topNode

ClusterArray<node> ogdf::ExtendedNestingGraph::m_topNode
private

Definition at line 381 of file ExtendedNestingGraph.h.

◆ m_topRank

ClusterArray<int> ogdf::ExtendedNestingGraph::m_topRank
private

Definition at line 383 of file ExtendedNestingGraph.h.

◆ m_type

NodeArray<NodeType> ogdf::ExtendedNestingGraph::m_type
private

Definition at line 387 of file ExtendedNestingGraph.h.

◆ m_vertical

EdgeArray<bool> ogdf::ExtendedNestingGraph::m_vertical
private

Definition at line 403 of file ExtendedNestingGraph.h.


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