ogdf::MMCrossingMinimizationModule Class Reference

Interface for minor-monotone crossing minimization algorithms. More...

#include <ogdf/planarity/MMCrossingMinimizationModule.h>

Inheritance diagram for ogdf::MMCrossingMinimizationModule:

Public Member Functions
	MMCrossingMinimizationModule ()
	Initializes a minor-monotone crossing minimization module.
virtual	~MMCrossingMinimizationModule ()
ReturnType	call (const Graph &G, const List< node > &splittableNodes, int &cr, const EdgeArray< bool > *forbid=nullptr)
	Performs minor-monotone crossing minimization on G for given splittable nodes.
ReturnType	call (const Graph &G, int &cr, const EdgeArray< bool > *forbid=nullptr)
	Performs minor-monotone crossing minimization on G.
ReturnType	call (PlanRepExpansion &PG, int cc, int &crossingNumber, const EdgeArray< bool > *forbid=nullptr)
	Computes a planarized representation of an expansion of the input graph.
int	numberOfNodeSplits () const
	Returns the number of required node splits after the call.
int	numberOfSplittedNodes () const
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.
virtual	~Module ()

Protected Member Functions
virtual ReturnType	doCall (PlanRepExpansion &PG, int cc, const EdgeArray< bool > *forbid, int &crossingNumber, int &numNS, int &numSN)=0
	Actual algorithm call that needs to be implemented by derived classed.

Private Attributes
int	m_nodeSplits
	The number of required node splits.
int	m_splittedNodes
	The number of nodes that are split.

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.

Detailed Description

Interface for minor-monotone crossing minimization algorithms.

Definition at line 45 of file MMCrossingMinimizationModule.h.

Constructor & Destructor Documentation

MMCrossingMinimizationModule()

ogdf::MMCrossingMinimizationModule::MMCrossingMinimizationModule ( )

inline

Initializes a minor-monotone crossing minimization module.

Definition at line 48 of file MMCrossingMinimizationModule.h.

~MMCrossingMinimizationModule()

virtual ogdf::MMCrossingMinimizationModule::~MMCrossingMinimizationModule ( )

inlinevirtual

Definition at line 51 of file MMCrossingMinimizationModule.h.

Member Function Documentation

call() [1/3]

ReturnType ogdf::MMCrossingMinimizationModule::call	(	const Graph &	G,
		const List< node > &	splittableNodes,
		int &	cr,
		const EdgeArray< bool > *	forbid = nullptr
	)

Performs minor-monotone crossing minimization on G for given splittable nodes.

Parameters

G	is the input graph.
splittableNodes	is the list of nodes that are allowed to be split.
cr	is assigned the number of crossings.
forbid	points to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are forbidden.

Returns

the status of the result.

call() [2/3]

ReturnType ogdf::MMCrossingMinimizationModule::call	(	const Graph &	G,
		int &	cr,
		const EdgeArray< bool > *	forbid = nullptr
	)

Performs minor-monotone crossing minimization on G.

Parameters

G	is the input graph.
cr	is assigned the number of crossings.
forbid	points to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are forbidden.

Returns

the status of the result.

call() [3/3]

ReturnType ogdf::MMCrossingMinimizationModule::call ( PlanRepExpansion &  PG, int  cc, int &  crossingNumber, const EdgeArray< bool > *  forbid = nullptr  )

inline

Computes a planarized representation of an expansion of the input graph.

Parameters

PG	represents the input graph as well as the computed planarized expansion after the call. PG has to be initialzed as a PlanRepExpansion of the input graph and is modified to obatain the planarized representation (nodes are eventually expanded by splitting the node and crossings are replaced by dummy vertices with degree four).
cc	is the number of the connected component in PG that is considered.
crossingNumber	is assigned the number of crossings.
forbid	points to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are forbidden.

Returns

the status of the result.

Definition at line 68 of file MMCrossingMinimizationModule.h.

doCall()

virtual ReturnType ogdf::MMCrossingMinimizationModule::doCall ( PlanRepExpansion &  PG, int  cc, const EdgeArray< bool > *  forbid, int &  crossingNumber, int &  numNS, int &  numSN  )

protectedpure virtual

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

Parameters

PG	represents the input graph as well as the computed planarized expansion after the call. PG is initialized as a PlanRepExpansion of the input graph and needs to be modified to obatain the planarized representation (crossings are replaced by dummy vertices with degree four).
cc	is the number of the connected component in PG that is considered.
forbid	points to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true.
crossingNumber	needs to be assigned the number of crossings.
numNS	needs to be assigned the required number of node splits.
numSN	needs to be assigned the number of splitted nodes.

Returns

the status of the result.

Implemented in ogdf::MMSubgraphPlanarizer.

numberOfNodeSplits()

int ogdf::MMCrossingMinimizationModule::numberOfNodeSplits ( ) const

inline

Returns the number of required node splits after the call.

Definition at line 102 of file MMCrossingMinimizationModule.h.

numberOfSplittedNodes()

int ogdf::MMCrossingMinimizationModule::numberOfSplittedNodes ( ) const

inline

Definition at line 104 of file MMCrossingMinimizationModule.h.

Member Data Documentation

m_nodeSplits

int ogdf::MMCrossingMinimizationModule::m_nodeSplits

private

The number of required node splits.

Definition at line 126 of file MMCrossingMinimizationModule.h.

m_splittedNodes

int ogdf::MMCrossingMinimizationModule::m_splittedNodes

private

The number of nodes that are split.

Definition at line 127 of file MMCrossingMinimizationModule.h.

---

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

• include/ogdf/planarity/MMCrossingMinimizationModule.h