Base class for crossing minimization algorithms. More...

#include <ogdf/planarity/CrossingMinimizationModule.h>

Inheritance diagram for ogdf::CrossingMinimizationModule:

Public Member Functions
	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.

virtual CrossingMinimizationModule *	clone () const =0
	Returns a new instance of the crossing minimization module with the same option settings.

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)=0
	Actual algorithm call that needs to be implemented by derived classes.

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

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 Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

Detailed Description

Base class for crossing minimization algorithms.

Definition at line 41 of file CrossingMinimizationModule.h.

Constructor & Destructor Documentation

◆ CrossingMinimizationModule() [1/2]

ogdf::CrossingMinimizationModule::CrossingMinimizationModule ( )

inline

Initializes a crossing minimization module (default constructor).

Definition at line 44 of file CrossingMinimizationModule.h.

◆ CrossingMinimizationModule() [2/2]

ogdf::CrossingMinimizationModule::CrossingMinimizationModule ( const CrossingMinimizationModule & cmm )

inline

Initializes an crossing minimization module (copy constructor).

Definition at line 47 of file CrossingMinimizationModule.h.

◆ ~CrossingMinimizationModule()

virtual ogdf::CrossingMinimizationModule::~CrossingMinimizationModule ( )

inlinevirtual

Destructor.

Definition at line 50 of file CrossingMinimizationModule.h.

Member Function Documentation

◆ call()

ReturnType ogdf::CrossingMinimizationModule::call	(	PlanRep &	pr,
		int	cc,
		int &	crossingNumber,
		const EdgeArray< int > *	pCostOrig = `nullptr`,
		const EdgeArray< bool > *	pForbiddenOrig = `nullptr`,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs = `nullptr`
	)

inline

Computes a planarized representation of the input graph.

Parameters

pr	represents the input graph as well as the computed planarized representation after the call. `pr` has to be initialzed as a PlanRep of the input graph and is modified to obatain the planarized representation (crossings are replaced by dummy vertices with degree four).
cc	is the index of the connected component in `pr` that is considered.
crossingNumber	is assigned the number of crossings.
pCostOrig	points to an edge array (of the original graph) that gives the cost of each edge. May be a 0-pointer, in which case all edges have cost 1.
pForbiddenOrig	points to an edge array (of the original graph) specifying which edges are not allowed to be crossed. May be a 0-pointer, in which case no edges are forbidden.
pEdgeSubGraphs	points to an edge array (of the original graph) specifying to which subgraph an edge belongs.

Returns: the status of the result.

Definition at line 70 of file CrossingMinimizationModule.h.

◆ clone()

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

pure virtual

Returns a new instance of the crossing minimization module with the same option settings.

Implemented in ogdf::PlanarizerChordlessCycle, ogdf::PlanarizerMixedInsertion, ogdf::PlanarizerStarReinsertion, and ogdf::SubgraphPlanarizer.

◆ computeCrossingNumber()

static int ogdf::CrossingMinimizationModule::computeCrossingNumber	(	GraphCopy &	graphCopy,
		const EdgeArray< int > *	pCost,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs
	)

inlinestaticprotected

Computes the (weighted) crossing number of the planarization graphCopy.

Parameters

graphCopy	represents the planarization of an original graph.
pCost	points to an edge array (of the original graph) with the cost of each edge. May be nullptr, in which case all edges have cost 1.
pEdgeSubGraphs	points to an edge array (of the original graph) specifying to which subgraph an edge belongs.

Returns: the (weighted) crossing number of graphCopy.

Definition at line 129 of file CrossingMinimizationModule.h.

◆ doCall()

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

protectedpure virtual

Actual algorithm call that needs to be implemented by derived classes.

Parameters

pr	represents the input graph as well as the computed planarized representation after the call. `pr` has to be initialzed as a PlanRep of the input graph and is modified to obatain the planarized representation (crossings are replaced by dummy vertices with degree four).
cc	is the index of the connected component in `pr` that is considered.
crossingNumber	is assigned the number of crossings.
pCostOrig	points to an edge array (of the original graph) that gives the cost of each edge. May be a 0-pointer, in which case all edges have cost 1.
pForbiddenOrig	points to an edge array (of the original graph) specifying which edges are not allowed to be crossed. May be a 0-pointer, in which case no edges are forbidden.
pEdgeSubGraphs	points to an edge array (of the original graph) specifying to which subgraph an edge belongs.

Returns: the status of the result.

Implemented in ogdf::PlanarizerChordlessCycle, ogdf::PlanarizerMixedInsertion, ogdf::PlanarizerStarReinsertion, and ogdf::SubgraphPlanarizer.

◆ operator()()

ReturnType ogdf::CrossingMinimizationModule::operator()	(	PlanRep &	pr,
		int	cc,
		int &	crossingNumber,
		const EdgeArray< int > *	pCostOrig = `nullptr`,
		const EdgeArray< bool > *	pForbiddenOrig = `nullptr`,
		const EdgeArray< uint32_t > *	pEdgeSubGraphs = `nullptr`
	)

inline

Computes a planarized representation of the input graph.

Parameters

pr	represents the input graph as well as the computed planarized representation after the call. `pr` has to be initialzed as a PlanRep of the input graph and is modified to obatain the planarized representation (crossings are replaced by dummy vertices with degree four).
cc	is the index of the connected component in `pr` that is considered.
crossingNumber	is assigned the number of crossings.
pCostOrig	points to an edge array (of the original graph) that gives the cost of each edge. May be a 0-pointer, in which case all edges have cost 1.
pForbiddenOrig	points to an edge array (of the original graph) specifying which edges are not allowed to be crossed. May be a 0-pointer, in which case no edges are forbidden.
pEdgeSubGraphs	points to an edge array (of the original graph) specifying to which subgraph an edge belongs.

Returns: the status of the result.

Definition at line 92 of file CrossingMinimizationModule.h.

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

include/ogdf/planarity/CrossingMinimizationModule.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CrossingMinimizationModule() [1/2]

◆ CrossingMinimizationModule() [2/2]

◆ ~CrossingMinimizationModule()

Member Function Documentation

◆ call()

◆ clone()

◆ computeCrossingNumber()

◆ doCall()

◆ operator()()

Open
Graph Drawing
Framework