Computation of a planar subgraph using PQ-trees. More...

#include <ogdf/planarity/PlanarSubgraphFast.h>

Inheritance diagram for ogdf::PlanarSubgraphFast< TCost >:

Classes
class	ThreadMaster

class	Worker

Public Member Functions
	PlanarSubgraphFast ()
	Creates an instance of the fast planar subgraph algorithm with default settings (runs = 10).

virtual PlanarSubgraphFast *	clone () const override
	Returns a new instance of fast planar subgraph with the same option settings.

int	runs () const
	Returns the current number of randomized runs.

void	runs (int nRuns)
	Sets the number of randomized runs to `nRuns`.

Public Member Functions inherited from ogdf::PlanarSubgraphModule< TCost >
	PlanarSubgraphModule ()
	Initializes a planar subgraph module (default constructor).

ReturnType	call (const Graph &G, const EdgeArray< TCost > &cost, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

ReturnType	call (const Graph &G, const EdgeArray< TCost > &cost, List< edge > &delEdges)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

ReturnType	call (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

ReturnType	call (const Graph &G, List< edge > &delEdges)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

ReturnType	callAndDelete (GraphCopy &GC, const List< edge > &preferredEdges, List< edge > &delOrigEdges, bool preferredImplyPlanar=false)
	Makes `GC` planar by deleting edges.

ReturnType	callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges)
	Makes `G` planar by deleting edges.

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

ReturnType	operator() (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

ReturnType	operator() (const Graph &G, List< edge > &delEdges)
	Returns the set of edges `delEdges` which have to be deleted to obtain the planar subgraph.

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.

Protected Member Functions
virtual Module::ReturnType	doCall (const Graph &G, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferedImplyPlanar) override
	Returns true, if G is planar, false otherwise.

Private Types
using	BlockType = std::pair< Graph , EdgeArray< edge > >

Private Member Functions
void	parCall (const Array< BlockType > &block, const EdgeArray< TCost > *pCost, int nRuns, unsigned int nThreads, List< edge > &delEdges)
	Realizes the parallel implementation.

void	seqCall (const Array< BlockType > &block, const EdgeArray< TCost > *pCost, int nRuns, bool randomize, List< edge > &delEdges)
	Realizes the sequential implementation.

Static Private Member Functions
static void	doWorkHelper (ThreadMaster &master)

static void	planarize (const Graph &G, NodeArray< int > &numbering, List< edge > &delEdges)
	Performs a planarization on a biconnected component of `G`.

Private Attributes
int	m_nRuns
	The number of runs for randomization.

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

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.

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

Detailed Description

template<typename TCost>
class ogdf::PlanarSubgraphFast< TCost >

Computation of a planar subgraph using PQ-trees.

Literature: Jayakumar, Thulasiraman, Swamy 1989

Optional Parameters

Option	Type	Default	Description
runs	int	0	the number of randomized runs performed by the algorithm; the best solution is picked among all the runs. If runs is 0, one deterministic run is performed.

Observe that this algorithm by theory does not compute a maximal planar subgraph. It is however the fastest known good heuristic.

Definition at line 82 of file PlanarSubgraphFast.h.

Member Typedef Documentation

◆ BlockType

template<typename TCost >

using ogdf::PlanarSubgraphFast< TCost >::BlockType = std::pair<Graph*, EdgeArray<edge>*>

private

Definition at line 83 of file PlanarSubgraphFast.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphFast()

template<typename TCost >

ogdf::PlanarSubgraphFast< TCost >::PlanarSubgraphFast ( )

inline

Creates an instance of the fast planar subgraph algorithm with default settings (runs = 10).

Definition at line 170 of file PlanarSubgraphFast.h.

Member Function Documentation

◆ clone()

template<typename TCost >

virtual PlanarSubgraphFast * ogdf::PlanarSubgraphFast< TCost >::clone ( ) const

inlineoverridevirtual

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

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 173 of file PlanarSubgraphFast.h.

◆ doCall()

template<typename TCost >

virtual Module::ReturnType ogdf::PlanarSubgraphFast< TCost >::doCall	(	const Graph &	G,
		const List< edge > &	preferedEdges,
		List< edge > &	delEdges,
		const EdgeArray< TCost > *	pCost,
		bool	preferedImplyPlanar
	)

inlineoverrideprotectedvirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 191 of file PlanarSubgraphFast.h.

◆ doWorkHelper()

template<typename TCost >

static void ogdf::PlanarSubgraphFast< TCost >::doWorkHelper ( ThreadMaster & master )

inlinestaticprivate

Definition at line 405 of file PlanarSubgraphFast.h.

◆ parCall()

template<typename TCost >

void ogdf::PlanarSubgraphFast< TCost >::parCall	(	const Array< BlockType > &	block,
		const EdgeArray< TCost > *	pCost,
		int	nRuns,
		unsigned int	nThreads,
		List< edge > &	delEdges
	)

inlineprivate

Realizes the parallel implementation.

Definition at line 328 of file PlanarSubgraphFast.h.

◆ planarize()

template<typename TCost >

static void ogdf::PlanarSubgraphFast< TCost >::planarize	(	const Graph &	G,
		NodeArray< int > &	numbering,
		List< edge > &	delEdges
	)

inlinestaticprivate

Performs a planarization on a biconnected component of G.

The numbering contains an st-numbering of the component.

Definition at line 352 of file PlanarSubgraphFast.h.

◆ runs() [1/2]

template<typename TCost >

int ogdf::PlanarSubgraphFast< TCost >::runs ( ) const

inline

Returns the current number of randomized runs.

Definition at line 183 of file PlanarSubgraphFast.h.

◆ runs() [2/2]

template<typename TCost >

void ogdf::PlanarSubgraphFast< TCost >::runs ( int nRuns )

inline

Sets the number of randomized runs to nRuns.

Definition at line 180 of file PlanarSubgraphFast.h.

◆ seqCall()

template<typename TCost >

void ogdf::PlanarSubgraphFast< TCost >::seqCall	(	const Array< BlockType > &	block,
		const EdgeArray< TCost > *	pCost,
		int	nRuns,
		bool	randomize,
		List< edge > &	delEdges
	)

inlineprivate

Realizes the sequential implementation.

Definition at line 269 of file PlanarSubgraphFast.h.

Member Data Documentation

◆ m_nRuns

template<typename TCost >

int ogdf::PlanarSubgraphFast< TCost >::m_nRuns

private

The number of runs for randomization.

Definition at line 266 of file PlanarSubgraphFast.h.

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

include/ogdf/planarity/PlanarSubgraphFast.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Optional Parameters

Member Typedef Documentation

◆ BlockType

Constructor & Destructor Documentation

◆ PlanarSubgraphFast()

Member Function Documentation

◆ clone()

◆ doCall()

◆ doWorkHelper()

◆ parCall()

◆ planarize()

◆ runs() [1/2]

◆ runs() [2/2]

◆ seqCall()

Member Data Documentation

◆ m_nRuns

Open
Graph Drawing
Framework