Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarizerMixedInsertion Class Reference

#include <ogdf/planarity/PlanarizerMixedInsertion.h>

+ Inheritance diagram for ogdf::PlanarizerMixedInsertion:

Public Types

enum  NodeSelectionMethod { NodeSelectionMethod::Random, NodeSelectionMethod::HigherDegree, NodeSelectionMethod::LowerDegree, NodeSelectionMethod::HigherNonPlanarDegree, NodeSelectionMethod::LowerNonPlanarDegree, NodeSelectionMethod::BothEndpoints }
 Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex. More...
 
- 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...
 

Public Member Functions

 PlanarizerMixedInsertion ()
 Creates a PlanarizerMixedInsertion with default settings. More...
 
 PlanarizerMixedInsertion (const PlanarizerMixedInsertion &planarizer)
 Creates a PlanarizerMixedInsertion with the same settings as planarizer. More...
 
virtual CrossingMinimizationModuleclone () const override
 Returns a new PlanarizerMixedInsertion with the same option settings. More...
 
NodeSelectionMethod nodeSelectionMethod ()
 Returns the used method of selecting nodes to reinsert. More...
 
void nodeSelectionMethod (NodeSelectionMethod method)
 Sets the used method of selecting nodes to reinsert. More...
 
PlanarizerMixedInsertionoperator= (const PlanarizerMixedInsertion &planarizer)
 Assignment operator, copies option settings only. More...
 
void setSubgraph (PlanarSubgraphModule< int > *pSubgraph)
 Sets the module option for the computation of the planar subgraph. More...
 
- Public Member Functions inherited from ogdf::CrossingMinimizationModule
 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...
 
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) override
 Implements the algorithm call. More...
 

Private Attributes

NodeSelectionMethod m_nodeSelectionMethod
 
std::unique_ptr< PlanarSubgraphModule< int > > m_subgraph
 < The planar subgraph algorithm. More...
 

Additional Inherited Members

- 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...
 
- Static Protected Member Functions inherited from ogdf::CrossingMinimizationModule
static int computeCrossingNumber (GraphCopy &graphCopy, const EdgeArray< int > *pCost, const EdgeArray< uint32_t > *pEdgeSubGraphs)
 Computes the (weighted) crossing number of the planarization graphCopy. More...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

Computes a planar subgraph of the graph and then re-inserts each original node that is incident to at least one edge not in the subgraph via the StarInserter. Whether all nodes incident to these edges are re-inserted or just some of them, can be configured. If an edge is not in the planar subgraph but both of its endpoints are cut vertices in the planar subgraph, the edge is reinserted via an EdgeInsertionModule. See:

M. Chimani, M. Ilsen, T. Wiedera: Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. In: Purchase H.C., Rutter I. (eds) GD 2021. LNCS, vol. 12868, pp. 41–56. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92931-2_3

Options

OptionTypeDefaultDescription
subgraphPlanarSubgraphModulePlanarSubgraphFast<int> The module for the computation of the planar subgraph.
nodeSelectionMethodNodeSelectionMethodHigherDegree Determines which nodes are reinserted.

Definition at line 70 of file PlanarizerMixedInsertion.h.

Member Enumeration Documentation

◆ NodeSelectionMethod

Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex.

Enumerator
Random 

Either the source or the target of e, decided randomly.

HigherDegree 

The endpoint of e with the higher degree.

LowerDegree 

The endpoint of e with the lower degree.

HigherNonPlanarDegree 

The endpoint of e with the higher number of incident edges not in the planar subgraph.

LowerNonPlanarDegree 

The endpoint of e with the lower number of incident edges not in the planar subgraph.

BothEndpoints 

Both the source and the target of e.

Definition at line 89 of file PlanarizerMixedInsertion.h.

Constructor & Destructor Documentation

◆ PlanarizerMixedInsertion() [1/2]

ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion ( )

Creates a PlanarizerMixedInsertion with default settings.

◆ PlanarizerMixedInsertion() [2/2]

ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion ( const PlanarizerMixedInsertion planarizer)

Creates a PlanarizerMixedInsertion with the same settings as planarizer.

Member Function Documentation

◆ clone()

virtual CrossingMinimizationModule* ogdf::PlanarizerMixedInsertion::clone ( ) const
overridevirtual

Returns a new PlanarizerMixedInsertion with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

virtual ReturnType ogdf::PlanarizerMixedInsertion::doCall ( PlanRep pr,
int  cc,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< uint32_t > *  pEdgeSubGraphs,
int &  crossingNumber 
)
overrideprotectedvirtual

Implements the algorithm call.

Precondition
pr must be simple.

Implements ogdf::CrossingMinimizationModule.

◆ nodeSelectionMethod() [1/2]

NodeSelectionMethod ogdf::PlanarizerMixedInsertion::nodeSelectionMethod ( )
inline

Returns the used method of selecting nodes to reinsert.

Definition at line 118 of file PlanarizerMixedInsertion.h.

◆ nodeSelectionMethod() [2/2]

void ogdf::PlanarizerMixedInsertion::nodeSelectionMethod ( NodeSelectionMethod  method)
inline

Sets the used method of selecting nodes to reinsert.

Definition at line 121 of file PlanarizerMixedInsertion.h.

◆ operator=()

PlanarizerMixedInsertion& ogdf::PlanarizerMixedInsertion::operator= ( const PlanarizerMixedInsertion planarizer)

Assignment operator, copies option settings only.

◆ setSubgraph()

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

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

Definition at line 113 of file PlanarizerMixedInsertion.h.

Member Data Documentation

◆ m_nodeSelectionMethod

NodeSelectionMethod ogdf::PlanarizerMixedInsertion::m_nodeSelectionMethod
private

Definition at line 130 of file PlanarizerMixedInsertion.h.

◆ m_subgraph

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

< The planar subgraph algorithm.

How to select the nodes which are reinserted.

Definition at line 127 of file PlanarizerMixedInsertion.h.


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