Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarizerStarReinsertion Class Reference

The star (re-)insertion approach for crossing minimization. More...

#include <ogdf/planarity/PlanarizerStarReinsertion.h>

+ Inheritance diagram for ogdf::PlanarizerStarReinsertion:

Public Member Functions

 PlanarizerStarReinsertion ()
 Creates a PlanarizerStarReinsertion with default settings. More...
 
 PlanarizerStarReinsertion (const PlanarizerStarReinsertion &planarizer)
 Creates a PlanarizerStarReinsertion with the same settings as planarizer. More...
 
virtual CrossingMinimizationModuleclone () const override
 Returns a new PlanarizerStarReinsertion with the same option settings. More...
 
PlanarizerStarReinsertionoperator= (const PlanarizerStarReinsertion &planarizer)
 Assignment operator, copies option settings only. More...
 
void setPlanarization (CrossingMinimizationModule *pPlanarizationModule)
 Sets the module option for the computation of the inital planarization. More...
 
Optional parameters
bool setTimeout ()
 Returns the current setting of options setTimeout. More...
 
void setTimeout (bool b)
 Sets the option setTimeout to b. More...
 
int maxIterations ()
 Returns the number of maxIterations. More...
 
void maxIterations (int maxIterations)
 Sets the maximum number of iterations. 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

ReturnType mainLoop (const PlanRep &pr, CrossingStructure &bestCS, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs)
 Reinserts a specific set of stars until a termination criterion is met. More...
 
bool reinsertStar (GraphCopy &currentPlanarization, DynamicDualGraph &dualGraph, node nodeToReinsert, CrossingStructure &bestCS, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs)
 Reinserts the star nodeToReinsert in currentPlanarization. More...
 

Private Attributes

StarInserter m_inserter
 
int m_maxIterations
 The maximum number of iterations. More...
 
std::unique_ptr< CrossingMinimizationModulem_planarization
 The initial planarization algorithm. More...
 
bool m_setTimeout
 Helper to insert stars. More...
 
int64_t m_stopTime
 When the algorithm should stop. 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

The star (re-)insertion approach for crossing minimization.

This crossing minimization module represents a customizable implementation of the star insertion approach. This approach consists of two phases. In the first phase, a planarization of the graph is computed, i.e. a planarized representation with crossings replaced by dummy nodes of degree 4. In the second phase, a set of original nodes (each with its star insertion paths) is re-inserted with as few crossings as possible, until no improvement is possible anymore (the configuration is "locally optimal" or a maximum number of iterations is reached.

The first step, i.e. the computation of the planarization, is implemented via a module option while the maximum number of iterations can be set directly.

More details on the star insertion approach can be found in

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

Optional parameters

OptionTypeDefaultDescription
setTimeoutbooltrue If set to true, the time limit is also passed to submodules; otherwise, a timeout might be checked late when a submodule requires a lot of runtime.
maxIterationsint-1 Maximum number of iterations. If negative, the algorithm stops when local optimality is reached. See maxIterations(int).

Module options

The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:

OptionTypeDefaultDescription
planarizationCrossingMinimizationModule SubgraphPlanarizer using FixedEmbeddingInserter The module for the computation of the planar subgraph.

Definition at line 98 of file PlanarizerStarReinsertion.h.

Constructor & Destructor Documentation

◆ PlanarizerStarReinsertion() [1/2]

ogdf::PlanarizerStarReinsertion::PlanarizerStarReinsertion ( )

Creates a PlanarizerStarReinsertion with default settings.

◆ PlanarizerStarReinsertion() [2/2]

ogdf::PlanarizerStarReinsertion::PlanarizerStarReinsertion ( const PlanarizerStarReinsertion planarizer)

Creates a PlanarizerStarReinsertion with the same settings as planarizer.

Member Function Documentation

◆ clone()

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

Returns a new PlanarizerStarReinsertion with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

virtual ReturnType ogdf::PlanarizerStarReinsertion::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 biconnected, simple, and already embedded, with pseudo crossings being removed.

Implements ogdf::CrossingMinimizationModule.

◆ mainLoop()

ReturnType ogdf::PlanarizerStarReinsertion::mainLoop ( const PlanRep pr,
CrossingStructure bestCS,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< uint32_t > *  pEdgeSubGraphs 
)
private

Reinserts a specific set of stars until a termination criterion is met.

Either the timout or the maximum number of iterations is reached, or the solution is locally optimal.

Parameters
prplanarized representation of the graph.
bestCSis assigned a representation of currentPlanarization with the least crossings found during the loop and its crossing number.
pCostOrigpoints to the cost of each original edge.
pForbiddenOrigpoints to an indicator for each original edge whether it is forbidden to be crossed.
pEdgeSubGraphspoints to an indicator for each original edge to which subgraph it belongs.
Returns
the return type of the algorithm.

◆ maxIterations() [1/2]

int ogdf::PlanarizerStarReinsertion::maxIterations ( )
inline

Returns the number of maxIterations.

Definition at line 200 of file PlanarizerStarReinsertion.h.

◆ maxIterations() [2/2]

void ogdf::PlanarizerStarReinsertion::maxIterations ( int  maxIterations)
inline

Sets the maximum number of iterations.

The algorithm terminates when the drawing is locally crossing-optimal: It tries to re-insert all of the nodes of the graph one after another; it stops when there is no node anymore whose re-insertion would improve the number of crossings.

The algorithm can be stopped ealier by setting a maximum number of iterations (during each of which all reinsertable nodes are reinserted). A number lower than 0 indicates that the algorithm should not be stopped before a locally optimal solution is found.

Definition at line 214 of file PlanarizerStarReinsertion.h.

◆ operator=()

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

Assignment operator, copies option settings only.

◆ reinsertStar()

bool ogdf::PlanarizerStarReinsertion::reinsertStar ( GraphCopy currentPlanarization,
DynamicDualGraph dualGraph,
node  nodeToReinsert,
CrossingStructure bestCS,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< uint32_t > *  pEdgeSubGraphs 
)
private

Reinserts the star nodeToReinsert in currentPlanarization.

If the reinsertion leads to a lower crossing number, update bestCS.

Parameters
currentPlanarizationplanarized representation of the graph.
dualGraphdual graph of currentPlanarization.
nodeToReinsertthe node to be reinserted.
bestCSis (assigned) a representation of currentPlanarization with the least crossings found so far as well as its crossing number.
pCostOrigpoints to the cost of each original edge.
pForbiddenOrigpoints to an indicator for each original edge whether it is forbidden to be crossed.
pEdgeSubGraphspoints to an indicator for each original edge to which subgraph it belongs.
Returns
whether a better solution was found, i.e. whether bestCS was updated.

◆ setPlanarization()

void ogdf::PlanarizerStarReinsertion::setPlanarization ( CrossingMinimizationModule pPlanarizationModule)
inline

Sets the module option for the computation of the inital planarization.

Definition at line 186 of file PlanarizerStarReinsertion.h.

◆ setTimeout() [1/2]

bool ogdf::PlanarizerStarReinsertion::setTimeout ( )
inline

Returns the current setting of options setTimeout.

Definition at line 194 of file PlanarizerStarReinsertion.h.

◆ setTimeout() [2/2]

void ogdf::PlanarizerStarReinsertion::setTimeout ( bool  b)
inline

Sets the option setTimeout to b.

Definition at line 197 of file PlanarizerStarReinsertion.h.

Member Data Documentation

◆ m_inserter

StarInserter ogdf::PlanarizerStarReinsertion::m_inserter
private

Definition at line 104 of file PlanarizerStarReinsertion.h.

◆ m_maxIterations

int ogdf::PlanarizerStarReinsertion::m_maxIterations
private

The maximum number of iterations.

Definition at line 108 of file PlanarizerStarReinsertion.h.

◆ m_planarization

std::unique_ptr<CrossingMinimizationModule> ogdf::PlanarizerStarReinsertion::m_planarization
private

The initial planarization algorithm.

Definition at line 102 of file PlanarizerStarReinsertion.h.

◆ m_setTimeout

bool ogdf::PlanarizerStarReinsertion::m_setTimeout
private

Helper to insert stars.

The option for setting timeouts in submodules.

Definition at line 106 of file PlanarizerStarReinsertion.h.

◆ m_stopTime

int64_t ogdf::PlanarizerStarReinsertion::m_stopTime
private

When the algorithm should stop.

Definition at line 110 of file PlanarizerStarReinsertion.h.


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