Maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test. More...

#include <ogdf/planarity/PlanarSubgraphBoyerMyrvold.h>

Inheritance diagram for ogdf::PlanarSubgraphBoyerMyrvold:

Public Member Functions
	PlanarSubgraphBoyerMyrvold (int runs=1, double randomness=0)
	Creates a new Boyer-Myrvold subgraph module.

	~PlanarSubgraphBoyerMyrvold ()

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

void	seed (std::minstd_rand rand)
	Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator.

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

ReturnType	call (const Graph &G, const EdgeArray< int > &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< int > &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 ReturnType	doCall (const Graph &graph, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< int > *pCost, bool preferedImplyPlanar) override
	Constructs a planar subgraph according to the options supplied to the constructor.

bool	isRemoved (const GraphCopy &copy, const edge e)
	Returns true iff this edge could not be embedded.

Private Attributes
BoothLueker	m_planModule

std::minstd_rand	m_rand

double	m_randomness

int	m_runs

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

Maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test.

Computes a (possibly non-maximal) planar subgraph using the ogdf::BoyerMyrvold planarity test. Runs in linear time.

Definition at line 55 of file PlanarSubgraphBoyerMyrvold.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphBoyerMyrvold()

ogdf::PlanarSubgraphBoyerMyrvold::PlanarSubgraphBoyerMyrvold	(	int	runs = `1`,
		double	randomness = `0`
	)

inlineexplicit

Creates a new Boyer-Myrvold subgraph module.

Parameters

runs	The number of times to start the algorithm, the greatest found subgraph is returned
randomness	If randomness equals 1, each edge is chosen with the same probability. A randomness of zero chooses each edge according to its cost. Any value between 0 and 1 is allowed and will result in a specific random influence. When performing multiple runs, a randomness greater zero should be chosen.

Definition at line 72 of file PlanarSubgraphBoyerMyrvold.h.

◆ ~PlanarSubgraphBoyerMyrvold()

ogdf::PlanarSubgraphBoyerMyrvold::~PlanarSubgraphBoyerMyrvold ( )

inline

Definition at line 75 of file PlanarSubgraphBoyerMyrvold.h.

Member Function Documentation

◆ clone()

virtual PlanarSubgraphBoyerMyrvold * ogdf::PlanarSubgraphBoyerMyrvold::clone ( ) const

inlineoverridevirtual

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

Implements ogdf::PlanarSubgraphModule< int >.

Definition at line 77 of file PlanarSubgraphBoyerMyrvold.h.

◆ doCall()

virtual ReturnType ogdf::PlanarSubgraphBoyerMyrvold::doCall	(	const Graph &	graph,
		const List< edge > &	preferedEdges,
		List< edge > &	delEdges,
		const EdgeArray< int > *	pCost,
		bool	preferedImplyPlanar
	)

overrideprotectedvirtual

Constructs a planar subgraph according to the options supplied to the constructor.

Parameters

graph	the Graph to be planarized
preferedEdges	ignored
delEdges	will contain the list of edges that can be deleted to achieve planarity
pCost	the costs for removing each edge
preferedImplyPlanar	ignored

Implements ogdf::PlanarSubgraphModule< int >.

◆ isRemoved()

bool ogdf::PlanarSubgraphBoyerMyrvold::isRemoved	(	const GraphCopy &	copy,
		const edge	e
	)

inlineprotected

Returns true iff this edge could not be embedded.

Definition at line 102 of file PlanarSubgraphBoyerMyrvold.h.

◆ seed()

void ogdf::PlanarSubgraphBoyerMyrvold::seed ( std::minstd_rand rand )

inline

Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator.

Definition at line 84 of file PlanarSubgraphBoyerMyrvold.h.