Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CommonCompactionConstraintGraphBase Class Referenceabstract

A common base class for ogdf::GridCompactionConstraintGraphBase and ogdf::CompactionConstraintGraphBase. More...

#include <ogdf/orthogonal/internal/CommonCompactionConstraintGraphBase.h>

+ Inheritance diagram for ogdf::CommonCompactionConstraintGraphBase:

Public Member Functions

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

 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

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

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

A common base class for ogdf::GridCompactionConstraintGraphBase and ogdf::CompactionConstraintGraphBase.

Definition at line 53 of file CommonCompactionConstraintGraphBase.h.

Constructor & Destructor Documentation

◆ CommonCompactionConstraintGraphBase()

ogdf::CommonCompactionConstraintGraphBase::CommonCompactionConstraintGraphBase ( const OrthoRep OR,
const PlanRep PG,
OrthoDir  arcDir,
int  costAssoc 
)
protected

Build constraint graph with basic arcs.

Member Function Documentation

◆ basicArc()

edge ogdf::CommonCompactionConstraintGraphBase::basicArc ( edge  e) const
inline

Returns constraint arc representing input edge e in constraint graph.

Definition at line 141 of file CommonCompactionConstraintGraphBase.h.

◆ computeTopologicalSegmentNum()

void ogdf::CommonCompactionConstraintGraphBase::computeTopologicalSegmentNum ( NodeArray< int > &  topNum)

Computes topological numbering on the segments of the constraint graph.

◆ cost()

int ogdf::CommonCompactionConstraintGraphBase::cost ( edge  e) const
inline

Returns cost of edge e.

Precondition
e is an edge in the constraint graph

Definition at line 116 of file CommonCompactionConstraintGraphBase.h.

◆ embed()

void ogdf::CommonCompactionConstraintGraphBase::embed ( )

Embeds constraint graph such that all sources and sinks lie in a common face.

◆ extraNode()

bool ogdf::CommonCompactionConstraintGraphBase::extraNode ( node  v) const
inline

Returns node status.

Definition at line 179 of file CommonCompactionConstraintGraphBase.h.

◆ extraRep()

node ogdf::CommonCompactionConstraintGraphBase::extraRep ( node  v) const
inline

Returns extraNode existing anchor representant.

Definition at line 121 of file CommonCompactionConstraintGraphBase.h.

◆ fixOnBorder()

bool ogdf::CommonCompactionConstraintGraphBase::fixOnBorder ( edge  e) const
inline

Returns true if edge is subject to length fixation if length < sep.

Definition at line 131 of file CommonCompactionConstraintGraphBase.h.

◆ getGraph() [1/2]

Graph& ogdf::CommonCompactionConstraintGraphBase::getGraph ( )
inline

Definition at line 89 of file CommonCompactionConstraintGraphBase.h.

◆ getGraph() [2/2]

const Graph& ogdf::CommonCompactionConstraintGraphBase::getGraph ( ) const
inline

Returns underlying graph.

Definition at line 88 of file CommonCompactionConstraintGraphBase.h.

◆ getLengthString()

virtual string ogdf::CommonCompactionConstraintGraphBase::getLengthString ( edge  e) const
protectedpure virtual

◆ getOrthoRep()

const OrthoRep& ogdf::CommonCompactionConstraintGraphBase::getOrthoRep ( ) const
inline

Returns underlying OrthoRep.

Definition at line 94 of file CommonCompactionConstraintGraphBase.h.

◆ getPlanRep()

const PlanRep& ogdf::CommonCompactionConstraintGraphBase::getPlanRep ( ) const
inline

Definition at line 98 of file CommonCompactionConstraintGraphBase.h.

◆ nodesIn()

const SListPure<node>& ogdf::CommonCompactionConstraintGraphBase::nodesIn ( node  v) const
inline

Returns list of nodes contained in segment v.

Precondition
v is in the constraint graph

Definition at line 104 of file CommonCompactionConstraintGraphBase.h.

◆ onBorder()

bool ogdf::CommonCompactionConstraintGraphBase::onBorder ( edge  e) const
inline

Returns true if edge lies on cage border.

Definition at line 126 of file CommonCompactionConstraintGraphBase.h.

◆ pathNodeOf()

node ogdf::CommonCompactionConstraintGraphBase::pathNodeOf ( node  v) const
inline

Returns the segment (path node in constraint graph) containing v.

Precondition
v is a node in the associated planarized representation

Definition at line 110 of file CommonCompactionConstraintGraphBase.h.

◆ removeRedundantVisibArcs()

void ogdf::CommonCompactionConstraintGraphBase::removeRedundantVisibArcs ( SListPure< Tuple2< node, node >> &  visibArcs)

Removes "arcs" from visibArcs which we already have in the constraint graph (as basic arcs)

◆ typeOf()

ConstraintEdgeType ogdf::CommonCompactionConstraintGraphBase::typeOf ( edge  e) const
inline

Returns type of edge e.

Precondition
e is an edge in the constraint graph

Definition at line 174 of file CommonCompactionConstraintGraphBase.h.

Member Data Documentation

◆ m_arcDir

OrthoDir ogdf::CommonCompactionConstraintGraphBase::m_arcDir
protected

Definition at line 72 of file CommonCompactionConstraintGraphBase.h.

◆ m_border

EdgeArray<int> ogdf::CommonCompactionConstraintGraphBase::m_border
protected

only used for cage precompaction in flowcompaction computecoords

Definition at line 65 of file CommonCompactionConstraintGraphBase.h.

◆ m_cost

EdgeArray<int> ogdf::CommonCompactionConstraintGraphBase::m_cost
protected

cost of an edge

Definition at line 62 of file CommonCompactionConstraintGraphBase.h.

◆ m_edgeToBasicArc

EdgeArray<edge> ogdf::CommonCompactionConstraintGraphBase::m_edgeToBasicArc
protected

basic arc representing an edge in PG

Definition at line 60 of file CommonCompactionConstraintGraphBase.h.

◆ m_extraNode

NodeArray<bool> ogdf::CommonCompactionConstraintGraphBase::m_extraNode
protected

Node does not represent drawing node as we dont have positions we save a drawing representant and an offset.

true iff node does not represent drawing node

Definition at line 69 of file CommonCompactionConstraintGraphBase.h.

◆ m_extraRep

NodeArray<node> ogdf::CommonCompactionConstraintGraphBase::m_extraRep
protected

existing representant of extranodes position anchor

Definition at line 70 of file CommonCompactionConstraintGraphBase.h.

◆ m_oppArcDir

OrthoDir ogdf::CommonCompactionConstraintGraphBase::m_oppArcDir
protected

Definition at line 73 of file CommonCompactionConstraintGraphBase.h.

◆ m_originalEdge

NodeArray<edge> ogdf::CommonCompactionConstraintGraphBase::m_originalEdge
protected

save edge for the basic arcs

Definition at line 75 of file CommonCompactionConstraintGraphBase.h.

◆ m_path

NodeArray<SListPure<node> > ogdf::CommonCompactionConstraintGraphBase::m_path
protected

list of nodes contained in a segment

Definition at line 58 of file CommonCompactionConstraintGraphBase.h.

◆ m_pathNode

NodeArray<node> ogdf::CommonCompactionConstraintGraphBase::m_pathNode
protected

segment containing a node in PG

Definition at line 59 of file CommonCompactionConstraintGraphBase.h.

◆ m_pOR

const OrthoRep* ogdf::CommonCompactionConstraintGraphBase::m_pOR
protected

Definition at line 55 of file CommonCompactionConstraintGraphBase.h.

◆ m_pPR

const PlanRep* ogdf::CommonCompactionConstraintGraphBase::m_pPR
protected

Definition at line 56 of file CommonCompactionConstraintGraphBase.h.

◆ m_sinks

SList<node> ogdf::CommonCompactionConstraintGraphBase::m_sinks
protected

Definition at line 78 of file CommonCompactionConstraintGraphBase.h.

◆ m_sources

SList<node> ogdf::CommonCompactionConstraintGraphBase::m_sources
protected

Definition at line 77 of file CommonCompactionConstraintGraphBase.h.

◆ m_type

EdgeArray<ConstraintEdgeType> ogdf::CommonCompactionConstraintGraphBase::m_type
protected

constraint type for each edge

Definition at line 63 of file CommonCompactionConstraintGraphBase.h.


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