Naive maximal planar subgraph approach that extends a configurable non-maximal subgraph heuristic. More...

#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>

Inheritance diagram for ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >:

Public Member Functions
	MaximalPlanarSubgraphSimple ()
	Constructor. More...

	MaximalPlanarSubgraphSimple (PlanarSubgraphModule< TCost > &heuristic)
	Constructor with user given heuristic that is executed before extending the solution to maximality. More...

virtual	~MaximalPlanarSubgraphSimple ()
	Desctructor. More...

virtual MaximalPlanarSubgraphSimple *	clone () const override
	Clone method. 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 &graph, 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 Attributes
bool	m_deleteHeuristic
	flag to store we have to delete a self created heuristic More...

PlanarSubgraphModule< TCost > &	m_heuristic
	user given heuristic More...

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::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >

Naive maximal planar subgraph approach that extends a configurable non-maximal subgraph heuristic.

A (possibly non-maximal) planar subgraph is first computed by the set heuristic (default: ogdf::PlanarSubgraphEmpty). Secondly, we iterate over all non-inserted edges performing one planarity test each. Each edge is inserted if planarity can be maintained and discarded otherwise.

Definition at line 67 of file MaximalPlanarSubgraphSimple.h.

Constructor & Destructor Documentation

◆ MaximalPlanarSubgraphSimple() [1/2]

template<typename TCost >

ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::MaximalPlanarSubgraphSimple ( )

inline

Constructor.

Definition at line 71 of file MaximalPlanarSubgraphSimple.h.

◆ MaximalPlanarSubgraphSimple() [2/2]

template<typename TCost >

ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::MaximalPlanarSubgraphSimple ( PlanarSubgraphModule< TCost > & heuristic )

inlineexplicit

Constructor with user given heuristic that is executed before extending the solution to maximality.

Parameters

heuristic

Definition at line 78 of file MaximalPlanarSubgraphSimple.h.

◆ ~MaximalPlanarSubgraphSimple()

template<typename TCost >

virtual ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::~MaximalPlanarSubgraphSimple ( )

inlinevirtual

Desctructor.

Definition at line 82 of file MaximalPlanarSubgraphSimple.h.

Member Function Documentation

◆ clone()

template<typename TCost >

virtual MaximalPlanarSubgraphSimple* ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::clone ( ) const

inlineoverridevirtual

Clone method.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 89 of file MaximalPlanarSubgraphSimple.h.

◆ doCall()

template<typename TCost >

virtual Module::ReturnType ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::doCall	(	const Graph &	graph,
		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.

Parameters

graph	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 106 of file MaximalPlanarSubgraphSimple.h.

Member Data Documentation

◆ m_deleteHeuristic

template<typename TCost >

bool ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::m_deleteHeuristic

private

flag to store we have to delete a self created heuristic

Definition at line 138 of file MaximalPlanarSubgraphSimple.h.

◆ m_heuristic

template<typename TCost >

PlanarSubgraphModule<TCost>& ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >::m_heuristic

private

user given heuristic

Definition at line 137 of file MaximalPlanarSubgraphSimple.h.

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

include/ogdf/planarity/MaximalPlanarSubgraphSimple.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<typename TCost> class ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >

Constructor & Destructor Documentation

◆ MaximalPlanarSubgraphSimple() [1/2]

◆ MaximalPlanarSubgraphSimple() [2/2]

◆ ~MaximalPlanarSubgraphSimple()

Member Function Documentation

◆ clone()

◆ doCall()

Member Data Documentation

◆ m_deleteHeuristic

◆ m_heuristic

Open
Graph Drawing
Framework

template<typename TCost>
class ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >