Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

SPQRTree.h
Go to the documentation of this file.
1 
32 #pragma once
33 
36 #include <ogdf/basic/SList.h>
37 
38 
39 namespace ogdf {
40 
72 {
73 public:
75  enum class NodeType { SNode, PNode, RNode };
76 
77  // destructor
78 
79  virtual ~SPQRTree() { }
80 
83 
85  virtual const Graph &originalGraph() const=0;
86 
88  virtual const Graph &tree() const=0;
89 
91  virtual edge rootEdge() const=0;
92 
94  virtual node rootNode() const=0;
95 
97  virtual int numberOfSNodes() const=0;
98 
100  virtual int numberOfPNodes() const=0;
101 
103  virtual int numberOfRNodes() const=0;
104 
109  virtual NodeType typeOf(node v) const=0;
110 
112  virtual List<node> nodesOfType(NodeType t) const=0;
113 
118  virtual Skeleton &skeleton(node v) const=0;
119 
124  virtual const Skeleton &skeletonOfReal(edge e) const=0;
125 
130  virtual edge copyOfReal(edge e) const=0;
131 
136  void pertinentGraph(node v, PertinentGraph &Gp) const
137  {
138  if (m_cpV == nullptr) m_cpV = new NodeArray<node>(originalGraph(),nullptr);
139  NodeArray<node> &cpV = *m_cpV;
140 
141  Gp.init(v);
142  cpRec(v,Gp);
143 
144  const Skeleton &S = skeleton(v);
145 
146  edge e = Gp.m_skRefEdge = S.referenceEdge();
147  if (e != nullptr) e = Gp.m_P.newEdge(cpV[S.original(e->source())],cpV[S.original(e->target())]);
148  Gp.m_vEdge = e;
149 
150  while (!m_cpVAdded.empty()) cpV[m_cpVAdded.popFrontRet()] = nullptr;
151  }
152 
156 
161  virtual node rootTreeAt(edge e) =0;
162 
167  virtual node rootTreeAt(node v) =0;
168 
169 
170  void directSkEdge(node vT, edge e, node src)
171  {
172  OGDF_ASSERT(e != nullptr);
173  OGDF_ASSERT(src == e->source() || src == e->target());
174 
175  if(e->source() != src) skeleton(vT).getGraph().reverseEdge(e);
176  }
177 
179  {
180  Graph &M = skeleton(vT).getGraph();
181  M.reverseEdge(M.split(e));
182  }
183 
184  // !@}
185 
186 protected:
187 
192  virtual void cpRec(node v, PertinentGraph &Gp) const=0;
193 
195  edge cpAddEdge(edge eOrig, PertinentGraph &Gp) const
196  {
197  edge eP = Gp.m_P.newEdge(cpAddNode(eOrig->source(),Gp),cpAddNode(eOrig->target(),Gp));
198  Gp.m_origE[eP] = eOrig;
199  return eP;
200  }
201 
203  node cpAddNode(node vOrig, PertinentGraph &Gp) const
204  {
205  node &vP = (*m_cpV)[vOrig];
206  if (vP == nullptr) {
207  m_cpVAdded.pushBack(vOrig);
208  Gp.m_origV[vP = Gp.m_P.newNode()] = vOrig;
209  }
210  return vP;
211  }
212 
213  // auxiliary members used for computing pertinent graphs
216 };
217 
218 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::SPQRTree::m_cpVAdded
SList< node > m_cpVAdded
list of added nodes (auxiliary member)
Definition: SPQRTree.h:215
PertinentGraph.h
Declaration of class PertinentGraph.
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::Graph::split
virtual edge split(edge e)
Splits edge e into two edges introducing a new node.
ogdf::PertinentGraph::m_P
Graph m_P
actual graph
Definition: PertinentGraph.h:137
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::SPQRTree
Linear-time implementation of static SPQR-trees.
Definition: SPQRTree.h:71
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::Graph::reverseEdge
void reverseEdge(edge e)
Reverses the edge e, i.e., exchanges source and target node.
Skeleton.h
Declaration of class Skeleton.
ogdf::SPQRTree::cpAddEdge
edge cpAddEdge(edge eOrig, PertinentGraph &Gp) const
Add an edge to Gp corresponding to eOrig.
Definition: SPQRTree.h:195
ogdf::Skeleton::referenceEdge
edge referenceEdge() const
Returns the reference edge of S in M.
Definition: Skeleton.h:94
ogdf::SPQRTree::replaceSkEdgeByPeak
void replaceSkEdgeByPeak(node vT, edge e)
Definition: SPQRTree.h:178
SList.h
Declaration of singly linked lists and iterators.
ogdf::PertinentGraph::m_skRefEdge
edge m_skRefEdge
reference edge (in skeleton(m_vT))
Definition: PertinentGraph.h:139
ogdf::PertinentGraph::m_vEdge
edge m_vEdge
reference edge (in m_P)
Definition: PertinentGraph.h:138
ogdf::PertinentGraph::m_origV
NodeArray< node > m_origV
corresp.
Definition: PertinentGraph.h:141
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::EdgeStandardType::tree
@ tree
for every hyperedge e a minimal subcubic tree connecting all hypernodes incident with e together is a...
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
ogdf::SPQRTree::pertinentGraph
void pertinentGraph(node v, PertinentGraph &Gp) const
Returns the pertinent graph of tree node v in Gp.
Definition: SPQRTree.h:136
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::SPQRTree::NodeType
NodeType
The type of a tree node in T.
Definition: SPQRTree.h:75
ogdf::PertinentGraph::init
void init(node vT)
Initialization of a pertinent graph of tree node vT.
Definition: PertinentGraph.h:77
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::Skeleton
Skeleton graphs of nodes in an SPQR-tree.
Definition: Skeleton.h:61
ogdf::Skeleton::original
virtual node original(node v) const =0
Returns the vertex in the original graph G that corresponds to v.
ogdf::PertinentGraph
Pertinent graphs of nodes in an SPQR-tree.
Definition: PertinentGraph.h:59
ogdf::SPQRTree::~SPQRTree
virtual ~SPQRTree()
Definition: SPQRTree.h:79
ogdf::SPQRTree::cpAddNode
node cpAddNode(node vOrig, PertinentGraph &Gp) const
Add a node to Gp corresponding to vOrig if required.
Definition: SPQRTree.h:203
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::SPQRTree::m_cpV
NodeArray< node > * m_cpV
node in pertinent graph corresponding to an original node (auxiliary member)
Definition: SPQRTree.h:214
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::PertinentGraph::m_origE
EdgeArray< edge > m_origE
corresp.
Definition: PertinentGraph.h:142
ogdf::SPQRTree::directSkEdge
void directSkEdge(node vT, edge e, node src)
Definition: SPQRTree.h:170