Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FixEdgeInserterCore.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/Timeouter.h>
36 #include <ogdf/basic/Module.h>
37 #include <ogdf/basic/FaceArray.h>
38 #include <ogdf/basic/FaceSet.h>
39 #include <ogdf/basic/Queue.h>
42 
43 namespace ogdf {
44 
46 {
47 public:
49  PlanRepLight &pr,
50  const EdgeArray<int> *pCostOrig,
51  const EdgeArray<bool> *pForbiddenOrig,
52  const EdgeArray<uint32_t> *pEdgeSubgraphs)
53  : m_pr(pr), m_pCost(pCostOrig), m_pForbidden(pForbiddenOrig), m_pSubgraph(pEdgeSubgraphs) { }
54 
55  virtual ~FixEdgeInserterCore() { }
56 
57  Module::ReturnType call(
58  const Array<edge> &origEdges,
59  bool keepEmbedding,
60  RemoveReinsertType rrPost,
61  double percentMostCrossed);
62 
63  int runsPostprocessing() const { return m_runsPostprocessing; }
64 
65 protected:
66  int getCost(edge e, int stSubGraph) const;
67  void findShortestPath(const CombinatorialEmbedding &E, edge eOrig, SList<adjEntry> &crossed);
68  void findWeightedShortestPath(const CombinatorialEmbedding &E, edge eOrig, SList<adjEntry> &crossed);
69 
70  int costCrossed(edge eOrig) const;
71  void insertEdge(CombinatorialEmbedding &E, edge eOrig, const SList<adjEntry> &crossed);
72  void removeEdge(CombinatorialEmbedding &E, edge eOrig);
73 
74  virtual void storeTypeOfCurrentEdge(edge eOrig) { }
75  virtual void init(CombinatorialEmbedding &E);
76  virtual void cleanup();
77  virtual void constructDual(const CombinatorialEmbedding &E);
78 
79  virtual void appendCandidates(QueuePure<edge> &queue, node v);
80  virtual void appendCandidates(Array<SListPure<edge> > &nodesAtDist, EdgeArray<int> &costDual, int maxCost, node v, int currentDist);
81 
82  virtual void insertEdgesIntoDual(const CombinatorialEmbedding &E, adjEntry adjSrc);
83  virtual void insertEdgesIntoDualAfterRemove(const CombinatorialEmbedding &E, face f);
84 
86 
90 
92 
95 
98 
101 
103 };
104 
105 
107 {
108 public:
110  PlanRepLight &pr,
111  const EdgeArray<int> *pCostOrig,
112  const EdgeArray<uint32_t> *pEdgeSubgraph) : FixEdgeInserterCore(pr, pCostOrig, nullptr, pEdgeSubgraph) { }
113 
114 protected:
115  void storeTypeOfCurrentEdge(edge eOrig) override { m_typeOfCurrentEdge = m_pr.typeOrig(eOrig); }
116  void init(CombinatorialEmbedding &E) override;
117  void cleanup() override;
118  void constructDual(const CombinatorialEmbedding &E) override;
119 
120  void appendCandidates(QueuePure<edge> &queue, node v) override;
121  void appendCandidates(Array<SListPure<edge> > &nodesAtDist, EdgeArray<int> &costDual, int maxCost, node v, int currentDist) override;
122 
123  void insertEdgesIntoDual(const CombinatorialEmbedding &E, adjEntry adjSrc) override;
125 
128 };
129 
130 }
ogdf::FixEdgeInserterCore::m_pForbidden
const EdgeArray< bool > * m_pForbidden
Definition: FixEdgeInserterCore.h:88
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::FixEdgeInserterCore::m_nodeOf
FaceArray< node > m_nodeOf
The node in dual corresponding to face in primal.
Definition: FixEdgeInserterCore.h:94
ogdf::FixEdgeInserterCore::m_runsPostprocessing
int m_runsPostprocessing
Runs of remove-reinsert method.
Definition: FixEdgeInserterCore.h:102
FaceSet.h
Declaration and implementation of ogdf::FaceSet.
ogdf::FixEdgeInserterCore::m_delFaces
FaceSet< false > * m_delFaces
Definition: FixEdgeInserterCore.h:96
ogdf::FixEdgeInserterCore::m_vT
node m_vT
The node in extended dual representing t.
Definition: FixEdgeInserterCore.h:100
ogdf::Graph::EdgeType
EdgeType
The type of edges (only used in derived classes).
Definition: Graph_d.h:541
ogdf::FixEdgeInserterUMLCore::m_primalIsGen
EdgeArray< bool > m_primalIsGen
true iff corresponding primal edge is a generalization.
Definition: FixEdgeInserterCore.h:126
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::FixEdgeInserterUMLCore::storeTypeOfCurrentEdge
void storeTypeOfCurrentEdge(edge eOrig) override
Definition: FixEdgeInserterCore.h:115
RemoveReinsertType.h
Definition of RemoveReinsertType (used for postprocessing in edge insertion algorithms).
ogdf::FixEdgeInserterCore::m_newFaces
FaceSet< false > * m_newFaces
Definition: FixEdgeInserterCore.h:97
ogdf::FixEdgeInserterCore::~FixEdgeInserterCore
virtual ~FixEdgeInserterCore()
Definition: FixEdgeInserterCore.h:55
ogdf::PlanRepLight
Light-weight version of a planarized representation, associated with a PlanRep.
Definition: PlanRepLight.h:44
Queue.h
Declaration and implementation of list-based queues (classes QueuePure<E> and Queue<E>).
ogdf::FixEdgeInserterUMLCore::appendCandidates
void appendCandidates(QueuePure< edge > &queue, node v) override
FaceArray.h
declaration and implementation of FaceArray class
ogdf::EdgeArray< int >
ogdf::FixEdgeInserterUMLCore::FixEdgeInserterUMLCore
FixEdgeInserterUMLCore(PlanRepLight &pr, const EdgeArray< int > *pCostOrig, const EdgeArray< uint32_t > *pEdgeSubgraph)
Definition: FixEdgeInserterCore.h:109
Timeouter.h
Declares base class for modules with timeout functionality.
ogdf::FixEdgeInserterCore::runsPostprocessing
int runsPostprocessing() const
Definition: FixEdgeInserterCore.h:63
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::FixEdgeInserterCore
Definition: FixEdgeInserterCore.h:45
ogdf::FixEdgeInserterCore::m_dual
Graph m_dual
(Extended) dual graph, constructed/destructed during call.
Definition: FixEdgeInserterCore.h:91
ogdf::FixEdgeInserterCore::m_pSubgraph
const EdgeArray< uint32_t > * m_pSubgraph
Definition: FixEdgeInserterCore.h:89
ogdf::FixEdgeInserterCore::FixEdgeInserterCore
FixEdgeInserterCore(PlanRepLight &pr, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubgraphs)
Definition: FixEdgeInserterCore.h:48
ogdf::FaceArray
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition: CombinatorialEmbedding.h:174
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::FixEdgeInserterUMLCore::init
void init(CombinatorialEmbedding &E) override
ogdf::FixEdgeInserterCore::m_pr
PlanRepLight & m_pr
Definition: FixEdgeInserterCore.h:85
ogdf::FixEdgeInserterUMLCore::cleanup
void cleanup() override
ogdf::FaceSet< false >
ogdf::FixEdgeInserterUMLCore::m_typeOfCurrentEdge
Graph::EdgeType m_typeOfCurrentEdge
Definition: FixEdgeInserterCore.h:127
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::FixEdgeInserterUMLCore::constructDual
void constructDual(const CombinatorialEmbedding &E) override
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::PlanRepLight::typeOrig
EdgeType typeOrig(edge eOrig) const
Definition: PlanRepLight.h:82
PlanRepLight.h
Declaration of class PlanRepLight.
ogdf::FixEdgeInserterUMLCore::insertEdgesIntoDualAfterRemove
void insertEdgesIntoDualAfterRemove(const CombinatorialEmbedding &E, face f) override
ogdf::FixEdgeInserterCore::m_primalAdj
EdgeArray< adjEntry > m_primalAdj
Adjacency entry in primal graph corresponding to edge in dual.
Definition: FixEdgeInserterCore.h:93
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::QueuePure
Implementation of list-based queues.
Definition: Queue.h:50
ogdf::FixEdgeInserterCore::storeTypeOfCurrentEdge
virtual void storeTypeOfCurrentEdge(edge eOrig)
Definition: FixEdgeInserterCore.h:74
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::RemoveReinsertType
RemoveReinsertType
The postprocessing method for edge insertion algorithms.
Definition: RemoveReinsertType.h:41
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::Timeouter
class for timeout funtionality.
Definition: Timeouter.h:47
Module.h
Declares base class for all module types.
ogdf::Module::ReturnType
ReturnType
The return type of a module.
Definition: Module.h:51
ogdf::FixEdgeInserterCore::m_vS
node m_vS
The node in extended dual representing s.
Definition: FixEdgeInserterCore.h:99
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::FixEdgeInserterCore::m_pCost
const EdgeArray< int > * m_pCost
Definition: FixEdgeInserterCore.h:87
ogdf::FixEdgeInserterUMLCore::insertEdgesIntoDual
void insertEdgesIntoDual(const CombinatorialEmbedding &E, adjEntry adjSrc) override
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111
ogdf::FixEdgeInserterUMLCore
Definition: FixEdgeInserterCore.h:106