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.

	SubgraphPlanarizer (const SubgraphPlanarizer &planarizer)
	Creates an instance of subgraph planarizer with the same settings as `planarizer`.

virtual CrossingMinimizationModule *	clone () const override
	Returns a new instance of subgraph planarizer with the same option settings.

unsigned int	maxThreads () const
	Returns the maximal number of used threads.

void	maxThreads (unsigned int n)
	Sets the maximal number of used threads to `n`.

SubgraphPlanarizer &	operator= (const SubgraphPlanarizer &planarizer)
	Assignment operator. Copies option settings only.

int	permutations ()
	Returns the number of permutations.

void	permutations (int p)
	Sets the number of permutations to `p`.

void	setInserter (EdgeInsertionModule *pInserter)
	Sets the module option for the edge insertion module.

void	setSubgraph (PlanarSubgraphModule< int > *pSubgraph)
	Sets the module option for the computation of the planar subgraph.

bool	setTimeout ()
	Returns the current setting of options setTimeout.

void	setTimeout (bool b)
	Sets the option setTimeout to `b`.

Public Member Functions inherited from ogdf::CrossingMinimizationModule
	CrossingMinimizationModule ()
	Initializes a crossing minimization module (default constructor).

	CrossingMinimizationModule (const CrossingMinimizationModule &cmm)
	Initializes an crossing minimization module (copy constructor).

virtual	~CrossingMinimizationModule ()
	Destructor.

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.

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.

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

virtual	~Module ()

Public Member Functions inherited from ogdf::Timeouter
	Timeouter ()
	timeout is turned of by default

	Timeouter (bool t)
	timeout is turned off (false) or on (true) (with 0 second)

	Timeouter (const Timeouter &t)

	Timeouter (double t)
	timeout is set to the given value (seconds)

	~Timeouter ()

bool	isTimeLimit () const
	returns whether any time limit is set or not

Timeouter &	operator= (const Timeouter &t)

double	timeLimit () const
	returns the current time limit for the call

void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)

void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.

Public Member Functions inherited from ogdf::Logger
	Logger ()
	creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel

	Logger (Level level)
	creates a new Logger-object with LogMode::Global and given local log-level

	Logger (LogMode m)
	creates a new Logger-object with given log-mode and local log-level equal globalLogLevel

	Logger (LogMode m, Level level)
	creates a new Logger-object with given log-mode and given local log-level

bool	is_lout (Level level=Level::Default) const
	returns true if such an lout command will result in text being printed

std::ostream &	lout (Level level=Level::Default) const
	stream for logging-output (local)

std::ostream &	sout () const
	stream for statistic-output (local)

std::ostream &	fout () const
	stream for forced output (local)

Level	localLogLevel () const
	gives the local log-level

void	localLogLevel (Level level)
	sets the local log-level

LogMode	localLogMode () const
	gives the local log-mode

void	localLogMode (LogMode m)
	sets the local log-mode

Level	effectiveLogLevel () const
	obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings)

bool	effectiveStatisticMode () const
	returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings)

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.

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< EdgeInsertionModule >	m_inserter
	The edge insertion module.

unsigned int	m_maxThreads
	The maximal number of used threads.

int	m_permutations
	The number of permutations.

bool	m_setTimeout
	The option for setting timeouts in submodules.

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

Additional Inherited Members
Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
	The return type of a module. More...

Public Types inherited from ogdf::Logger
enum class	Level { Minor , Medium , Default , High , Alarm , Force }
	supported log-levels from lowest to highest importance More...

enum class	LogMode { Global , GlobalLog , Log , 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.

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

static std::ostream &	slout (Level level=Level::Default)
	stream for logging-output (global)

static std::ostream &	ssout ()
	stream for statistic-output (global)

static std::ostream &	sfout ()
	stream for forced output (global)

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

static std::ostream &	ilout (Level level=Level::Default)

static std::ostream &	ifout ()
	stream for forced output (global; used by internal libraries, e.g. Abacus)

static Level	globalLogLevel ()
	gives the global log-level

static void	globalLogLevel (Level level)
	sets the global log-level

static Level	globalInternalLibraryLogLevel ()
	gives the internal-library log-level

static void	globalInternalLibraryLogLevel (Level level)
	sets the internal-library log-level

static Level	globalMinimumLogLevel ()
	gives the globally minimally required log-level

static void	globalMinimumLogLevel (Level level)
	sets the globally minimally required log-level

static bool	globalStatisticMode ()
	returns true if we are globally in statistic mode

static void	globalStatisticMode (bool s)
	sets whether we are globally in statistic mode

static void	setWorldStream (std::ostream &o)
	change the stream to which allowed output is written (by default: `std::cout`)

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`.

Protected Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

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

Option	Type	Default	Description
permutations	int	1	The number of permutations the (complete) edge insertion phase is repeated.
setTimeout	bool	true	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.
maxThreads	int	System::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:

Option	Type	Default	Description
subgraph	PlanarSubgraphModule	FastPlanarSubgraph	The module for the computation of the planar subgraph.
inserter	EdgeInsertionModule	VariableEmbeddingInserter	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:

include/ogdf/planarity/SubgraphPlanarizer.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Optional parameters

Module options

Constructor & Destructor Documentation

◆ SubgraphPlanarizer() [1/2]

◆ SubgraphPlanarizer() [2/2]

Member Function Documentation

◆ clone()

◆ doCall()

◆ doSinglePermutation()

◆ doWorkHelper()

◆ maxThreads() [1/2]

◆ maxThreads() [2/2]

◆ operator=()

◆ permutations() [1/2]

◆ permutations() [2/2]

◆ setInserter()

◆ setSubgraph()

◆ setTimeout() [1/2]

◆ setTimeout() [2/2]

Member Data Documentation

◆ m_inserter

◆ m_maxThreads

◆ m_permutations

◆ m_setTimeout

◆ m_subgraph

Open
Graph Drawing
Framework