Edge insertion module that inserts each edge optimally into a fixed embedding. More...
#include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
Public Member Functions | |
FixedEmbeddingUpwardEdgeInserter () | |
Creates an instance of fixed-embedding edge inserter. More... | |
~FixedEmbeddingUpwardEdgeInserter () | |
Public Member Functions inherited from ogdf::UpwardEdgeInserterModule | |
UpwardEdgeInserterModule () | |
Initializes an edge insertion module. More... | |
virtual | ~UpwardEdgeInserterModule () |
ReturnType | call (UpwardPlanRep &UPR, const EdgeArray< bool > &forbidOriginal, const List< edge > &origEdges) |
Inserts all edges in origEdges with given forbidden edges into UPR . More... | |
ReturnType | call (UpwardPlanRep &UPR, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbidOriginal, const List< edge > &origEdges) |
Inserts all edges in origEdges with given forbidden edges into UPR . More... | |
ReturnType | call (UpwardPlanRep &UPR, const EdgeArray< int > &costOrig, const List< edge > &origEdges) |
Inserts all edges in origEdges with given costs into UPR . More... | |
ReturnType | call (UpwardPlanRep &UPR, const List< edge > &origEdges) |
Inserts all edges in origEdges into UPR . More... | |
Public Member Functions inherited from ogdf::Module | |
Module () | |
Initializes a module. More... | |
virtual | ~Module () |
Private Member Functions | |
void | constraintFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path) |
compute a constraint feasible insertion path usig heuristic. More... | |
virtual ReturnType | doCall (UpwardPlanRep &UPR, const List< edge > &origEdges, const EdgeArray< int > *costOrig=nullptr, const EdgeArray< bool > *forbiddenEdgeOrig=nullptr) override |
void | dynamicLock (UpwardPlanRep &UPR, EdgeArray< bool > &locked, face f, adjEntry e_cur) |
compute a list of dynamic locked edges More... | |
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 More... | |
void | getPath (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path, bool heuristic) |
compute an insertion path More... | |
ReturnType | insertAll (UpwardPlanRep &UPR, List< edge > &toInsert, EdgeArray< int > &cost) |
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 More... | |
bool | isConstraintFeasible (UpwardPlanRep &UPR, List< edge > &origEdges, edge e_orig, SList< adjEntry > &path) |
return true if current insertion path is contraint feasible More... | |
bool | isUpwardPlanar (Graph &G) const |
void | markDown (const Graph &G, node v, EdgeArray< bool > &markedEdges) |
mark the edges which dominate node v More... | |
void | markUp (const Graph &G, node v, EdgeArray< bool > &markedEdges) |
mark the edges which are dominates by node v More... | |
void | minFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path) |
compute the minimal feasible insertion path More... | |
void | nextFeasibleEdges (UpwardPlanRep &UPR, List< adjEntry > &nextEdges, face f, adjEntry e_cur, EdgeArray< bool > &locked, bool heuristic) |
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 insertion path. More... | |
Additional Inherited Members | |
Public Types inherited from ogdf::Module | |
enum | ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error } |
The return type of a module. More... | |
Static Public Member Functions inherited from ogdf::Module | |
static bool | isSolution (ReturnType ret) |
Returns true iff ret indicates that the module returned a feasible solution. More... | |
Edge insertion module that inserts each edge optimally into a fixed embedding.
Definition at line 41 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inline |
Creates an instance of fixed-embedding edge inserter.
Definition at line 44 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inline |
Definition at line 46 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inlineprivate |
compute a constraint feasible insertion path usig heuristic.
Definition at line 86 of file FixedEmbeddingUpwardEdgeInserter.h.
|
overrideprivatevirtual |
UPR | is the input upward planarized representation of a FUPS and will also receive the result. |
origEdges | is the list of original edges (edges in the original graph of UPR ) that have to be inserted. |
costOrig | points to an edge array containing the costs of original edges; edges in UPR without an original edge have zero costs. |
forbiddenEdgeOrig | points to an edge array indicating if an original edge is forbidden to be crossed. |
Implements ogdf::UpwardEdgeInserterModule.
|
private |
compute a list of dynamic locked edges
|
private |
compute the feasible edges of the face f with respect to e
|
private |
compute an insertion path
|
private |
|
private |
return true if current insertion path is contraint feasible
|
private |
return true if current insertion path is contraint feasible
|
inlineprivate |
Definition at line 50 of file FixedEmbeddingUpwardEdgeInserter.h.
|
private |
mark the edges which dominate node v
|
private |
mark the edges which are dominates by node v
|
inlineprivate |
compute the minimal feasible insertion path
Definition at line 80 of file FixedEmbeddingUpwardEdgeInserter.h.
|
private |
|
private |
compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible insertion path.