Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CrossingMinimizationModule Class Referenceabstract

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). More...
 
 CrossingMinimizationModule (const CrossingMinimizationModule &cmm)
 Initializes an crossing minimization module (copy constructor). More...
 
virtual ~CrossingMinimizationModule ()
 Destructor. More...
 
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. More...
 
virtual CrossingMinimizationModuleclone () const =0
 Returns a new instance of the crossing minimization module with the same option settings. More...
 
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. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds) More...
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 

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

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

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 45 of file CrossingMinimizationModule.h.

◆ CrossingMinimizationModule() [2/2]

ogdf::CrossingMinimizationModule::CrossingMinimizationModule ( const CrossingMinimizationModule cmm)
inline

Initializes an crossing minimization module (copy constructor).

Definition at line 48 of file CrossingMinimizationModule.h.

◆ ~CrossingMinimizationModule()

virtual ogdf::CrossingMinimizationModule::~CrossingMinimizationModule ( )
inlinevirtual

Destructor.

Definition at line 51 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
prrepresents 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).
ccis the index of the connected component in pr that is considered.
crossingNumberis assigned the number of crossings.
pCostOrigpoints 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.
pForbiddenOrigpoints 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.
pEdgeSubGraphspoints to an edge array (of the original graph) specifying to which subgraph an edge belongs.
Returns
the status of the result.

Definition at line 72 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::PlanarizerStarReinsertion, ogdf::SubgraphPlanarizer, ogdf::PlanarizerMixedInsertion, and ogdf::PlanarizerChordlessCycle.

◆ 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
graphCopyrepresents the planarization of an original graph.
pCostpoints 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.
pEdgeSubGraphspoints 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 140 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
prrepresents 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).
ccis the index of the connected component in pr that is considered.
crossingNumberis assigned the number of crossings.
pCostOrigpoints 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.
pForbiddenOrigpoints 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.
pEdgeSubGraphspoints to an edge array (of the original graph) specifying to which subgraph an edge belongs.
Returns
the status of the result.

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

◆ 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
prrepresents 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).
ccis the index of the connected component in pr that is considered.
crossingNumberis assigned the number of crossings.
pCostOrigpoints 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.
pForbiddenOrigpoints 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.
pEdgeSubGraphspoints to an edge array (of the original graph) specifying to which subgraph an edge belongs.
Returns
the status of the result.

Definition at line 97 of file CrossingMinimizationModule.h.


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