Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

MMVariableEmbeddingInserter.h
Go to the documentation of this file.
1 
32 #pragma once
33 
37 #include <ogdf/basic/FaceArray.h>
38 #include <ogdf/basic/NodeSet.h>
39 #include <ogdf/basic/tuples.h>
40 
41 namespace ogdf {
42 
44 
48 {
49 public:
52 
53  // destruction
55 
56 
64  m_rrOption = rrOption;
65  }
66 
69  return m_rrOption;
70  }
71 
72 
74 
79  void percentMostCrossed(double percent) {
80  m_percentMostCrossed = percent;
81  }
82 
84  double percentMostCrossed() const {
85  return m_percentMostCrossed;
86  }
87 
88 
89 private:
90  class Block;
91  class ExpandedSkeleton;
92 
94 
95  struct AnchorNodeInfo {
96  AnchorNodeInfo() { m_adj_1 = m_adj_2 = nullptr; }
98  m_adj_1 = adj;
99  m_adj_2 = nullptr;
100  }
102  m_adj_1 = adj_1;
103  m_adj_2 = adj_2;
104  }
105 
108  };
109 
110  enum class PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };
111 
112  struct Paths {
113  Paths() :
114  m_addPartLeft(3), m_addPartRight(3),
115  m_paths(3),
116  m_src(0,2,nullptr), m_tgt(0,2,nullptr),
117  m_pred(0,2,PathType::pathToEdge)
118  { }
119 
126  };
127 
137  virtual ReturnType doCall(
138  PlanRepExpansion &PG,
139  const List<edge> &origEdges,
140  const EdgeArray<bool> *forbiddenEdgeOrig) override;
141 
150  void collectAnchorNodes(
151  node v,
152  NodeSet<> &nodes,
153  const PlanRepExpansion::NodeSplit *nsParent) const;
154 
163  void findSourcesAndTargets(
164  node src, node tgt,
165  NodeSet<> &sources,
166  NodeSet<> &targets) const;
167 
174  void anchorNodes(
175  node vOrig,
176  NodeSet<> &nodes) const;
177 
178  static node commonDummy(
179  NodeSet<> &sources,
180  NodeSet<> &targets);
181 
191  void insert(List<Crossing> &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd);
192 
193  node prepareAnchorNode(
194  const AnchorNodeInfo &anchor,
195  node vOrig,
196  bool isSrc,
197  edge &eExtra);
198 
199  void preprocessInsertionPath(
200  const AnchorNodeInfo &srcInfo,
201  const AnchorNodeInfo &tgtInfo,
202  node srcOrig,
203  node tgtOrig,
204  node &src,
205  node &tgt,
206  edge &eSrc,
207  edge &eTgt);
208 
209  node preparePath(
210  node vAnchor,
211  adjEntry adjPath,
212  bool bOrigEdge,
213  node vOrig);
214 
215  void findPseudos(
216  node vDummy,
217  adjEntry adjSrc,
218  AnchorNodeInfo &infoSrc,
219  SListPure<node> &pseudos);
220 
221  void insertWithCommonDummy(
222  edge eOrig,
223  node vDummy,
224  node &src,
225  node &tgt);
226 
236  bool dfsVertex(node v,
237  int parent,
238  List<Crossing> &eip,
239  AnchorNodeInfo &vStart,
240  AnchorNodeInfo &vEnd);
241 
252  bool dfsBlock(int i,
253  node parent,
254  node &repS,
255  List<Crossing> &eip,
256  AnchorNodeInfo &vStart,
257  AnchorNodeInfo &vEnd);
258 
259  bool pathSearch(node v, edge parent, const Block &BC, List<edge> &path);
260 
269  void blockInsert(
270  Block &BC,
271  List<Crossing> &L,
272  AnchorNodeInfo &srcInfo,
273  AnchorNodeInfo &tgtInfo);
274 
275  void buildSubpath(
276  node v,
277  edge eIn,
278  edge eOut,
279  Paths &paths,
280  bool &bPathToEdge,
281  bool &bPathToSrc,
282  bool &bPathToTgt,
283  ExpandedSkeleton &Exp);
284 
285  void contractSplitIfReq(node u);
286  void convertDummy(
287  node u,
288  node vOrig,
290 
291  void writeEip(const List<Crossing> &eip);
292 
295 
297 
300 
305 
308 };
309 
310 }
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo::m_adj_2
adjEntry m_adj_2
Definition: MMVariableEmbeddingInserter.h:107
MMEdgeInsertionModule.h
Declaration of interface for minor-monotone edge insertion algorithms.
NodeSet.h
Declaration and implementation of ogdf::NodeSet.
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::MMVariableEmbeddingInserter::Paths::m_src
Array< AnchorNodeInfo > m_src
Definition: MMVariableEmbeddingInserter.h:123
ogdf::PlanRepExpansion::Crossing
Definition: PlanRepExpansion.h:57
ogdf::MMVariableEmbeddingInserter::Paths::m_addPartLeft
Array< SList< adjEntry > > m_addPartLeft
Definition: MMVariableEmbeddingInserter.h:120
ogdf::MMVariableEmbeddingInserter::percentMostCrossed
void percentMostCrossed(double percent)
Sets the portion of most crossed edges used during postprocessing.
Definition: MMVariableEmbeddingInserter.h:79
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo::AnchorNodeInfo
AnchorNodeInfo(adjEntry adj_1, adjEntry adj_2)
Definition: MMVariableEmbeddingInserter.h:101
ogdf::MMVariableEmbeddingInserter
Minor-monotone edge insertion with variable embedding.
Definition: MMVariableEmbeddingInserter.h:47
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo::m_adj_1
adjEntry m_adj_1
Definition: MMVariableEmbeddingInserter.h:106
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::MMVariableEmbeddingInserter::m_pTargets
NodeSet * m_pTargets
The set of possible end nodes of an insertion path.
Definition: MMVariableEmbeddingInserter.h:299
ogdf::MMVariableEmbeddingInserter::removeReinsert
RemoveReinsertType removeReinsert() const
Returns the current setting of the remove-reinsert option.
Definition: MMVariableEmbeddingInserter.h:68
ogdf::MMVariableEmbeddingInserter::Paths::m_pred
Array< PathType > m_pred
Definition: MMVariableEmbeddingInserter.h:125
ogdf::MMVariableEmbeddingInserter::Paths
Definition: MMVariableEmbeddingInserter.h:112
ogdf::PlanRepExpansion
Planarized representations (of a connected component) of a graph.
Definition: PlanRepExpansion.h:54
ogdf::MMVariableEmbeddingInserter::Paths::m_tgt
Array< AnchorNodeInfo > m_tgt
Definition: MMVariableEmbeddingInserter.h:124
RemoveReinsertType.h
Definition of RemoveReinsertType (used for postprocessing in edge insertion algorithms).
ogdf::Block
Class representing idea of Blocks used in GlobalSifting and GridSifting algorithms.
Definition: BlockOrder.h:72
ogdf::MMVariableEmbeddingInserter::m_forbiddenEdgeOrig
const EdgeArray< bool > * m_forbiddenEdgeOrig
Definition: MMVariableEmbeddingInserter.h:307
ogdf::NodeSet
Node sets.
Definition: NodeSet.h:54
ogdf::MMVariableEmbeddingInserter::percentMostCrossed
double percentMostCrossed() const
Returns the current setting of the option percentMostCrossed.
Definition: MMVariableEmbeddingInserter.h:84
ogdf::MMVariableEmbeddingInserter::m_pPG
PlanRepExpansion * m_pPG
Pointer to the planarized expansion.
Definition: MMVariableEmbeddingInserter.h:296
FaceArray.h
declaration and implementation of FaceArray class
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::EdgeArray< bool >
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::MMVariableEmbeddingInserter::removeReinsert
void removeReinsert(RemoveReinsertType rrOption)
Sets the remove-reinsert option for postprocessing.
Definition: MMVariableEmbeddingInserter.h:62
ogdf::MMVariableEmbeddingInserter::Paths::m_addPartRight
Array< SList< adjEntry > > m_addPartRight
Definition: MMVariableEmbeddingInserter.h:121
ogdf::MMVariableEmbeddingInserter::m_edgeB
Array< SList< edge > > m_edgeB
The list of edges in block i.
Definition: MMVariableEmbeddingInserter.h:303
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo::AnchorNodeInfo
AnchorNodeInfo(adjEntry adj)
Definition: MMVariableEmbeddingInserter.h:97
ogdf::MMVariableEmbeddingInserter::m_nodeB
Array< SList< node > > m_nodeB
The list of nodes in block i.
Definition: MMVariableEmbeddingInserter.h:302
ogdf::MMVariableEmbeddingInserter::~MMVariableEmbeddingInserter
virtual ~MMVariableEmbeddingInserter()
Definition: MMVariableEmbeddingInserter.h:54
ogdf::MMVariableEmbeddingInserter::PathType
PathType
Definition: MMVariableEmbeddingInserter.h:110
ogdf::MMVariableEmbeddingInserter::m_compV
NodeArray< SList< int > > m_compV
The list of blocks containing a node v.
Definition: MMVariableEmbeddingInserter.h:301
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::MMEdgeInsertionModule
Interface for minor-monotone edge insertion algorithms.
Definition: MMEdgeInsertionModule.h:46
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::MMVariableEmbeddingInserter::Paths::m_paths
Array< List< Crossing > > m_paths
Definition: MMVariableEmbeddingInserter.h:122
ogdf::List< edge >
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo::AnchorNodeInfo
AnchorNodeInfo()
Definition: MMVariableEmbeddingInserter.h:96
ogdf::MMVariableEmbeddingInserter::m_GtoBC
NodeArray< node > m_GtoBC
Maps a node in the planarized expansion to the corresponding node in block.
Definition: MMVariableEmbeddingInserter.h:304
CombinatorialEmbedding.h
Declaration of CombinatorialEmbedding and face.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::RemoveReinsertType
RemoveReinsertType
The postprocessing method for edge insertion algorithms.
Definition: RemoveReinsertType.h:41
ogdf::MMVariableEmbeddingInserter::m_conFinished
bool m_conFinished
Stores if a possible target node in a block has already been found.
Definition: MMVariableEmbeddingInserter.h:306
ogdf::PlanRepExpansion::NodeSplit
Representation of a node split in a planarized expansion.
Definition: PlanRepExpansion.h:78
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::MMVariableEmbeddingInserter::m_rrOption
RemoveReinsertType m_rrOption
The remove-reinsert option.
Definition: MMVariableEmbeddingInserter.h:293
ogdf::MMVariableEmbeddingInserter::Paths::Paths
Paths()
Definition: MMVariableEmbeddingInserter.h:113
ogdf::MMVariableEmbeddingInserter::AnchorNodeInfo
Definition: MMVariableEmbeddingInserter.h:95
ogdf::MMVariableEmbeddingInserter::m_pSources
NodeSet * m_pSources
The set of possible start nodes of an insertion path.
Definition: MMVariableEmbeddingInserter.h:298
ogdf::RemoveReinsertType::IncInserted
@ IncInserted
Postprocessing for (so far) inserted edges after each edge insertion.
ogdf::Module::ReturnType
ReturnType
The return type of a module.
Definition: Module.h:51
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
tuples.h
Declaration and implementation of class Tuple2, Tuple3 and Tuple4.
ogdf::MMVariableEmbeddingInserter::m_percentMostCrossed
double m_percentMostCrossed
The percentMostCrossed option.
Definition: MMVariableEmbeddingInserter.h:294