Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarizerChordlessCycle Class Reference

#include <ogdf/planarity/PlanarizerChordlessCycle.h>

+ Inheritance diagram for ogdf::PlanarizerChordlessCycle:

Public Member Functions

 PlanarizerChordlessCycle ()
 Creates a PlanarizerChordlessCycle with default settings. More...
 
 PlanarizerChordlessCycle (const PlanarizerChordlessCycle &planarizer)
 Creates a PlanarizerChordlessCycle with the same settings as planarizer. More...
 
virtual CrossingMinimizationModuleclone () const override
 Returns a new PlanarizerChordlessCycle with the same option settings. More...
 
PlanarizerChordlessCycleoperator= (const PlanarizerChordlessCycle &planarizer)
 Assignment operator, copies option settings only. 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 Member Functions

void addToGraphCopy (GraphCopy &graphCopy, GraphCopy &copyCopy, DynamicDualGraph &dual, node vOrig, const EdgeArray< int > *pCostOrig, EdgeArray< int > *pCostCopy)
 Creates a copy of vOrig in graphCopy and optimally inserts a copy of this copy in the planarization copyCopy. More...
 
bool findChordlessCycle (const Graph &G, List< node > &cycle)
 
void transferToPlanRep (PlanRep &pr, const GraphCopy &graphCopy, const GraphCopy &copyCopy)
 Creates crossings in pr that resemble the crossings in copyCopy. More...
 

Private Attributes

StarInserter m_inserter
 The StarInserter used to insert new nodes into the planarization. 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...
 
- 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

Starts with a chordless cycle of the graph and then inserts each original node that is adjacent to already inserted ones via the StarInserter. See:

K. Clancy, M. Haythorpe, A. Newcombe: An effective crossing minimisation heuristic based on star insertion. J. Graph Algorithms Appl. 23(2): 135-166 (2019)

Warning
Ignores the time limit set in the CrossingMinimizationModule. However, the heuristic should be very fast in practice anyway.

Definition at line 53 of file PlanarizerChordlessCycle.h.

Constructor & Destructor Documentation

◆ PlanarizerChordlessCycle() [1/2]

ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle ( )

Creates a PlanarizerChordlessCycle with default settings.

◆ PlanarizerChordlessCycle() [2/2]

ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle ( const PlanarizerChordlessCycle planarizer)

Creates a PlanarizerChordlessCycle with the same settings as planarizer.

Member Function Documentation

◆ addToGraphCopy()

void ogdf::PlanarizerChordlessCycle::addToGraphCopy ( GraphCopy graphCopy,
GraphCopy copyCopy,
DynamicDualGraph dual,
node  vOrig,
const EdgeArray< int > *  pCostOrig,
EdgeArray< int > *  pCostCopy 
)
private

Creates a copy of vOrig in graphCopy and optimally inserts a copy of this copy in the planarization copyCopy.

Parameters
graphCopyis the graph copy of the original graph.
copyCopyis the graph copy/planarization of graphCopy.
dualis the dual graph of copyCopy.
vOrigis the node in the original graph for which a copy is created in graphCopy and copyCopy.
pCostOrigare the edge costs in the original graph.
pCostCopyare the edge costs in graphCopy (edge costs for the newly created edges are added).

◆ clone()

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

Returns a new PlanarizerChordlessCycle with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

virtual ReturnType ogdf::PlanarizerChordlessCycle::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.

◆ findChordlessCycle()

bool ogdf::PlanarizerChordlessCycle::findChordlessCycle ( const Graph G,
List< node > &  cycle 
)
private
Parameters
Ggraph in which a chordless cycle should be found.
cycleis assigned a list of nodes in G which induce a chordless cycle.

◆ operator=()

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

Assignment operator, copies option settings only.

◆ transferToPlanRep()

void ogdf::PlanarizerChordlessCycle::transferToPlanRep ( PlanRep pr,
const GraphCopy graphCopy,
const GraphCopy copyCopy 
)
private

Creates crossings in pr that resemble the crossings in copyCopy.

Warning
the order of adjEntries around each node is not copied.
Parameters
pris assigned the final planarization as it is contained in copyCopy in terms of crossings (but pr must be planarly embedded again afterwards).
graphCopyis a copy of pr's original graph and the original of copyCopy.
copyCopyis a planarization that contains the crossings that should be copied to pr.

Member Data Documentation

◆ m_inserter

StarInserter ogdf::PlanarizerChordlessCycle::m_inserter
private

The StarInserter used to insert new nodes into the planarization.

Definition at line 127 of file PlanarizerChordlessCycle.h.


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