Computes a planar subgraph of the graph and then re-inserts each original node that is incident to at least one edge not in the subgraph via the StarInserter. More...

#include <ogdf/planarity/PlanarizerMixedInsertion.h>

Inheritance diagram for ogdf::PlanarizerMixedInsertion:

Public Types
enum class	NodeSelectionMethod { Random , HigherDegree , LowerDegree , HigherNonPlanarDegree , LowerNonPlanarDegree , BothEndpoints }
	Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex. More...

Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
	The return type of a module. More...

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

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

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

NodeSelectionMethod	nodeSelectionMethod ()
	Returns the used method of selecting nodes to reinsert.

void	nodeSelectionMethod (NodeSelectionMethod method)
	Sets the used method of selecting nodes to reinsert.

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

void	setSubgraph (PlanarSubgraphModule< int > *pSubgraph)
	Sets the module option for the computation of the planar subgraph.

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 Attributes
NodeSelectionMethod	m_nodeSelectionMethod

std::unique_ptr< PlanarSubgraphModule< int > >	m_subgraph
	< The planar subgraph algorithm.

Additional Inherited Members
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

Computes a planar subgraph of the graph and then re-inserts each original node that is incident to at least one edge not in the subgraph via the StarInserter.

Whether all nodes incident to these edges are re-inserted or just some of them, can be configured. If an edge is not in the planar subgraph but both of its endpoints are cut vertices in the planar subgraph, the edge is reinserted via an EdgeInsertionModule. See:

M. Chimani, M. Ilsen, T. Wiedera: Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. In: Purchase H.C., Rutter I. (eds) GD 2021. LNCS, vol. 12868, pp. 41–56. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92931-2_3

Options

Option	Type	Default	Description
subgraph	PlanarSubgraphModule	PlanarSubgraphFast<int>	The module for the computation of the planar subgraph.
nodeSelectionMethod	NodeSelectionMethod	HigherDegree	Determines which nodes are reinserted.

Definition at line 69 of file PlanarizerMixedInsertion.h.

Member Enumeration Documentation

◆ NodeSelectionMethod

enum class ogdf::PlanarizerMixedInsertion::NodeSelectionMethod

strong

Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex.

Enumerator
Random	Either the source or the target of e, decided randomly.
HigherDegree	The endpoint of e with the higher degree.
LowerDegree	The endpoint of e with the lower degree.
HigherNonPlanarDegree	The endpoint of e with the higher number of incident edges not in the planar subgraph.
LowerNonPlanarDegree	The endpoint of e with the lower number of incident edges not in the planar subgraph.
BothEndpoints	Both the source and the target of e.

Definition at line 84 of file PlanarizerMixedInsertion.h.

Constructor & Destructor Documentation

◆ PlanarizerMixedInsertion() [1/2]

ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion ( )

Creates a PlanarizerMixedInsertion with default settings.

◆ PlanarizerMixedInsertion() [2/2]

ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion ( const PlanarizerMixedInsertion & planarizer )

Creates a PlanarizerMixedInsertion with the same settings as planarizer.

Member Function Documentation

◆ clone()

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

overridevirtual

Returns a new PlanarizerMixedInsertion with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

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

◆ nodeSelectionMethod() [1/2]

NodeSelectionMethod ogdf::PlanarizerMixedInsertion::nodeSelectionMethod ( )

inline

Returns the used method of selecting nodes to reinsert.

Definition at line 111 of file PlanarizerMixedInsertion.h.

◆ nodeSelectionMethod() [2/2]

void ogdf::PlanarizerMixedInsertion::nodeSelectionMethod ( NodeSelectionMethod method )

inline

Sets the used method of selecting nodes to reinsert.

Definition at line 114 of file PlanarizerMixedInsertion.h.

◆ operator=()

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

Assignment operator, copies option settings only.

◆ setSubgraph()

void ogdf::PlanarizerMixedInsertion::setSubgraph ( PlanarSubgraphModule< int > * pSubgraph )

inline

Sets the module option for the computation of the planar subgraph.

Definition at line 108 of file PlanarizerMixedInsertion.h.

Member Data Documentation

◆ m_nodeSelectionMethod

NodeSelectionMethod ogdf::PlanarizerMixedInsertion::m_nodeSelectionMethod

private

Definition at line 121 of file PlanarizerMixedInsertion.h.

◆ m_subgraph

std::unique_ptr<PlanarSubgraphModule<int> > ogdf::PlanarizerMixedInsertion::m_subgraph

private

< The planar subgraph algorithm.

How to select the nodes which are reinserted.

Definition at line 118 of file PlanarizerMixedInsertion.h.

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

include/ogdf/planarity/PlanarizerMixedInsertion.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Options

Member Enumeration Documentation

◆ NodeSelectionMethod

Constructor & Destructor Documentation

◆ PlanarizerMixedInsertion() [1/2]

◆ PlanarizerMixedInsertion() [2/2]

Member Function Documentation

◆ clone()

◆ doCall()

◆ nodeSelectionMethod() [1/2]

◆ nodeSelectionMethod() [2/2]

◆ operator=()

◆ setSubgraph()

Member Data Documentation

◆ m_nodeSelectionMethod

◆ m_subgraph

Open
Graph Drawing
Framework