Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MMCrossingMinimizationModule Class Referenceabstract

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 46 of file MMCrossingMinimizationModule.h.

Constructor & Destructor Documentation

◆ MMCrossingMinimizationModule()

ogdf::MMCrossingMinimizationModule::MMCrossingMinimizationModule ( )
inline

Initializes a minor-monotone crossing minimization module.

Definition at line 50 of file MMCrossingMinimizationModule.h.

◆ ~MMCrossingMinimizationModule()

virtual ogdf::MMCrossingMinimizationModule::~MMCrossingMinimizationModule ( )
inlinevirtual

Definition at line 53 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
Gis the input graph.
splittableNodesis the list of nodes that are allowed to be split.
cris assigned the number of crossings.
forbidpoints 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
Gis the input graph.
cris assigned the number of crossings.
forbidpoints 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
PGrepresents 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).
ccis the number of the connected component in PG that is considered.
crossingNumberis assigned the number of crossings.
forbidpoints 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 70 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
PGrepresents 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).
ccis the number of the connected component in PG that is considered.
forbidpoints to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true.
crossingNumberneeds to be assigned the number of crossings.
numNSneeds to be assigned the required number of node splits.
numSNneeds 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 109 of file MMCrossingMinimizationModule.h.

◆ numberOfSplittedNodes()

int ogdf::MMCrossingMinimizationModule::numberOfSplittedNodes ( ) const
inline

Definition at line 111 of file MMCrossingMinimizationModule.h.

Member Data Documentation

◆ m_nodeSplits

int ogdf::MMCrossingMinimizationModule::m_nodeSplits
private

The number of required node splits.

Definition at line 137 of file MMCrossingMinimizationModule.h.

◆ m_splittedNodes

int ogdf::MMCrossingMinimizationModule::m_splittedNodes
private

The number of nodes that are split.

Definition at line 138 of file MMCrossingMinimizationModule.h.


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