Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::FixedEmbeddingUpwardEdgeInserter Class Reference

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...
 

Detailed Description

Edge insertion module that inserts each edge optimally into a fixed embedding.

Definition at line 41 of file FixedEmbeddingUpwardEdgeInserter.h.

Constructor & Destructor Documentation

◆ FixedEmbeddingUpwardEdgeInserter()

ogdf::FixedEmbeddingUpwardEdgeInserter::FixedEmbeddingUpwardEdgeInserter ( )
inline

Creates an instance of fixed-embedding edge inserter.

Definition at line 45 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ ~FixedEmbeddingUpwardEdgeInserter()

ogdf::FixedEmbeddingUpwardEdgeInserter::~FixedEmbeddingUpwardEdgeInserter ( )
inline

Definition at line 47 of file FixedEmbeddingUpwardEdgeInserter.h.

Member Function Documentation

◆ constraintFIP()

void ogdf::FixedEmbeddingUpwardEdgeInserter::constraintFIP ( UpwardPlanRep UPR,
List< edge > &  origEdges,
EdgeArray< int > &  cost,
edge  e_orig,
SList< adjEntry > &  path 
)
inlineprivate

compute a constraint feasible insertion path usig heuristic.

Definition at line 96 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ doCall()

virtual ReturnType ogdf::FixedEmbeddingUpwardEdgeInserter::doCall ( UpwardPlanRep UPR,
const List< edge > &  origEdges,
const EdgeArray< int > *  costOrig = nullptr,
const EdgeArray< bool > *  forbiddenEdgeOrig = nullptr 
)
overrideprivatevirtual
Parameters
UPRis the input upward planarized representation of a FUPS and will also receive the result.
origEdgesis the list of original edges (edges in the original graph of UPR) that have to be inserted.
costOrigpoints to an edge array containing the costs of original edges; edges in UPR without an original edge have zero costs.
forbiddenEdgeOrigpoints to an edge array indicating if an original edge is forbidden to be crossed.

Implements ogdf::UpwardEdgeInserterModule.

◆ dynamicLock()

void ogdf::FixedEmbeddingUpwardEdgeInserter::dynamicLock ( UpwardPlanRep UPR,
EdgeArray< bool > &  locked,
face  f,
adjEntry  e_cur 
)
private

compute a list of dynamic locked edges

◆ feasibleEdges()

void ogdf::FixedEmbeddingUpwardEdgeInserter::feasibleEdges ( UpwardPlanRep UPR,
face  f,
adjEntry  adj,
EdgeArray< bool > &  locked,
List< adjEntry > &  feasible,
bool  heuristic 
)
private

compute the feasible edges of the face f with respect to e

◆ getPath()

void ogdf::FixedEmbeddingUpwardEdgeInserter::getPath ( UpwardPlanRep UPR,
List< edge > &  origEdges,
EdgeArray< int > &  cost,
edge  e_orig,
SList< adjEntry > &  path,
bool  heuristic 
)
private

compute an insertion path

◆ insertAll()

ReturnType ogdf::FixedEmbeddingUpwardEdgeInserter::insertAll ( UpwardPlanRep UPR,
List< edge > &  toInsert,
EdgeArray< int > &  cost 
)
private

◆ isConstraintFeasible() [1/2]

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible ( UpwardPlanRep UPR,
const List< edge > &  orig_edges,
edge  e_orig,
adjEntry  adjCurrent,
adjEntry  adjNext,
EdgeArray< adjEntry > &  predAdj 
)
private

return true if current insertion path is contraint feasible

◆ isConstraintFeasible() [2/2]

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible ( UpwardPlanRep UPR,
List< edge > &  origEdges,
edge  e_orig,
SList< adjEntry > &  path 
)
private

return true if current insertion path is contraint feasible

◆ isUpwardPlanar()

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isUpwardPlanar ( Graph G) const
inlineprivate

Definition at line 52 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ markDown()

void ogdf::FixedEmbeddingUpwardEdgeInserter::markDown ( const Graph G,
node  v,
EdgeArray< bool > &  markedEdges 
)
private

mark the edges which dominate node v

◆ markUp()

void ogdf::FixedEmbeddingUpwardEdgeInserter::markUp ( const Graph G,
node  v,
EdgeArray< bool > &  markedEdges 
)
private

mark the edges which are dominates by node v

◆ minFIP()

void ogdf::FixedEmbeddingUpwardEdgeInserter::minFIP ( UpwardPlanRep UPR,
List< edge > &  origEdges,
EdgeArray< int > &  cost,
edge  e_orig,
SList< adjEntry > &  path 
)
inlineprivate

compute the minimal feasible insertion path

Definition at line 87 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ nextFeasibleEdges()

void ogdf::FixedEmbeddingUpwardEdgeInserter::nextFeasibleEdges ( UpwardPlanRep UPR,
List< adjEntry > &  nextEdges,
face  f,
adjEntry  e_cur,
EdgeArray< bool > &  locked,
bool  heuristic 
)
private

◆ staticLock()

void ogdf::FixedEmbeddingUpwardEdgeInserter::staticLock ( UpwardPlanRep UPR,
EdgeArray< bool > &  locked,
const List< edge > &  origEdges,
edge  e_orig 
)
private

compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible insertion path.


The documentation for this class was generated from the following file: