Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::VariableEmbeddingInserter Class Reference

Optimal edge insertion module. More...

#include <ogdf/planarity/VariableEmbeddingInserter.h>

+ Inheritance diagram for ogdf::VariableEmbeddingInserter:

Public Member Functions

 VariableEmbeddingInserter ()
 Creates an instance of variable embedding edge inserter with default settings. More...
 
 VariableEmbeddingInserter (const VariableEmbeddingInserter &inserter)
 Creates an instance of variable embedding inserter with the same settings as inserter. More...
 
 ~VariableEmbeddingInserter ()
 Destructor. More...
 
Module::ReturnType callPostprocessing (PlanRepLight &pr, const Array< edge > &origEdges)
 Calls only the postprocessing; assumes that all edges in origEdges are already inserted into PG. More...
 
virtual EdgeInsertionModuleclone () const
 Returns a new instance of the variable embedding inserter with the same option settings. More...
 
VariableEmbeddingInserteroperator= (const VariableEmbeddingInserter &inserter)
 Assignment operator. Copies option settings only. More...
 
Optional parameters
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...
 
Further information
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< 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 > &edgeSubGraphs)
 Inserts all edges in origEdges with given costs and subgraphs (for simultaneous drawing) 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 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 > &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=0, const EdgeArray< bool > *pForbiddenOrig=0, const EdgeArray< __uint32 > *pEdgeSubGraphs=0)
 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 (double t)
 timeout is set to the given value (seconds) More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
double timeLimit () const
 returns the current time limit for the call More...
 

Private Member Functions

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

Private Attributes

double m_percentMostCrossed
 The portion of most crossed edges considered. More...
 
RemoveReinsertType m_rrOption
 The remove-reinsert method. More...
 
int m_runsPostprocessing
 Runs of remove-reinsert method. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
 The return type of a module. More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff retVal indicates that the module returned a feasible solution. 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.

The class VariableEmbeddingInserterOld represents the optimal edge insertion algorithm, which inserts a single edge with a minum 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 69 of file VariableEmbeddingInserter.h.

Constructor & Destructor Documentation

ogdf::VariableEmbeddingInserter::VariableEmbeddingInserter ( )

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

ogdf::VariableEmbeddingInserter::VariableEmbeddingInserter ( const VariableEmbeddingInserter inserter)

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

ogdf::VariableEmbeddingInserter::~VariableEmbeddingInserter ( )
inline

Destructor.

Definition at line 79 of file VariableEmbeddingInserter.h.

Member Function Documentation

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

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 94 of file VariableEmbeddingInserter.h.

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

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

Implements ogdf::EdgeInsertionModule.

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

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

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

Assignment operator. Copies option settings only.

void ogdf::VariableEmbeddingInserter::percentMostCrossed ( double  percent)
inline

Sets the option percentMostCrossed to percent.

This option determines the portion of most crossed edges used if the remove-reinsert method is set to rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.

Definition at line 120 of file VariableEmbeddingInserter.h.

double ogdf::VariableEmbeddingInserter::percentMostCrossed ( ) const
inline

Returns the current setting of option percentMostCrossed.

Definition at line 125 of file VariableEmbeddingInserter.h.

void ogdf::VariableEmbeddingInserter::removeReinsert ( RemoveReinsertType  rrOption)
inline

Sets the remove-reinsert postprocessing method.

Definition at line 105 of file VariableEmbeddingInserter.h.

RemoveReinsertType ogdf::VariableEmbeddingInserter::removeReinsert ( ) const
inline

Returns the current setting of the remove-reinsert postprocessing method.

Definition at line 110 of file VariableEmbeddingInserter.h.

int ogdf::VariableEmbeddingInserter::runsPostprocessing ( ) const
inline

Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.

Definition at line 135 of file VariableEmbeddingInserter.h.

Member Data Documentation

double ogdf::VariableEmbeddingInserter::m_percentMostCrossed
private

The portion of most crossed edges considered.

Definition at line 159 of file VariableEmbeddingInserter.h.

RemoveReinsertType ogdf::VariableEmbeddingInserter::m_rrOption
private

The remove-reinsert method.

Definition at line 158 of file VariableEmbeddingInserter.h.

int ogdf::VariableEmbeddingInserter::m_runsPostprocessing
private

Runs of remove-reinsert method.

Definition at line 161 of file VariableEmbeddingInserter.h.


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