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

Inheritance diagram for ogdf::MMCrossingMinimizationModule:

Public Member Functions
	MMCrossingMinimizationModule ()
	Initializes a minor-monotone crossing minimization module.
virtual	~MMCrossingMinimizationModule ()
ReturnType	call (PlanRepExpansion &PG, int cc, int &crossingNumber, const EdgeArray< bool > *forbid=0)
	Computes a planarized representation of an expansion of the input graph.
ReturnType	call (const Graph &G, int &cr, const EdgeArray< bool > *forbid=0)
	Performs minor-monotone crossing minimization on G.
ReturnType	call (const Graph &G, const List< node > &splittableNodes, int &cr, const EdgeArray< bool > *forbid=0)
	Performs minor-monotone crossing minimization on G for given splittable nodes.
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	ReturnType { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
	The return type of a module. More...
Static Public Member Functions inherited from ogdf::Module
static bool	isSolution (ReturnType ret)
	Returns true iff retVal indicates that the module returned a feasible solution.

Detailed Description

Interface for minor-monotone crossing minimization algorithms.

Constructor & Destructor Documentation

ogdf::MMCrossingMinimizationModule::MMCrossingMinimizationModule ( )

inline

Initializes a minor-monotone crossing minimization module.

virtual ogdf::MMCrossingMinimizationModule::~MMCrossingMinimizationModule ( )

inlinevirtual

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

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.

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

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.

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

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.

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.