Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::VariableEmbeddingInserter Class Reference

Optimal edge insertion module. More...

#include <ogdf/planarity/VariableEmbeddingInserter.h>

+ Inheritance diagram for ogdf::VariableEmbeddingInserter:

Public Member Functions

Module::ReturnType callPostprocessing (PlanRepLight &pr, const Array< edge > &origEdges)
 Calls only the postprocessing; assumes that all edges in origEdges are already inserted into pr. More...
 
virtual EdgeInsertionModuleclone () const override
 Returns a new instance of the variable embedding inserter with the same option settings. More...
 
 VariableEmbeddingInserterBase ()
 Creates an instance of variable embedding edge inserter with default settings. More...
 
 VariableEmbeddingInserterBase (const VariableEmbeddingInserterBase &inserter)
 Creates an instance of variable embedding inserter with the same settings as inserter. More...
 
- Public Member Functions inherited from ogdf::VariableEmbeddingInserterBase
 VariableEmbeddingInserterBase ()
 Creates an instance of variable embedding edge inserter with default settings. More...
 
 VariableEmbeddingInserterBase (const VariableEmbeddingInserterBase &inserter)
 Creates an instance of variable embedding inserter with the same settings as inserter. More...
 
virtual ~VariableEmbeddingInserterBase ()
 Destructor. More...
 
VariableEmbeddingInserterBaseoperator= (const VariableEmbeddingInserterBase &inserter)
 Assignment operator. Copies option settings only. More...
 
void removeReinsert (RemoveReinsertType rrOption)
 Sets the remove-reinsert postprocessing method. More...
 
RemoveReinsertType removeReinsert () const
 Returns the current setting of the remove-reinsert postprocessing method. More...
 
void percentMostCrossed (double percent)
 Sets the option percentMostCrossed to percent. More...
 
double percentMostCrossed () const
 Returns the current setting of option percentMostCrossed. More...
 
int runsPostprocessing () const
 Returns the number of runs performed by the remove-reinsert method after the algorithm has been called. More...
 
- Public Member Functions inherited from ogdf::EdgeInsertionModule
 EdgeInsertionModule ()
 Initializes an edge insertion module (default constructor). More...
 
 EdgeInsertionModule (const EdgeInsertionModule &eim)
 Initializes an edge insertion module (copy constructor). More...
 
virtual ~EdgeInsertionModule ()
 Destructor. More...
 
ReturnType call (PlanRepLight &pr, const Array< edge > &origEdges)
 Inserts all edges in origEdges into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
 Inserts all edges in origEdges with given forbidden edges into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges)
 Inserts all edges in origEdges with given costs into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs)
 Inserts all edges in origEdges with given costs and subgraphs (for simultaneous drawing) into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
 Inserts all edges in origEdges with given costs and forbidden edges into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs)
 Inserts all edges in origEdges with given costs, forbidden edges, and subgraphs (for simultaneous drawing) into pr. More...
 
ReturnType callEx (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
 Inserts all edges in origEdges into pr, optionally costs, forbidden edges, and subgraphs (for simultaneous drawing) may be given. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds) More...
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 

Private Member Functions

virtual ReturnType doCall (PlanRepLight &PG, const Array< edge > &origEdges, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubgraph) override
 Implements the algorithm call. More...
 
ReturnType doCallPostprocessing (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubgraphs)
 

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...
 
- Protected Member Functions inherited from ogdf::VariableEmbeddingInserterBase
void runsPostprocessing (int runs)
 Sets the number of runs performed by the remove-reinsert method. More...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

Optimal edge insertion module.

Optimal edge insertion algorithm that inserts a single edge with a minimum number of crossings into a planar graph.

The implementation is based on the following publication:

Carsten Gutwenger, Petra Mutzel, Rene Weiskircher: Inserting an Edge into a Planar Graph. Algorithmica 41(4), pp. 289-308, 2005.

Definition at line 52 of file VariableEmbeddingInserter.h.

Member Function Documentation

◆ callPostprocessing()

Module::ReturnType ogdf::VariableEmbeddingInserter::callPostprocessing ( PlanRepLight pr,
const Array< edge > &  origEdges 
)
inline

Calls only the postprocessing; assumes that all edges in origEdges are already inserted into pr.

Parameters
pris the input planarized representation and will also receive the result.
origEdgesis the array of original edges (edges in the original graph of pr) that have to be inserted.
Returns
the status of the result.

Definition at line 66 of file VariableEmbeddingInserter.h.

◆ clone()

virtual EdgeInsertionModule* ogdf::VariableEmbeddingInserter::clone ( ) const
overridevirtual

Returns a new instance of the variable embedding inserter with the same option settings.

Implements ogdf::EdgeInsertionModule.

◆ doCall()

virtual ReturnType ogdf::VariableEmbeddingInserter::doCall ( PlanRepLight PG,
const Array< edge > &  origEdges,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< uint32_t > *  pEdgeSubgraph 
)
overrideprivatevirtual

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

◆ doCallPostprocessing()

ReturnType ogdf::VariableEmbeddingInserter::doCallPostprocessing ( PlanRepLight pr,
const Array< edge > &  origEdges,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< uint32_t > *  pEdgeSubgraphs 
)
private

◆ VariableEmbeddingInserterBase() [1/2]

ogdf::VariableEmbeddingInserterBase::VariableEmbeddingInserterBase
inline

Creates an instance of variable embedding edge inserter with default settings.

Definition at line 44 of file VariableEmbeddingInserterBase.h.

◆ VariableEmbeddingInserterBase() [2/2]

ogdf::VariableEmbeddingInserterBase::VariableEmbeddingInserterBase
inline

Creates an instance of variable embedding inserter with the same settings as inserter.

Definition at line 50 of file VariableEmbeddingInserterBase.h.


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