Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SubgraphPlanarizer Class Reference

The planarization approach for crossing minimization. More...

#include <ogdf/planarity/SubgraphPlanarizer.h>

+ Inheritance diagram for ogdf::SubgraphPlanarizer:

Public Member Functions

 SubgraphPlanarizer ()
 Creates an instance of subgraph planarizer with default settings. More...
 
 SubgraphPlanarizer (const SubgraphPlanarizer &planarizer)
 Creates an instance of subgraph planarizer with the same settings as planarizer. More...
 
virtual CrossingMinimizationModuleclone () const override
 Returns a new instance of subgraph planarizer with the same option settings. More...
 
unsigned int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (unsigned int n)
 Sets the maximal number of used threads to n. More...
 
SubgraphPlanarizeroperator= (const SubgraphPlanarizer &planarizer)
 Assignment operator. Copies option settings only. More...
 
int permutations ()
 Returns the number of permutations. More...
 
void permutations (int p)
 Sets the number of permutations to p. More...
 
void setInserter (EdgeInsertionModule *pInserter)
 Sets the module option for the edge insertion module. More...
 
void setSubgraph (PlanarSubgraphModule< int > *pSubgraph)
 Sets the module option for the computation of the planar subgraph. More...
 
bool setTimeout ()
 Returns the current setting of options setTimeout. More...
 
void setTimeout (bool b)
 Sets the option setTimeout to b. 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...
 
- Public Member Functions inherited from ogdf::Logger
 Logger ()
 creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel More...
 
 Logger (Level level)
 creates a new Logger-object with LogMode::Log and given local log-level More...
 
 Logger (LogMode m)
 creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More...
 
 Logger (LogMode m, Level level)
 creates a new Logger-object with given log-mode and given local log-level More...
 
bool is_lout (Level level=Level::Default) const
 returns true if such an lout command will result in text being printed More...
 
std::ostream & lout (Level level=Level::Default, bool indent=true) const
 stream for logging-output (local) More...
 
std::ostream & sout () const
 stream for statistic-output (local) More...
 
std::ostream & fout () const
 stream for forced output (local) More...
 
Level localLogLevel () const
 gives the local log-level More...
 
void localLogLevel (Level level)
 sets the local log-level More...
 
LogMode localLogMode () const
 gives the local log-mode More...
 
void localLogMode (LogMode m)
 sets the local log-mode More...
 
void indent (int by=1)
 
void dedent (int by=1)
 
int getIndent () const
 
void setIndent (int indent)
 
Level effectiveLogLevel () const
 obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings) More...
 
bool effectiveStatisticMode () const
 returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) 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...
 

Static Private Member Functions

static bool doSinglePermutation (PlanRepLight &prl, int cc, const EdgeArray< int > *pCost, const EdgeArray< bool > *pForbid, const EdgeArray< uint32_t > *pEdgeSubGraphs, Array< edge > &deletedEdges, EdgeInsertionModule &inserter, std::minstd_rand &rng, int &crossingNumber)
 
static void doWorkHelper (ThreadMaster &master, EdgeInsertionModule &inserter, std::minstd_rand &rng)
 

Private Attributes

std::unique_ptr< EdgeInsertionModulem_inserter
 The edge insertion module. More...
 
unsigned int m_maxThreads
 The maximal number of used threads. More...
 
int m_permutations
 The number of permutations. More...
 
bool m_setTimeout
 The option for setting timeouts in submodules. More...
 
std::unique_ptr< PlanarSubgraphModule< int > > m_subgraph
 The planar subgraph algorithm. 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...
 
- Public Types inherited from ogdf::Logger
enum  Level { Level::Minor, Level::Medium, Level::Default, Level::High, Level::Alarm, Level::Force }
 supported log-levels from lowest to highest importance More...
 
enum  LogMode { LogMode::Global, LogMode::GlobalLog, LogMode::Log, LogMode::Statistic }
 Local log-modes. 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 Public Member Functions inherited from ogdf::Logger
static bool is_slout (Level level=Level::Default)
 returns true if such an slout command will result in text being printed More...
 
static std::ostream & slout (Level level=Level::Default)
 stream for logging-output (global) More...
 
static std::ostream & ssout ()
 stream for statistic-output (global) More...
 
static std::ostream & sfout ()
 stream for forced output (global) More...
 
static bool is_ilout (Level level=Level::Default)
 stream for logging-output (global; used by internal libraries, e.g. Abacus) returns true if such an ilout command will result in text being printed More...
 
static std::ostream & ilout (Level level=Level::Default)
 
static std::ostream & ifout ()
 stream for forced output (global; used by internal libraries, e.g. Abacus) More...
 
static Level globalLogLevel ()
 gives the global log-level More...
 
static void globalLogLevel (Level level)
 sets the global log-level More...
 
static Level globalInternalLibraryLogLevel ()
 gives the internal-library log-level More...
 
static void globalInternalLibraryLogLevel (Level level)
 sets the internal-library log-level More...
 
static Level globalMinimumLogLevel ()
 gives the globally minimally required log-level More...
 
static void globalMinimumLogLevel (Level level)
 sets the globally minimally required log-level More...
 
static bool globalStatisticMode ()
 returns true if we are globally in statistic mode More...
 
static void globalStatisticMode (bool s)
 sets whether we are globally in statistic mode More...
 
static void setWorldStream (std::ostream &o)
 change the stream to which allowed output is written (by default: std::cout) 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 planarization approach for crossing minimization.

This crossing minimization module represents a customizable implementation of the planarization approach. This approach consists of two phases. In the first phase, a planar subgraph is computed, and in the second phase, the remaining edges are re-inserted one-by-one, each time with as few crossings as possible; the crossings are then replaced by dummy nodes of degree four, resulting in a planarized representation of the graph.

Both steps, the computation of the planar subgraph and the re-insertion of a single edge, are implemented using module options. Additionaly, the second phase can be repeated several times, each time with a randomly permuted order of the edges to be re-inserted, and taking the solution with the least crossings. This can improve the quality of the solution significantly. More details on the planarization approach can be found in

C. Gutwenger, P. Mutzel: An Experimental Study of Crossing Minimization Heuristics. 11th International Symposium on Graph Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.

Optional parameters

OptionTypeDefaultDescription
permutationsint1 The number of permutations the (complete) edge insertion phase is repeated.
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.
maxThreadsintSystem::numberOfProcessors() This is the maximal number of threads that will be used for parallelizing the algorithm. At the moment, each permutation is parallelized, hence the there will never be used more threads than permutations. To achieve sequential behaviour, set maxThreads to 1.

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
subgraphPlanarSubgraphModuleFastPlanarSubgraph The module for the computation of the planar subgraph.
inserterEdgeInsertionModuleVariableEmbeddingInserter The module used for edge insertion. The edges not contained in the planar subgraph are re-inserted one-by-one, each with as few crossings as possible.

Definition at line 106 of file SubgraphPlanarizer.h.

Constructor & Destructor Documentation

◆ SubgraphPlanarizer() [1/2]

ogdf::SubgraphPlanarizer::SubgraphPlanarizer ( )

Creates an instance of subgraph planarizer with default settings.

◆ SubgraphPlanarizer() [2/2]

ogdf::SubgraphPlanarizer::SubgraphPlanarizer ( const SubgraphPlanarizer planarizer)

Creates an instance of subgraph planarizer with the same settings as planarizer.

Member Function Documentation

◆ clone()

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

Returns a new instance of subgraph planarizer with the same option settings.

Implements ogdf::CrossingMinimizationModule.

◆ doCall()

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

Implements ogdf::CrossingMinimizationModule.

◆ doSinglePermutation()

static bool ogdf::SubgraphPlanarizer::doSinglePermutation ( PlanRepLight prl,
int  cc,
const EdgeArray< int > *  pCost,
const EdgeArray< bool > *  pForbid,
const EdgeArray< uint32_t > *  pEdgeSubGraphs,
Array< edge > &  deletedEdges,
EdgeInsertionModule inserter,
std::minstd_rand &  rng,
int &  crossingNumber 
)
staticprivate

◆ doWorkHelper()

static void ogdf::SubgraphPlanarizer::doWorkHelper ( ThreadMaster &  master,
EdgeInsertionModule inserter,
std::minstd_rand &  rng 
)
staticprivate

◆ maxThreads() [1/2]

unsigned int ogdf::SubgraphPlanarizer::maxThreads ( ) const
inline

Returns the maximal number of used threads.

Definition at line 148 of file SubgraphPlanarizer.h.

◆ maxThreads() [2/2]

void ogdf::SubgraphPlanarizer::maxThreads ( unsigned int  n)
inline

Sets the maximal number of used threads to n.

Definition at line 151 of file SubgraphPlanarizer.h.

◆ operator=()

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

Assignment operator. Copies option settings only.

◆ permutations() [1/2]

int ogdf::SubgraphPlanarizer::permutations ( )
inline

Returns the number of permutations.

Definition at line 136 of file SubgraphPlanarizer.h.

◆ permutations() [2/2]

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

Sets the number of permutations to p.

Definition at line 139 of file SubgraphPlanarizer.h.

◆ setInserter()

void ogdf::SubgraphPlanarizer::setInserter ( EdgeInsertionModule pInserter)
inline

Sets the module option for the edge insertion module.

Definition at line 133 of file SubgraphPlanarizer.h.

◆ setSubgraph()

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

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

Definition at line 130 of file SubgraphPlanarizer.h.

◆ setTimeout() [1/2]

bool ogdf::SubgraphPlanarizer::setTimeout ( )
inline

Returns the current setting of options setTimeout.

Definition at line 142 of file SubgraphPlanarizer.h.

◆ setTimeout() [2/2]

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

Sets the option setTimeout to b.

Definition at line 145 of file SubgraphPlanarizer.h.

Member Data Documentation

◆ m_inserter

std::unique_ptr<EdgeInsertionModule> ogdf::SubgraphPlanarizer::m_inserter
private

The edge insertion module.

Definition at line 167 of file SubgraphPlanarizer.h.

◆ m_maxThreads

unsigned int ogdf::SubgraphPlanarizer::m_maxThreads
private

The maximal number of used threads.

Definition at line 171 of file SubgraphPlanarizer.h.

◆ m_permutations

int ogdf::SubgraphPlanarizer::m_permutations
private

The number of permutations.

Definition at line 169 of file SubgraphPlanarizer.h.

◆ m_setTimeout

bool ogdf::SubgraphPlanarizer::m_setTimeout
private

The option for setting timeouts in submodules.

Definition at line 170 of file SubgraphPlanarizer.h.

◆ m_subgraph

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

The planar subgraph algorithm.

Definition at line 166 of file SubgraphPlanarizer.h.


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