Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FixedEmbeddingUpwardEdgeInserter.h
Go to the documentation of this file.
1 
32 #pragma once
33 
37 
38 namespace ogdf {
39 
42 {
43 public:
46 
48 
49 
50 private:
51 
52  bool isUpwardPlanar(Graph &G) const
53  {
55  }
56 
66  virtual ReturnType doCall(UpwardPlanRep &UPR,
67  const List<edge> &origEdges,
68  const EdgeArray<int> *costOrig = nullptr,
69  const EdgeArray<bool> *forbiddenEdgeOrig = nullptr
70  ) override;
71 
72 
73  ReturnType insertAll(UpwardPlanRep &UPR,
74  List<edge> &toInsert,
75  EdgeArray<int> &cost);
76 
77 
79  void staticLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, const List<edge> &origEdges, edge e_orig);
80 
82  void dynamicLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, face f, adjEntry e_cur);
83 
84  void nextFeasibleEdges(UpwardPlanRep &UPR, List<adjEntry> &nextEdges, face f, adjEntry e_cur, EdgeArray<bool> &locked, bool heuristic);
85 
87  void minFIP(UpwardPlanRep &UPR,
88  List<edge> &origEdges,
89  EdgeArray<int> &cost,
90  edge e_orig,
91  SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, false); }
92 
93 
94 
97  List<edge> &origEdges,
98  EdgeArray<int> &cost,
99  edge e_orig,
100  SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, true); }
101 
103  void getPath(UpwardPlanRep &UPR,
104  List<edge> &origEdges,
105  EdgeArray<int> &cost,
106  edge e_orig,
107  SList<adjEntry> &path,
108  bool heuristic);
109 
110 
112  void markUp(const Graph &G, node v, EdgeArray<bool> &markedEdges);
113 
114 
116  void markDown(const Graph &G, node v, EdgeArray<bool> &markedEdges);
117 
119  void feasibleEdges(UpwardPlanRep &UPR,
120  face f, // current face
121  adjEntry adj, // current adjEntry, right face muss be f
122  EdgeArray<bool> &locked, // we compute the dyn. locked edges on the fly with respect to e
123  List<adjEntry> &feasible, // the list of feasible edges in f with respect to e
124  bool heuristic);
125 
127  bool isConstraintFeasible(UpwardPlanRep &UPR,
128  const List<edge> &orig_edges,
129  edge e_orig,
130  adjEntry adjCurrent,
131  adjEntry adjNext, // the next adjEntry of the current insertion path
132  EdgeArray<adjEntry> &predAdj //Array to reconstruction the insertion path
133  );
134 
135 
137  bool isConstraintFeasible(UpwardPlanRep &UPR,
138  List<edge> &origEdges,
139  edge e_orig,
140  SList<adjEntry> &path);
141 };
142 
143 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::UpwardPlanarity::isUpwardPlanar_singleSource
static bool isUpwardPlanar_singleSource(const Graph &G)
Tests whether the single-source digraph G is upward planar.
UpwardEdgeInserterModule.h
Declaration of interface for edge insertion algorithms.
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::FixedEmbeddingUpwardEdgeInserter
Edge insertion module that inserts each edge optimally into a fixed embedding.
Definition: FixedEmbeddingUpwardEdgeInserter.h:41
ogdf::EdgeArray< int >
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::FixedEmbeddingUpwardEdgeInserter::FixedEmbeddingUpwardEdgeInserter
FixedEmbeddingUpwardEdgeInserter()
Creates an instance of fixed-embedding edge inserter.
Definition: FixedEmbeddingUpwardEdgeInserter.h:45
ogdf::UpwardEdgeInserterModule
Definition: UpwardEdgeInserterModule.h:39
UpwardPlanarity.h
Declaration of class UpwardPlanarity, which implements different types of algorithms testing upward p...
ogdf::List< edge >
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::FixedEmbeddingUpwardEdgeInserter::~FixedEmbeddingUpwardEdgeInserter
~FixedEmbeddingUpwardEdgeInserter()
Definition: FixedEmbeddingUpwardEdgeInserter.h:47
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::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::FixedEmbeddingUpwardEdgeInserter::isUpwardPlanar
bool isUpwardPlanar(Graph &G) const
Definition: FixedEmbeddingUpwardEdgeInserter.h:52
ogdf::UpwardPlanRep
Upward planarized representations (of a connected component) of a graph.
Definition: UpwardPlanRep.h:51
ogdf::FixedEmbeddingUpwardEdgeInserter::minFIP
void minFIP(UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
compute the minimal feasible insertion path
Definition: FixedEmbeddingUpwardEdgeInserter.h:87
ogdf::FixedEmbeddingUpwardEdgeInserter::constraintFIP
void constraintFIP(UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
compute a constraint feasible insertion path usig heuristic.
Definition: FixedEmbeddingUpwardEdgeInserter.h:96
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111