ogdf::PlanarSubgraphCactus< TCost > Class Template Reference

Maximum planar subgraph approximation algorithm by Calinescu et al. More...

#include <ogdf/planarity/PlanarSubgraphCactus.h>

Inheritance diagram for ogdf::PlanarSubgraphCactus< TCost >:

Public Member Functions
	PlanarSubgraphCactus ()
virtual PlanarSubgraphCactus *	clone () const override
	Returns a new instance of the planarization module with the same settings.
Public Member Functions inherited from ogdf::PlanarSubgraphTriangles< TCost >
	PlanarSubgraphTriangles (bool onlyTriangles=false)
	Creates a planarization module based on triangle or diamond matching.
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.

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 Member Functions inherited from ogdf::PlanarSubgraphTriangles< TCost >
virtual Module::ReturnType	doCall (const Graph &graph, const List< edge > &, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar=false) override
	Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
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::PlanarSubgraphCactus< TCost >

Maximum planar subgraph approximation algorithm by Calinescu et al.

The algorithm has an approximation factor of 7/18. Setting preferred edges is not supported. Weighted edges are heuristically respected but there is no approximation guarantee in the weighted case.

Definition at line 47 of file PlanarSubgraphCactus.h.

Constructor & Destructor Documentation

PlanarSubgraphCactus()

template<typename TCost >

ogdf::PlanarSubgraphCactus< TCost >::PlanarSubgraphCactus ( )

inline

Definition at line 49 of file PlanarSubgraphCactus.h.

Member Function Documentation

clone()

template<typename TCost >

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

inlineoverridevirtual

Returns a new instance of the planarization module with the same settings.

Reimplemented from ogdf::PlanarSubgraphTriangles< TCost >.

Definition at line 51 of file PlanarSubgraphCactus.h.

---

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

• include/ogdf/planarity/PlanarSubgraphCactus.h