Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

UpwardPlanRep.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/GraphCopy.h>
36 
37 
38 namespace ogdf {
39 
40 
52 {
53 public:
54 
56 
57 #if 0
58  //debug only
60 #endif
61 
62  /* @{
63  * \brief Creates a planarized representation with respect to \p Gamma.
64  * Gamma muss be an upward planar embedding with a fixed ext. face
65  * Precondition: the graph is a single source graph
66  */
67 
68  explicit UpwardPlanRep(const CombinatorialEmbedding &Gamma); //upward planar embedding with a fixed ext. face
69 
70  UpwardPlanRep(const GraphCopy &GC, // must be upward embedded and single source
71  adjEntry adj_ext); // the right face of this adjEntry is the external face
72 
74  UpwardPlanRep(const UpwardPlanRep &UPR);
75 
77  UpwardPlanRep(): GraphCopy(), isAugmented(false), t_hat(nullptr), s_hat(nullptr), extFaceHandle(nullptr), crossings(0) // multisources(false)
78  {
79  m_Gamma.init(*this);
80  m_isSinkArc.init(*this, false);
81  m_isSourceArc.init(*this, false);
82  }
83 
84  virtual ~UpwardPlanRep() {}
85 
87  void insertEdgePathEmbedded(
88  edge eOrig,
89  SList<adjEntry> crossedEdges,
90  EdgeArray<int> &cost);
91 
93  // pred. the graph muss be a sinlge source graph
94  // We construct node t and connect the sink-switches with t. The new arcs are sSinkArc.
95  // For simplicity we construct an additional edge (t,t_hat) (the extFaceArc), where t_hat is the super sink.
96  void augment();
97 
99  bool augmented() const { return isAugmented; }
100 
102  const CombinatorialEmbedding & getEmbedding() const {return m_Gamma;}
103 
104  CombinatorialEmbedding & getEmbedding() {return m_Gamma;}
105 
106  node getSuperSink() const {return t_hat;}
107 
108  node getSuperSource() const {return s_hat;}
109 
110  int numberOfCrossings() const {return crossings;}
111 
113  UpwardPlanRep &operator=(const UpwardPlanRep &copy);
114 
115  bool isSinkArc(edge e) const {return m_isSinkArc[e];}
116 
117  bool isSourceArc(edge e) const {return m_isSourceArc[e];}
118 
121  adjEntry sinkSwitchOf(node v) {return m_sinkSwitchOf[v];}
122 
124  adjEntry getAdjEntry(const CombinatorialEmbedding &Gamma, node v, face f) const;
125 
126  //return the left in edge of node v.
128  {
129  if (v->indeg() == 0)
130  return nullptr;
131 
132  adjEntry adjFound = nullptr;
133  for(adjEntry adj : v->adjEntries) {
134  if (adj->theEdge()->target() == v && adj->cyclicSucc()->theEdge()->source() == v) {
135  adjFound = adj;
136  break;
137  }
138  }
139  return adjFound;
140  }
141 
142  // debug
143  void outputFaces(const CombinatorialEmbedding &embedding) const {
144  std::cout << std::endl << "Face UPR " << std::endl;
145  for (face f : embedding.faces) {
146  std::cout << "face " << f->index() << ": ";
147  adjEntry adjNext = f->firstAdj();
148  do {
149  std::cout << adjNext->theEdge() << "; ";
150  adjNext = adjNext->faceCycleSucc();
151  } while (adjNext != f->firstAdj());
152  std::cout << std::endl;
153  }
154  if (embedding.externalFace() != nullptr)
155  std::cout << "ext. face of the graph is: " << embedding.externalFace()->index() << std::endl;
156  else
157  std::cout << "no ext. face set." << std::endl;
158  }
159 
160 
161 protected:
162 
163  bool isAugmented;
164 
166 
168 
170 
171  // sinkArk are edges which are added to transform the original graph to single sink graph.
172  // note: the extFaceHandle is a sink arc.
174 
175  // source arc are edges which are added to transform the original graph to a single source graph
177 
178  // 0 if node v is not a non-top-sink-switch of a internal face.
179  // else v is (non-top) sink-switch of f (= right face of adjEntry).
181 
182  adjEntry extFaceHandle; // the right face of this adjEntry is always the ext. face
183 
185 
186 
187 private:
188  void computeSinkSwitches();
189 
191  void initMe();
192 
193  void copyMe(const UpwardPlanRep &UPR);
194 
195  void removeSinkArcs(SList<adjEntry> &crossedEdges);
196 
197  void constructSinkArcs(face f, node t);
198 };
199 
200 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::UpwardPlanRep::m_sinkSwitchOf
NodeArray< adjEntry > m_sinkSwitchOf
Definition: UpwardPlanRep.h:180
ogdf::UpwardPlanRep::augmented
bool augmented() const
return true if graph is augmented to a single source single sink graph
Definition: UpwardPlanRep.h:99
ogdf::SubgraphUpwardPlanarizer
Takes an acyclic connected non-upward-planar graph and planarizes it, i.e., we obtain an upward-plana...
Definition: SubgraphUpwardPlanarizer.h:66
ogdf::UpwardPlanRep::m_isSinkArc
EdgeArray< bool > m_isSinkArc
Definition: UpwardPlanRep.h:173
ogdf::UpwardPlanRep::crossings
int crossings
Definition: UpwardPlanRep.h:184
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::UpwardPlanRep::~UpwardPlanRep
virtual ~UpwardPlanRep()
Definition: UpwardPlanRep.h:84
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::UpwardPlanRep::sinkSwitchOf
adjEntry sinkSwitchOf(node v)
0 if node v is not a sink switch (not the top sink switch !!) of an internal face....
Definition: UpwardPlanRep.h:121
ogdf::UpwardPlanRep::numberOfCrossings
int numberOfCrossings() const
Definition: UpwardPlanRep.h:110
ogdf::UpwardPlanRep::extFaceHandle
adjEntry extFaceHandle
Definition: UpwardPlanRep.h:182
ogdf::UpwardPlanRep::UpwardPlanRep
UpwardPlanRep()
standart constructor
Definition: UpwardPlanRep.h:77
ogdf::FixedEmbeddingUpwardEdgeInserter
Edge insertion module that inserts each edge optimally into a fixed embedding.
Definition: FixedEmbeddingUpwardEdgeInserter.h:41
ogdf::GraphCopy::init
void init(const Graph &G)
Re-initializes the copy using the graph G.
ogdf::UpwardPlanRep::getEmbedding
const CombinatorialEmbedding & getEmbedding() const
return the upward planar embedding
Definition: UpwardPlanRep.h:102
ogdf::UpwardPlanRep::isAugmented
bool isAugmented
the UpwardPlanRep is augmented to a single source and single sink graph
Definition: UpwardPlanRep.h:163
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::EdgeArray< int >
ogdf::UpwardPlanRep::m_isSourceArc
EdgeArray< bool > m_isSourceArc
Definition: UpwardPlanRep.h:176
ogdf::UpwardPlanRep::isSinkArc
bool isSinkArc(edge e) const
Definition: UpwardPlanRep.h:115
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::FaceElement::firstAdj
adjEntry firstAdj() const
Returns the first adjacency element in the face.
Definition: CombinatorialEmbedding.h:145
ogdf::UpwardPlanRep::t_hat
node t_hat
< embedding og this UpwardPlanRep
Definition: UpwardPlanRep.h:167
ogdf::UpwardPlanRep::leftInEdge
adjEntry leftInEdge(node v) const
Definition: UpwardPlanRep.h:127
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::ConstCombinatorialEmbedding::faces
internal::GraphObjectContainer< FaceElement > faces
The container containing all face objects.
Definition: CombinatorialEmbedding.h:220
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
ogdf::UpwardPlanRep::s_hat
node s_hat
the super source
Definition: UpwardPlanRep.h:169
ogdf::NodeElement::indeg
int indeg() const
Returns the indegree of the node.
Definition: Graph_d.h:206
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
GraphCopy.h
Declaration of graph copy classes.
ogdf::UpwardPlanRep::getSuperSink
node getSuperSink() const
Definition: UpwardPlanRep.h:106
ogdf::AdjElement::cyclicSucc
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition: Graph_d.h:279
ogdf::ConstCombinatorialEmbedding::externalFace
face externalFace() const
Returns the external face.
Definition: CombinatorialEmbedding.h:306
ogdf::FaceElement::index
int index() const
Returns the index of the face.
Definition: CombinatorialEmbedding.h:142
ogdf::UpwardPlanRep::m_Gamma
CombinatorialEmbedding m_Gamma
Definition: UpwardPlanRep.h:165
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::AdjElement::faceCycleSucc
adjEntry faceCycleSucc() const
Returns the cyclic successor in face.
Definition: Graph_d.h:142
ogdf::UpwardPlanRep::outputFaces
void outputFaces(const CombinatorialEmbedding &embedding) const
Definition: UpwardPlanRep.h:143
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::UpwardPlanRep
Upward planarized representations (of a connected component) of a graph.
Definition: UpwardPlanRep.h:51
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::UpwardPlanRep::isSourceArc
bool isSourceArc(edge e) const
Definition: UpwardPlanRep.h:117
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::UpwardPlanRep::getEmbedding
CombinatorialEmbedding & getEmbedding()
Definition: UpwardPlanRep.h:104
ogdf::UpwardPlanRep::getSuperSource
node getSuperSource() const
Definition: UpwardPlanRep.h:108
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111