Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CompactionConstraintGraphBase Class Reference

Class implementing template-parameter-independent behaviour of ogdf::CompactionConstraintGraph. More...

#include <ogdf/orthogonal/CompactionConstraintGraph.h>

+ Inheritance diagram for ogdf::CompactionConstraintGraphBase:

Public Member Functions

void align (bool b)
 Triggers alignment (=>some special edge handling to support al.) More...
 
bool alignmentArc (edge e) const
 Returns if arc is important for alignment. These are the arcs representing node to gen. merger edges. More...
 
edge pathToOriginal (node v)
 
Edge property getters
bool verticalGen (edge e) const
 Returns true if e is vertical edge in PlanRepUML hierarchy. More...
 
bool verticalArc (edge e) const
 Returns true if e is basic arc of vertical edge in PlanRepUML hierarchy. More...
 
- Public Member Functions inherited from ogdf::CommonCompactionConstraintGraphBase
edge basicArc (edge e) const
 Returns constraint arc representing input edge e in constraint graph. More...
 
void computeTopologicalSegmentNum (NodeArray< int > &topNum)
 Computes topological numbering on the segments of the constraint graph. More...
 
void embed ()
 Embeds constraint graph such that all sources and sinks lie in a common face. More...
 
bool extraNode (node v) const
 Returns node status. More...
 
void removeRedundantVisibArcs (SListPure< Tuple2< node, node >> &visibArcs)
 Removes "arcs" from visibArcs which we already have in the constraint graph (as basic arcs) More...
 
ConstraintEdgeType typeOf (edge e) const
 Returns type of edge e. More...
 
const GraphgetGraph () const
 Returns underlying graph. More...
 
GraphgetGraph ()
 
const OrthoRepgetOrthoRep () const
 Returns underlying OrthoRep. More...
 
const PlanRepgetPlanRep () const
 
const SListPure< node > & nodesIn (node v) const
 Returns list of nodes contained in segment v. More...
 
node pathNodeOf (node v) const
 Returns the segment (path node in constraint graph) containing v. More...
 
int cost (edge e) const
 Returns cost of edge e. More...
 
node extraRep (node v) const
 Returns extraNode existing anchor representant. More...
 
bool onBorder (edge e) const
 Returns true if edge lies on cage border. More...
 
bool fixOnBorder (edge e) const
 Returns true if edge is subject to length fixation if length < sep. More...
 

Protected Member Functions

 CompactionConstraintGraphBase (const OrthoRep &OR, const PlanRep &PG, OrthoDir arcDir, int costGen=1, int costAssoc=1, bool align=false)
 Construction. More...
 
- Protected Member Functions inherited from ogdf::CommonCompactionConstraintGraphBase
 CommonCompactionConstraintGraphBase (const OrthoRep &OR, const PlanRep &PG, OrthoDir arcDir, int costAssoc)
 Build constraint graph with basic arcs. More...
 
virtual string getLengthString (edge e) const =0
 
- 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...
 
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 Attributes

EdgeArray< bool > m_alignmentArc
 Basic arcs that have to be short for alignment (node to gen expander) More...
 
int m_edgeCost [2]
 
NodeArray< edgem_pathToEdge
 save the (single!) edge (segment) for a pathNode More...
 
EdgeArray< bool > m_verticalArc
 arc corresponding to such an edge More...
 
EdgeArray< bool > m_verticalGen
 generalization that runs vertical relative to hierarchy More...
 
- Protected Attributes inherited from ogdf::CommonCompactionConstraintGraphBase
OrthoDir m_arcDir
 
EdgeArray< int > m_border
 only used for cage precompaction in flowcompaction computecoords More...
 
EdgeArray< int > m_cost
 cost of an edge More...
 
EdgeArray< edgem_edgeToBasicArc
 basic arc representing an edge in PG More...
 
NodeArray< bool > m_extraNode
 Node does not represent drawing node as we dont have positions we save a drawing representant and an offset. More...
 
NodeArray< nodem_extraRep
 existing representant of extranodes position anchor More...
 
OrthoDir m_oppArcDir
 
NodeArray< edgem_originalEdge
 save edge for the basic arcs More...
 
NodeArray< SListPure< node > > m_path
 list of nodes contained in a segment More...
 
NodeArray< nodem_pathNode
 segment containing a node in PG More...
 
const OrthoRepm_pOR
 
const PlanRepm_pPR
 
SList< nodem_sinks
 
SList< nodem_sources
 
EdgeArray< ConstraintEdgeTypem_type
 constraint type for each edge More...
 
- Protected 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...
 

Private Member Functions

void dfsInsertPathVertex (node v, node pathVertex, NodeArray< bool > &visited, const NodeArray< node > &genOpposite)
 
void insertBasicArcs (const PlanRep &PG)
 
void insertPathVertices (const PlanRep &PG)
 

Private Attributes

bool m_align
 

Additional Inherited Members

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

Detailed Description

Class implementing template-parameter-independent behaviour of ogdf::CompactionConstraintGraph.

Definition at line 45 of file CompactionConstraintGraph.h.

Constructor & Destructor Documentation

◆ CompactionConstraintGraphBase()

ogdf::CompactionConstraintGraphBase::CompactionConstraintGraphBase ( const OrthoRep OR,
const PlanRep PG,
OrthoDir  arcDir,
int  costGen = 1,
int  costAssoc = 1,
bool  align = false 
)
protected

Construction.

Member Function Documentation

◆ align()

void ogdf::CompactionConstraintGraphBase::align ( bool  b)
inline

Triggers alignment (=>some special edge handling to support al.)

Definition at line 61 of file CompactionConstraintGraph.h.

◆ alignmentArc()

bool ogdf::CompactionConstraintGraphBase::alignmentArc ( edge  e) const
inline

Returns if arc is important for alignment. These are the arcs representing node to gen. merger edges.

Definition at line 65 of file CompactionConstraintGraph.h.

◆ dfsInsertPathVertex()

void ogdf::CompactionConstraintGraphBase::dfsInsertPathVertex ( node  v,
node  pathVertex,
NodeArray< bool > &  visited,
const NodeArray< node > &  genOpposite 
)
private

◆ insertBasicArcs()

void ogdf::CompactionConstraintGraphBase::insertBasicArcs ( const PlanRep PG)
private

◆ insertPathVertices()

void ogdf::CompactionConstraintGraphBase::insertPathVertices ( const PlanRep PG)
private

◆ pathToOriginal()

edge ogdf::CompactionConstraintGraphBase::pathToOriginal ( node  v)
inline

Definition at line 67 of file CompactionConstraintGraph.h.

◆ verticalArc()

bool ogdf::CompactionConstraintGraphBase::verticalArc ( edge  e) const
inline

Returns true if e is basic arc of vertical edge in PlanRepUML hierarchy.

Precondition
e is arc in the constraint graph

Definition at line 56 of file CompactionConstraintGraph.h.

◆ verticalGen()

bool ogdf::CompactionConstraintGraphBase::verticalGen ( edge  e) const
inline

Returns true if e is vertical edge in PlanRepUML hierarchy.

Definition at line 52 of file CompactionConstraintGraph.h.

Member Data Documentation

◆ m_align

bool ogdf::CompactionConstraintGraphBase::m_align
private

Definition at line 90 of file CompactionConstraintGraph.h.

◆ m_alignmentArc

EdgeArray<bool> ogdf::CompactionConstraintGraphBase::m_alignmentArc
protected

Basic arcs that have to be short for alignment (node to gen expander)

Definition at line 84 of file CompactionConstraintGraph.h.

◆ m_edgeCost

int ogdf::CompactionConstraintGraphBase::m_edgeCost[2]
protected

Definition at line 77 of file CompactionConstraintGraph.h.

◆ m_pathToEdge

NodeArray<edge> ogdf::CompactionConstraintGraphBase::m_pathToEdge
protected

save the (single!) edge (segment) for a pathNode

Definition at line 86 of file CompactionConstraintGraph.h.

◆ m_verticalArc

EdgeArray<bool> ogdf::CompactionConstraintGraphBase::m_verticalArc
protected

arc corresponding to such an edge

Definition at line 81 of file CompactionConstraintGraph.h.

◆ m_verticalGen

EdgeArray<bool> ogdf::CompactionConstraintGraphBase::m_verticalGen
protected

generalization that runs vertical relative to hierarchy

Definition at line 80 of file CompactionConstraintGraph.h.


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