Exact computation of a maximum planar subgraph. More...

#include <ogdf/planarity/MaximumPlanarSubgraph.h>

Inheritance diagram for ogdf::MaximumPlanarSubgraph< TCost >:

Public Member Functions
	MaximumPlanarSubgraph ()

virtual	~MaximumPlanarSubgraph ()

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

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

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

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

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

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

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

ReturnType	callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges)
	Makes `G` planar by deleting edges. 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...

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

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

Timeouter &	operator= (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 Module::ReturnType	doCall (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar) override
	Computes the set of edges `delEdges` which have to be deleted to obtain the planar subgraph. More...

Private Member Functions
Module::ReturnType	callWithDouble (MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< double > *pCost, List< edge > &delEdges)

template<typename U = TCost>
Module::ReturnType	callWithDouble (MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< U > *pCost, List< edge > &delEdges)

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

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

Detailed Description

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

Exact computation of a maximum planar subgraph.

Definition at line 56 of file MaximumPlanarSubgraph.h.

Constructor & Destructor Documentation

◆ MaximumPlanarSubgraph()

template<typename TCost >

ogdf::MaximumPlanarSubgraph< TCost >::MaximumPlanarSubgraph ( )

inline

Definition at line 59 of file MaximumPlanarSubgraph.h.

◆ ~MaximumPlanarSubgraph()

template<typename TCost >

virtual ogdf::MaximumPlanarSubgraph< TCost >::~MaximumPlanarSubgraph ( )

inlinevirtual

Definition at line 62 of file MaximumPlanarSubgraph.h.

Member Function Documentation

◆ callWithDouble() [1/2]

template<typename TCost >

Module::ReturnType ogdf::MaximumPlanarSubgraph< TCost >::callWithDouble	(	MaximumCPlanarSubgraph &	mc,
		const Graph &	G,
		const EdgeArray< double > *	pCost,
		List< edge > &	delEdges
	)

inlineprivate

Definition at line 199 of file MaximumPlanarSubgraph.h.

◆ callWithDouble() [2/2]

template<typename TCost >

template<typename U = TCost>

Module::ReturnType ogdf::MaximumPlanarSubgraph< TCost >::callWithDouble	(	MaximumCPlanarSubgraph &	mc,
		const Graph &	G,
		const EdgeArray< U > *	pCost,
		List< edge > &	delEdges
	)

inlineprivate

Definition at line 186 of file MaximumPlanarSubgraph.h.

◆ clone()

template<typename TCost >

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

inlineoverridevirtual

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

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 64 of file MaximumPlanarSubgraph.h.

◆ doCall()

template<typename TCost >

virtual Module::ReturnType ogdf::MaximumPlanarSubgraph< TCost >::doCall	(	const Graph &	G,
		const List< edge > &	preferredEdges,
		List< edge > &	delEdges,
		const EdgeArray< TCost > *	pCost,
		bool	preferredImplyPlanar
	)

inlineoverrideprotectedvirtual

Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.

This is the actual algorithm call and needs to be implemented by derived classes.

Parameters

G	is the input graph.
preferredEdges	are edges that should be contained in the planar subgraph.
delEdges	is the set of edges that need to be deleted to obtain the planar subgraph.
pCost	is apointer to an edge array containing the edge costs; this pointer can be 0 if no costs are given (all edges have cost 1).
preferredImplyPlanar	indicates that the edges `preferredEdges` induce a planar graph.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 74 of file MaximumPlanarSubgraph.h.

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

include/ogdf/planarity/MaximumPlanarSubgraph.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

◆ MaximumPlanarSubgraph()

◆ ~MaximumPlanarSubgraph()

Member Function Documentation

◆ callWithDouble() [1/2]

◆ callWithDouble() [2/2]

◆ clone()

◆ doCall()

Open
Graph Drawing
Framework

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