Optimal edge insertion module. More...

#include <ogdf/planarity/VariableEmbeddingInserterDyn.h>

Inheritance diagram for ogdf::VariableEmbeddingInserterDyn:

Public Member Functions
virtual EdgeInsertionModule *	clone () const override
	Returns a new instance of the variable embedding inserter with the same option settings.

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

	VariableEmbeddingInserterBase (const VariableEmbeddingInserterBase &inserter)
	Creates an instance of variable embedding inserter with the same settings as `inserter`.

Public Member Functions inherited from ogdf::VariableEmbeddingInserterBase
	VariableEmbeddingInserterBase ()
	Creates an instance of variable embedding edge inserter with default settings.

	VariableEmbeddingInserterBase (const VariableEmbeddingInserterBase &inserter)
	Creates an instance of variable embedding inserter with the same settings as `inserter`.

virtual	~VariableEmbeddingInserterBase ()
	Destructor.

VariableEmbeddingInserterBase &	operator= (const VariableEmbeddingInserterBase &inserter)
	Assignment operator. Copies option settings only.

void	removeReinsert (RemoveReinsertType rrOption)
	Sets the remove-reinsert postprocessing method.

RemoveReinsertType	removeReinsert () const
	Returns the current setting of the remove-reinsert postprocessing method.

void	percentMostCrossed (double percent)
	Sets the option percentMostCrossed to `percent`.

double	percentMostCrossed () const
	Returns the current setting of option percentMostCrossed.

int	runsPostprocessing () const
	Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.

Public Member Functions inherited from ogdf::EdgeInsertionModule
	EdgeInsertionModule ()
	Initializes an edge insertion module (default constructor).

	EdgeInsertionModule (const EdgeInsertionModule &eim)
	Initializes an edge insertion module (copy constructor).

virtual	~EdgeInsertionModule ()
	Destructor.

ReturnType	call (PlanRepLight &pr, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` with given forbidden edges into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` with given costs into `pr`.

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

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

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

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.

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

virtual	~Module ()

Public Member Functions inherited from ogdf::Timeouter
	Timeouter ()
	timeout is turned of by default

	Timeouter (bool t)
	timeout is turned off (false) or on (true) (with 0 second)

	Timeouter (const Timeouter &t)

	Timeouter (double t)
	timeout is set to the given value (seconds)

	~Timeouter ()

bool	isTimeLimit () const
	returns whether any time limit is set or not

Timeouter &	operator= (const Timeouter &t)

double	timeLimit () const
	returns the current time limit for the call

void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)

void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.

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

Additional Inherited Members
Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , 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.

Protected Member Functions inherited from ogdf::VariableEmbeddingInserterBase
void	runsPostprocessing (int runs)
	Sets the number of runs performed by the remove-reinsert method.

Protected Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

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.

In contrast to ogdf::VariableEmbeddingInserter, a ogdf::DynamicSPQRForest is used.

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 54 of file VariableEmbeddingInserterDyn.h.

Member Function Documentation

◆ clone()

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

overridevirtual

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

Implements ogdf::EdgeInsertionModule.

◆ doCall()

virtual ReturnType ogdf::VariableEmbeddingInserterDyn::doCall	(	PlanRepLight &	pr,
		const Array< edge > &	origEdges,
		const EdgeArray< int > *	pCostOrig,
		const EdgeArray< bool > *	pForbiddenOrig,
		const EdgeArray< uint32_t > *	pEdgeSubgraphs
	)