Open
Graph Drawing
Framework

 v.2015.05
 

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
 Returns a new instance of subgraph planarizer with the same option settings. More...
 
int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (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 *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=0, const EdgeArray< bool > *pForbiddenOrig=0, const EdgeArray< __uint32 > *pEdgeSubGraphs=0)
 Computes a planarized representation of the input graph. More...
 
ReturnType operator() (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=0, const EdgeArray< bool > *pForbiddenOrig=0, const EdgeArray< __uint32 > *pEdgeSubGraphs=0)
 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 (double t)
 timeout is set to the given value (seconds) More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
double timeLimit () const
 returns the current time limit for the call More...
 
- Public Member Functions inherited from ogdf::Logger
 Logger ()
 creates a new Logger-object with LM_GLOBAL and local log-level equal globalLogLevel More...
 
 Logger (LogMode m)
 creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More...
 
 Logger (Level l)
 creates a new Logger-object with LM_GLOBAL and given local log-level More...
 
 Logger (LogMode m, Level l)
 creates a new Logger-object with given log-mode and given local log-level More...
 
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...
 
std::ostream & fout () const
 stream for forced output (local) More...
 
bool is_lout (Level l=LL_DEFAULT) const
 returns true if such an lout command will result in text being printed More...
 
Level localLogLevel () const
 gives the local log-level More...
 
void localLogLevel (Level l)
 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...
 
std::ostream & lout (Level l=LL_DEFAULT) const
 stream for logging-output (local) More...
 
std::ostream & sout () const
 stream for statistic-output (local) More...
 

Protected Member Functions

virtual ReturnType doCall (PlanRep &pr, int cc, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< __uint32 > *pEdgeSubGraphs, int &crossingNumber)
 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 > *pEdgeSubGraphs, Array< edge > &deletedEdges, EdgeInsertionModule &inserter, int &crossingNumber)
 
static void doWorkHelper (ThreadMaster &master, EdgeInsertionModule &inserter)
 

Private Attributes

ModuleOption< EdgeInsertionModulem_inserter
 The edge insertion module. More...
 
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...
 
ModuleOption< PlanarSubgraphModulem_subgraph
 The planar subgraph algorithm. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
 The return type of a module. More...
 
- Public Types inherited from ogdf::Logger
enum  Level { LL_MINOR, LL_MEDIUM, LL_DEFAULT, LL_HIGH, LL_ALARM, LL_FORCE }
 supported log-levels from lowest to highest importance More...
 
enum  LogMode { LM_GLOBAL, LM_GLOBALLOG, LM_LOG, LM_STATISTIC }
 (local) log-modes (see class description) More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff retVal indicates that the module returned a feasible solution. More...
 
- Static Public Member Functions inherited from ogdf::Logger
static Level globalInternalLibraryLogLevel ()
 gives the internal-library log-level More...
 
static void globalInternalLibraryLogLevel (Level l)
 sets the internal-library log-level More...
 
static Level globalLogLevel ()
 gives the global log-level More...
 
static void globalLogLevel (Level l)
 sets the global log-level More...
 
static Level globalMinimumLogLevel ()
 gives the globally minimally required log-level More...
 
static void globalMinimumLogLevel (Level l)
 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 std::ostream & ifout ()
 stream for forced output (global; used by internal libraries, e.g. Abacus) More...
 
static std::ostream & ilout (Level l=LL_DEFAULT)
 
static bool is_ilout (Level l=LL_DEFAULT)
 
static bool is_slout (Level l=LL_DEFAULT)
 returns true if such an slout command will result in text being printed More...
 
static void setWorldStream (std::ostream &o)
 change the stream to which allowed output is written (by default: cout) More...
 
static std::ostream & sfout ()
 stream for forced output (global) More...
 
static std::ostream & slout (Level l=LL_DEFAULT)
 stream for logging-output (global) More...
 
static std::ostream & ssout ()
 stream for statistic-output (global) 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 122 of file SubgraphPlanarizer.h.

Constructor & Destructor Documentation

ogdf::SubgraphPlanarizer::SubgraphPlanarizer ( )

Creates an instance of subgraph planarizer with default settings.

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

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

Member Function Documentation

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

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

Implements ogdf::CrossingMinimizationModule.

virtual ReturnType ogdf::SubgraphPlanarizer::doCall ( PlanRep pr,
int  cc,
const EdgeArray< int > *  pCostOrig,
const EdgeArray< bool > *  pForbiddenOrig,
const EdgeArray< __uint32 > *  pEdgeSubGraphs,
int &  crossingNumber 
)
protectedvirtual

Implements the algorithm call.

Implements ogdf::CrossingMinimizationModule.

static bool ogdf::SubgraphPlanarizer::doSinglePermutation ( PlanRepLight prl,
int  cc,
const EdgeArray< int > *  pCost,
const EdgeArray< bool > *  pForbid,
const EdgeArray< __uint32 > *  pEdgeSubGraphs,
Array< edge > &  deletedEdges,
EdgeInsertionModule inserter,
int &  crossingNumber 
)
staticprivate
static void ogdf::SubgraphPlanarizer::doWorkHelper ( ThreadMaster &  master,
EdgeInsertionModule inserter 
)
staticprivate
int ogdf::SubgraphPlanarizer::maxThreads ( ) const
inline

Returns the maximal number of used threads.

Definition at line 173 of file SubgraphPlanarizer.h.

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

Sets the maximal number of used threads to n.

Definition at line 176 of file SubgraphPlanarizer.h.

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

Assignment operator. Copies option settings only.

int ogdf::SubgraphPlanarizer::permutations ( )
inline

Returns the number of permutations.

Definition at line 161 of file SubgraphPlanarizer.h.

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

Sets the number of permutations to p.

Definition at line 164 of file SubgraphPlanarizer.h.

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

Sets the module option for the edge insertion module.

Definition at line 156 of file SubgraphPlanarizer.h.

void ogdf::SubgraphPlanarizer::setSubgraph ( PlanarSubgraphModule pSubgraph)
inline

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

Definition at line 151 of file SubgraphPlanarizer.h.

bool ogdf::SubgraphPlanarizer::setTimeout ( )
inline

Returns the current setting of options setTimeout.

Definition at line 167 of file SubgraphPlanarizer.h.

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

Sets the option setTimeout to b.

Definition at line 170 of file SubgraphPlanarizer.h.

Member Data Documentation

ModuleOption<EdgeInsertionModule> ogdf::SubgraphPlanarizer::m_inserter
private

The edge insertion module.

Definition at line 203 of file SubgraphPlanarizer.h.

int ogdf::SubgraphPlanarizer::m_maxThreads
private

The maximal number of used threads.

Definition at line 207 of file SubgraphPlanarizer.h.

int ogdf::SubgraphPlanarizer::m_permutations
private

The number of permutations.

Definition at line 205 of file SubgraphPlanarizer.h.

bool ogdf::SubgraphPlanarizer::m_setTimeout
private

The option for setting timeouts in submodules.

Definition at line 206 of file SubgraphPlanarizer.h.

ModuleOption<PlanarSubgraphModule> ogdf::SubgraphPlanarizer::m_subgraph
private

The planar subgraph algorithm.

Definition at line 202 of file SubgraphPlanarizer.h.


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