|
|||
|
|
|
|||
|
|
Edge insertion module that inserts each edge optimally into a fixed embedding. More...
#include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
Inheritance diagram for ogdf::FixedEmbeddingUpwardEdgeInserter: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 48 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inline |
Creates an instance of fixed-embedding edge inserter.
Definition at line 51 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inline |
Definition at line 53 of file FixedEmbeddingUpwardEdgeInserter.h.
|
inlineprivate |
compute a constraint feasible insertion path usig heuristic.
Definition at line 93 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 57 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 87 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.
