Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
FixedEmbeddingUpwardEdgeInserter.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39
42public:
45
47
48
49private:
50 bool isUpwardPlanar(Graph& G) const { return UpwardPlanarity::isUpwardPlanar_singleSource(G); }
51
62 const EdgeArray<int>* costOrig = nullptr,
63 const EdgeArray<bool>* forbiddenEdgeOrig = nullptr) override;
64
65
67
68
71 edge e_orig);
72
75
77 EdgeArray<bool>& locked, bool heuristic);
78
81 SList<adjEntry>& path) {
82 getPath(UPR, origEdges, cost, e_orig, path, false);
83 }
84
87 SList<adjEntry>& path) {
88 getPath(UPR, origEdges, cost, e_orig, path, true);
89 }
90
93 SList<adjEntry>& path, bool heuristic);
94
95
98
99
102
105 face f, // current face
106 adjEntry adj, // current adjEntry, right face muss be f
107 EdgeArray<bool>& locked, // we compute the dyn. locked edges on the fly with respect to e
108 List<adjEntry>& feasible, // the list of feasible edges in f with respect to e
109 bool heuristic);
110
114 adjEntry adjNext, // the next adjEntry of the current insertion path
115 EdgeArray<adjEntry>& predAdj //Array to reconstruction the insertion path
116 );
117
118
121 SList<adjEntry>& path);
122};
123
124}
Declaration of CombinatorialEmbedding and face.
Declaration of interface for edge insertion algorithms.
Declaration of class UpwardPlanarity, which implements different types of algorithms testing upward p...
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Faces in a combinatorial embedding.
Edge insertion module that inserts each edge optimally into a fixed embedding.
void constraintFIP(UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
compute a constraint feasible insertion path usig heuristic.
bool isConstraintFeasible(UpwardPlanRep &UPR, List< edge > &origEdges, edge e_orig, SList< adjEntry > &path)
return true if current insertion path is contraint feasible
void dynamicLock(UpwardPlanRep &UPR, EdgeArray< bool > &locked, face f, adjEntry e_cur)
compute a list of dynamic locked edges
void feasibleEdges(UpwardPlanRep &UPR, face f, adjEntry adj, EdgeArray< bool > &locked, List< adjEntry > &feasible, bool heuristic)
compute the feasible edges of the face f with respect to e
void markDown(const Graph &G, node v, EdgeArray< bool > &markedEdges)
mark the edges which dominate node v
bool isConstraintFeasible(UpwardPlanRep &UPR, const List< edge > &orig_edges, edge e_orig, adjEntry adjCurrent, adjEntry adjNext, EdgeArray< adjEntry > &predAdj)
return true if current insertion path is contraint feasible
void markUp(const Graph &G, node v, EdgeArray< bool > &markedEdges)
mark the edges which are dominates by node v
void nextFeasibleEdges(UpwardPlanRep &UPR, List< adjEntry > &nextEdges, face f, adjEntry e_cur, EdgeArray< bool > &locked, bool heuristic)
void getPath(UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path, bool heuristic)
compute an insertion path
void minFIP(UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
compute the minimal feasible insertion path
void staticLock(UpwardPlanRep &UPR, EdgeArray< bool > &locked, const List< edge > &origEdges, edge e_orig)
compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible inserti...
FixedEmbeddingUpwardEdgeInserter()
Creates an instance of fixed-embedding edge inserter.
ReturnType insertAll(UpwardPlanRep &UPR, List< edge > &toInsert, EdgeArray< int > &cost)
virtual ReturnType doCall(UpwardPlanRep &UPR, const List< edge > &origEdges, const EdgeArray< int > *costOrig=nullptr, const EdgeArray< bool > *forbiddenEdgeOrig=nullptr) override
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
ReturnType
The return type of a module.
Definition Module.h:50
Class for the representation of nodes.
Definition Graph_d.h:177
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Upward planarized representations (of a connected component) of a graph.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.