Starts with a chordless cycle of the graph and then inserts each original node that is adjacent to already inserted ones via the StarInserter. More...

#include <ogdf/planarity/PlanarizerChordlessCycle.h>

Inheritance diagram for ogdf::PlanarizerChordlessCycle:

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

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

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

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

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
void	addToGraphCopy (GraphCopy &graphCopy, GraphCopy &copyCopy, DynamicDualGraph &dual, node vOrig, const EdgeArray< int > pCostOrig, EdgeArray< int > pCostCopy)
	Creates a copy of `vOrig` in `graphCopy` and optimally inserts a copy of this copy in the planarization `copyCopy`.

bool	findChordlessCycle (const Graph &G, List< node > &cycle)

void	transferToPlanRep (PlanRep &pr, const GraphCopy &graphCopy, const GraphCopy &copyCopy)
	Creates crossings in `pr` that resemble the crossings in `copyCopy`.

Private Attributes
StarInserter	m_inserter
	The StarInserter used to insert new nodes into the planarization.

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

Starts with a chordless cycle of the graph and then inserts each original node that is adjacent to already inserted ones via the StarInserter.

See:

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

Warning: Ignores the time limit set in the CrossingMinimizationModule. However, the heuristic should be very fast in practice anyway.

Definition at line 52 of file PlanarizerChordlessCycle.h.

Constructor & Destructor Documentation

◆ PlanarizerChordlessCycle() [1/2]

ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle ( )

Creates a PlanarizerChordlessCycle with default settings.

◆ PlanarizerChordlessCycle() [2/2]

ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle ( const PlanarizerChordlessCycle & planarizer )

Creates a PlanarizerChordlessCycle with the same settings as planarizer.

Member Function Documentation

◆ addToGraphCopy()

void ogdf::PlanarizerChordlessCycle::addToGraphCopy	(	GraphCopy &	graphCopy,
		GraphCopy &	copyCopy,
		DynamicDualGraph &	dual,
		node	vOrig,
		const EdgeArray< int > *	pCostOrig,
		EdgeArray< int > *	pCostCopy
	)

private

Creates a copy of vOrig in graphCopy and optimally inserts a copy of this copy in the planarization copyCopy.

Parameters

graphCopy	is the graph copy of the original graph.
copyCopy	is the graph copy/planarization of `graphCopy`.
dual	is the dual graph of `copyCopy`.
vOrig	is the node in the original graph for which a copy is created in `graphCopy` and `copyCopy`.
pCostOrig	are the edge costs in the original graph.
pCostCopy	are the edge costs in `graphCopy` (edge costs for the newly created edges are added).

◆ clone()

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

overridevirtual

Returns a new PlanarizerChordlessCycle with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

virtual ReturnType ogdf::PlanarizerChordlessCycle::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 simple.

Implements ogdf::CrossingMinimizationModule.

◆ findChordlessCycle()

bool ogdf::PlanarizerChordlessCycle::findChordlessCycle	(	const Graph &	G,
		List< node > &	cycle
	)

private

Parameters

G	graph in which a chordless cycle should be found.
cycle	is assigned a list of nodes in `G` which induce a chordless cycle.

◆ operator=()

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

Assignment operator, copies option settings only.

◆ transferToPlanRep()

void ogdf::PlanarizerChordlessCycle::transferToPlanRep	(	PlanRep &	pr,
		const GraphCopy &	graphCopy,
		const GraphCopy &	copyCopy
	)

private

Creates crossings in pr that resemble the crossings in copyCopy.

Warning: the order of adjEntries around each node is not copied.

Parameters

pr	is assigned the final planarization as it is contained in copyCopy in terms of crossings (but `pr` must be planarly embedded again afterwards).
graphCopy	is a copy of `pr's` original graph and the original of `copyCopy`.
copyCopy	is a planarization that contains the crossings that should be copied to `pr`.

Member Data Documentation

◆ m_inserter

StarInserter ogdf::PlanarizerChordlessCycle::m_inserter

private

The StarInserter used to insert new nodes into the planarization.

Definition at line 114 of file PlanarizerChordlessCycle.h.

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

include/ogdf/planarity/PlanarizerChordlessCycle.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ PlanarizerChordlessCycle() [1/2]

◆ PlanarizerChordlessCycle() [2/2]

Member Function Documentation

◆ addToGraphCopy()

◆ clone()

◆ doCall()

◆ findChordlessCycle()

◆ operator=()

◆ transferToPlanRep()

Member Data Documentation

◆ m_inserter

Open
Graph Drawing
Framework