Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MMSubgraphPlanarizer Class Reference

Planarization approach for minor-monotone crossing minimization. More...

#include <ogdf/planarity/MMSubgraphPlanarizer.h>

+ Inheritance diagram for ogdf::MMSubgraphPlanarizer:

Public Member Functions

 MMSubgraphPlanarizer ()
 Creates a subgraph planarizer for minor-monotone crossing minimization. More...
 
int permutations ()
 Returns the number of performed permutations in the edge insertion step. More...
 
void permutations (int p)
 Sets the number of performed permutations in the edge insertion step. More...
 
void setInserter (MMEdgeInsertionModule *pInserter)
 Sets the module option for minor-monotone edge insertion. More...
 
void setSubgraph (PlanarSubgraphModule< int > *pSubgraph)
 Sets the module option for the computation of the planar subgraph. More...
 
- Public Member Functions inherited from ogdf::MMCrossingMinimizationModule
 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) override
 Actual algorithm call that needs to be implemented by derived classed. More...
 

Private Attributes

std::unique_ptr< MMEdgeInsertionModulem_inserter
 The minor-monotone edge insertion module. More...
 
int m_permutations
 The number of permutations. More...
 
std::unique_ptr< PlanarSubgraphModule< int > > m_subgraph
 The planar subgraph module. 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

Planarization approach for minor-monotone crossing minimization.

Definition at line 47 of file MMSubgraphPlanarizer.h.

Constructor & Destructor Documentation

◆ MMSubgraphPlanarizer()

ogdf::MMSubgraphPlanarizer::MMSubgraphPlanarizer ( )

Creates a subgraph planarizer for minor-monotone crossing minimization.

Member Function Documentation

◆ doCall()

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

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.

Implements ogdf::MMCrossingMinimizationModule.

◆ permutations() [1/2]

int ogdf::MMSubgraphPlanarizer::permutations ( )
inline

Returns the number of performed permutations in the edge insertion step.

Definition at line 59 of file MMSubgraphPlanarizer.h.

◆ permutations() [2/2]

void ogdf::MMSubgraphPlanarizer::permutations ( int  p)
inline

Sets the number of performed permutations in the edge insertion step.

Definition at line 62 of file MMSubgraphPlanarizer.h.

◆ setInserter()

void ogdf::MMSubgraphPlanarizer::setInserter ( MMEdgeInsertionModule pInserter)
inline

Sets the module option for minor-monotone edge insertion.

Definition at line 56 of file MMSubgraphPlanarizer.h.

◆ setSubgraph()

void ogdf::MMSubgraphPlanarizer::setSubgraph ( PlanarSubgraphModule< int > *  pSubgraph)
inline

Sets the module option for the computation of the planar subgraph.

Definition at line 53 of file MMSubgraphPlanarizer.h.

Member Data Documentation

◆ m_inserter

std::unique_ptr<MMEdgeInsertionModule> ogdf::MMSubgraphPlanarizer::m_inserter
private

The minor-monotone edge insertion module.

Definition at line 70 of file MMSubgraphPlanarizer.h.

◆ m_permutations

int ogdf::MMSubgraphPlanarizer::m_permutations
private

The number of permutations.

Definition at line 72 of file MMSubgraphPlanarizer.h.

◆ m_subgraph

std::unique_ptr<PlanarSubgraphModule<int> > ogdf::MMSubgraphPlanarizer::m_subgraph
private

The planar subgraph module.

Definition at line 69 of file MMSubgraphPlanarizer.h.


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