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. More...

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. More...

ReturnType	call (const Graph &G, int &cr, const EdgeArray< bool > *forbid=nullptr)
	Performs minor-monotone crossing minimization on `G`. More...

ReturnType	call (PlanRepExpansion &PG, int cc, int &crossingNumber, const EdgeArray< bool > *forbid=nullptr)
	Computes a planarized representation of an expansion of the input graph. More...

int	numberOfNodeSplits () const
	Returns the number of required node splits after the call. More...

int	numberOfSplittedNodes () const

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module. More...

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. More...

Private Attributes
int	m_nodeSplits
	The number of required node splits. More...

int	m_splittedNodes
	The number of nodes that are split. More...

Additional Inherited Members
Public Types inherited from ogdf::Module
enum	ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::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. More...

Detailed Description

Interface for minor-monotone crossing minimization algorithms.

Definition at line 49 of file MMCrossingMinimizationModule.h.

Constructor & Destructor Documentation

◆ MMCrossingMinimizationModule()

ogdf::MMCrossingMinimizationModule::MMCrossingMinimizationModule ( )

inline

Initializes a minor-monotone crossing minimization module.

Definition at line 52 of file MMCrossingMinimizationModule.h.

◆ ~MMCrossingMinimizationModule()

virtual ogdf::MMCrossingMinimizationModule::~MMCrossingMinimizationModule ( )

inlinevirtual

Definition at line 55 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 72 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 106 of file MMCrossingMinimizationModule.h.

◆ numberOfSplittedNodes()

int ogdf::MMCrossingMinimizationModule::numberOfSplittedNodes ( ) const

inline

Definition at line 108 of file MMCrossingMinimizationModule.h.

Member Data Documentation

◆ m_nodeSplits

int ogdf::MMCrossingMinimizationModule::m_nodeSplits

private

The number of required node splits.

Definition at line 130 of file MMCrossingMinimizationModule.h.

◆ m_splittedNodes

int ogdf::MMCrossingMinimizationModule::m_splittedNodes

private

The number of nodes that are split.

Definition at line 131 of file MMCrossingMinimizationModule.h.

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

include/ogdf/planarity/MMCrossingMinimizationModule.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MMCrossingMinimizationModule()

◆ ~MMCrossingMinimizationModule()

Member Function Documentation

◆ call() [1/3]

◆ call() [2/3]

◆ call() [3/3]

◆ doCall()

◆ numberOfNodeSplits()

◆ numberOfSplittedNodes()

Member Data Documentation

◆ m_nodeSplits

◆ m_splittedNodes

Open
Graph Drawing
Framework