The star (re-)insertion approach for crossing minimization. More...

#include <ogdf/planarity/PlanarizerStarReinsertion.h>

Inheritance diagram for ogdf::PlanarizerStarReinsertion:

Public Member Functions
	PlanarizerStarReinsertion ()
	Creates a PlanarizerStarReinsertion with default settings.

	PlanarizerStarReinsertion (const PlanarizerStarReinsertion &planarizer)
	Creates a PlanarizerStarReinsertion with the same settings as `planarizer`.

virtual CrossingMinimizationModule *	clone () const override
	Returns a new PlanarizerStarReinsertion with the same option settings.

PlanarizerStarReinsertion &	operator= (const PlanarizerStarReinsertion &planarizer)
	Assignment operator, copies option settings only.

void	setPlanarization (CrossingMinimizationModule *pPlanarizationModule)
	Sets the module option for the computation of the inital planarization.

Optional parameters
bool	setTimeout ()
	Returns the current setting of options setTimeout.

void	setTimeout (bool b)
	Sets the option setTimeout to `b`.

int	maxIterations ()
	Returns the number of maxIterations.

void	maxIterations (int maxIterations)
	Sets the maximum number of iterations.

Public Member Functions inherited from ogdf::CrossingMinimizationModule
	CrossingMinimizationModule ()
	Initializes a crossing minimization module (default constructor).

	CrossingMinimizationModule (const CrossingMinimizationModule &cmm)
	Initializes an crossing minimization module (copy constructor).

virtual	~CrossingMinimizationModule ()
	Destructor.

ReturnType	call (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > pCostOrig=nullptr, const EdgeArray< bool > pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
	Computes a planarized representation of the input graph.

ReturnType	operator() (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > pCostOrig=nullptr, const EdgeArray< bool > pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
	Computes a planarized representation of the input graph.

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.

Protected Member Functions
virtual ReturnType	doCall (PlanRep &pr, int cc, const EdgeArray< int > pCostOrig, const EdgeArray< bool > pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs, int &crossingNumber) override
	Implements the algorithm call.

Private Member Functions
ReturnType	mainLoop (const PlanRep &pr, CrossingStructure &bestCS, const EdgeArray< int > pCostOrig, const EdgeArray< bool > pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs)
	Reinserts a specific set of stars until a termination criterion is met.

bool	reinsertStar (GraphCopy &currentPlanarization, DynamicDualGraph &dualGraph, node nodeToReinsert, CrossingStructure &bestCS, const EdgeArray< int > pCostOrig, const EdgeArray< bool > pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs)
	Reinserts the star `nodeToReinsert` in `currentPlanarization`.

Private Attributes
StarInserter	m_inserter

int	m_maxIterations
	The maximum number of iterations.

std::unique_ptr< CrossingMinimizationModule >	m_planarization
	The initial planarization algorithm.

bool	m_setTimeout
	Helper to insert stars.

int64_t	m_stopTime
	When the algorithm should stop.

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.

Static Protected Member Functions inherited from ogdf::CrossingMinimizationModule
static int	computeCrossingNumber (GraphCopy &graphCopy, const EdgeArray< int > pCost, const EdgeArray< uint32_t > pEdgeSubGraphs)
	Computes the (weighted) crossing number of the planarization `graphCopy`.

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

Detailed Description

The star (re-)insertion approach for crossing minimization.

This crossing minimization module represents a customizable implementation of the star insertion approach. This approach consists of two phases. In the first phase, a planarization of the graph is computed, i.e. a planarized representation with crossings replaced by dummy nodes of degree 4. In the second phase, a set of original nodes (each with its star insertion paths) is re-inserted with as few crossings as possible, until no improvement is possible anymore (the configuration is "locally optimal" or a maximum number of iterations is reached.

The first step, i.e. the computation of the planarization, is implemented via a module option while the maximum number of iterations can be set directly.

More details on the star insertion approach can be found in

K. Clancy, M. Haythorpe, A. Newcombe: An effective crossing minimisation heuristic based on star insertion. J. Graph Algorithms Appl. 23(2): 135-166 (2019)

Optional parameters

Option	Type	Default	Description
setTimeout	bool	true	If set to true, the time limit is also passed to submodules; otherwise, a timeout might be checked late when a submodule requires a lot of runtime.
maxIterations	int	-1	Maximum number of iterations. If negative, the algorithm stops when local optimality is reached. See maxIterations(int).

Module options

The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:

Option	Type	Default	Description
planarization	CrossingMinimizationModule	SubgraphPlanarizer using FixedEmbeddingInserter	The module for the computation of the planar subgraph.

Definition at line 107 of file PlanarizerStarReinsertion.h.

Constructor & Destructor Documentation

◆ PlanarizerStarReinsertion() [1/2]

ogdf::PlanarizerStarReinsertion::PlanarizerStarReinsertion ( )

Creates a PlanarizerStarReinsertion with default settings.

◆ PlanarizerStarReinsertion() [2/2]

ogdf::PlanarizerStarReinsertion::PlanarizerStarReinsertion ( const PlanarizerStarReinsertion & planarizer )

Creates a PlanarizerStarReinsertion with the same settings as planarizer.

Member Function Documentation

◆ clone()

virtual CrossingMinimizationModule * ogdf::PlanarizerStarReinsertion::clone ( ) const

overridevirtual

Returns a new PlanarizerStarReinsertion with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

virtual ReturnType ogdf::PlanarizerStarReinsertion::doCall	(	PlanRep &	pr,
		int	cc,
		const EdgeArray< int > *	pCostOrig,
		const EdgeArray< bool > *	pForbiddenOrig,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs,
		int &	crossingNumber
	)

overrideprotectedvirtual

Implements the algorithm call.

Precondition: pr must be biconnected, simple, and already embedded, with pseudo crossings being removed.

Implements ogdf::CrossingMinimizationModule.

◆ mainLoop()

ReturnType ogdf::PlanarizerStarReinsertion::mainLoop	(	const PlanRep &	pr,
		CrossingStructure &	bestCS,
		const EdgeArray< int > *	pCostOrig,
		const EdgeArray< bool > *	pForbiddenOrig,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs
	)

private

Reinserts a specific set of stars until a termination criterion is met.

Either the timout or the maximum number of iterations is reached, or the solution is locally optimal.

Parameters

pr	planarized representation of the graph.
bestCS	is assigned a representation of `currentPlanarization` with the least crossings found during the loop and its crossing number.
pCostOrig	points to the cost of each original edge.
pForbiddenOrig	points to an indicator for each original edge whether it is forbidden to be crossed.
pEdgeSubGraphs	points to an indicator for each original edge to which subgraph it belongs.

Returns: the return type of the algorithm.

◆ maxIterations() [1/2]

int ogdf::PlanarizerStarReinsertion::maxIterations ( )

inline

Returns the number of maxIterations.

Definition at line 197 of file PlanarizerStarReinsertion.h.

◆ maxIterations() [2/2]

void ogdf::PlanarizerStarReinsertion::maxIterations ( int maxIterations )

inline

Sets the maximum number of iterations.

The algorithm terminates when the drawing is locally crossing-optimal: It tries to re-insert all of the nodes of the graph one after another; it stops when there is no node anymore whose re-insertion would improve the number of crossings.

The algorithm can be stopped ealier by setting a maximum number of iterations (during each of which all reinsertable nodes are reinserted). A number lower than 0 indicates that the algorithm should not be stopped before a locally optimal solution is found.

Definition at line 211 of file PlanarizerStarReinsertion.h.

◆ operator=()

PlanarizerStarReinsertion & ogdf::PlanarizerStarReinsertion::operator= ( const PlanarizerStarReinsertion & planarizer )

Assignment operator, copies option settings only.

◆ reinsertStar()

bool ogdf::PlanarizerStarReinsertion::reinsertStar	(	GraphCopy &	currentPlanarization,
		DynamicDualGraph &	dualGraph,
		node	nodeToReinsert,
		CrossingStructure &	bestCS,
		const EdgeArray< int > *	pCostOrig,
		const EdgeArray< bool > *	pForbiddenOrig,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs
	)

private

Reinserts the star nodeToReinsert in currentPlanarization.

If the reinsertion leads to a lower crossing number, update bestCS.

Parameters

currentPlanarization	planarized representation of the graph.
dualGraph	dual graph of `currentPlanarization`.
nodeToReinsert	the node to be reinserted.
bestCS	is (assigned) a representation of `currentPlanarization` with the least crossings found so far as well as its crossing number.
pCostOrig	points to the cost of each original edge.
pForbiddenOrig	points to an indicator for each original edge whether it is forbidden to be crossed.
pEdgeSubGraphs	points to an indicator for each original edge to which subgraph it belongs.

Returns: whether a better solution was found, i.e. whether bestCS was updated.

◆ setPlanarization()

void ogdf::PlanarizerStarReinsertion::setPlanarization ( CrossingMinimizationModule * pPlanarizationModule )

inline

Sets the module option for the computation of the inital planarization.

Definition at line 183 of file PlanarizerStarReinsertion.h.

◆ setTimeout() [1/2]

bool ogdf::PlanarizerStarReinsertion::setTimeout ( )

inline

Returns the current setting of options setTimeout.

Definition at line 191 of file PlanarizerStarReinsertion.h.

◆ setTimeout() [2/2]

void ogdf::PlanarizerStarReinsertion::setTimeout ( bool b )

inline

Sets the option setTimeout to b.

Definition at line 194 of file PlanarizerStarReinsertion.h.

Member Data Documentation

◆ m_inserter

StarInserter ogdf::PlanarizerStarReinsertion::m_inserter

private

Definition at line 112 of file PlanarizerStarReinsertion.h.

◆ m_maxIterations

int ogdf::PlanarizerStarReinsertion::m_maxIterations

private

The maximum number of iterations.

Definition at line 116 of file PlanarizerStarReinsertion.h.

◆ m_planarization

std::unique_ptr<CrossingMinimizationModule> ogdf::PlanarizerStarReinsertion::m_planarization

private

The initial planarization algorithm.

Definition at line 110 of file PlanarizerStarReinsertion.h.

◆ m_setTimeout

bool ogdf::PlanarizerStarReinsertion::m_setTimeout

private

Helper to insert stars.

The option for setting timeouts in submodules.

Definition at line 114 of file PlanarizerStarReinsertion.h.

◆ m_stopTime

int64_t ogdf::PlanarizerStarReinsertion::m_stopTime

private

When the algorithm should stop.

Definition at line 118 of file PlanarizerStarReinsertion.h.

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

include/ogdf/planarity/PlanarizerStarReinsertion.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Optional parameters

Module options

Constructor & Destructor Documentation

◆ PlanarizerStarReinsertion() [1/2]

◆ PlanarizerStarReinsertion() [2/2]

Member Function Documentation

◆ clone()

◆ doCall()

◆ mainLoop()

◆ maxIterations() [1/2]

◆ maxIterations() [2/2]

◆ operator=()

◆ reinsertStar()

◆ setPlanarization()

◆ setTimeout() [1/2]

◆ setTimeout() [2/2]

Member Data Documentation

◆ m_inserter

◆ m_maxIterations

◆ m_planarization

◆ m_setTimeout

◆ m_stopTime

Open
Graph Drawing
Framework