ogdf::BoothLueker Class Reference

Booth-Lueker planarity test. More...

#include <ogdf/planarity/BoothLueker.h>

Inheritance diagram for ogdf::BoothLueker:

Public Member Functions
	BoothLueker ()
	~BoothLueker ()
virtual bool	isPlanar (const Graph &G) override
	Returns true, if G is planar, false otherwise.
virtual bool	isPlanarDestructive (Graph &G) override
	Returns true, if G is planar, false otherwise.
virtual bool	planarEmbed (Graph &G) override
	Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
virtual bool	planarEmbedPlanarGraph (Graph &G) override
	Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
Public Member Functions inherited from ogdf::PlanarityModule
	PlanarityModule ()
virtual	~PlanarityModule ()

Private Member Functions
bool	doEmbed (Graph &G, NodeArray< int > &numbering, EdgeArray< edge > &backTableEdges, EdgeArray< edge > &forwardTableEdges)
	Performs a planarity test on a biconnected component of G and embedds it planar.
bool	doTest (Graph &G, NodeArray< int > &numbering)
	Performs a planarity test on a biconnected component of G.
void	entireEmbed (Graph &G, NodeArray< SListPure< adjEntry > > &entireEmbedding, NodeArray< SListIterator< adjEntry > > &adjMarker, NodeArray< bool > &mark, node v)
bool	preparation (Graph &G, bool embed)
	Prepares the planarity test and the planar embedding.
void	prepareParallelEdges (Graph &G)

Private Attributes
EdgeArray< bool >	m_isParallel
int	m_parallelCount
EdgeArray< ListPure< edge > >	m_parallelEdges

Detailed Description

Booth-Lueker planarity test.

This class implements the linear-time planarity test proposed by Booth and Luecker, based on PQ-trees.
This class is deprecated! You will usually want to use the more modern/faster/versatile linear-time planarity test by Boyer and Myrvold instead, implemented in the class BoyerMyrvold. Generally, it is suggested to use the direct function calls isPlanar and planarEmbed in extended_graph_alg.h (which in turn use BoyerMyrvold).

Definition at line 51 of file BoothLueker.h.

Constructor & Destructor Documentation

BoothLueker()

ogdf::BoothLueker::BoothLueker ( )

inline

Definition at line 53 of file BoothLueker.h.

~BoothLueker()

ogdf::BoothLueker::~BoothLueker ( )

inline

Definition at line 55 of file BoothLueker.h.

Member Function Documentation

doEmbed()

bool ogdf::BoothLueker::doEmbed ( Graph &  G, NodeArray< int > &  numbering, EdgeArray< edge > &  backTableEdges, EdgeArray< edge > &  forwardTableEdges  )

private

Performs a planarity test on a biconnected component of G and embedds it planar.

numbering contains an st-numbering of the component.

doTest()

bool ogdf::BoothLueker::doTest ( Graph &  G, NodeArray< int > &  numbering  )

private

Performs a planarity test on a biconnected component of G.

numbering contains an st-numbering of the component.

entireEmbed()

void ogdf::BoothLueker::entireEmbed ( Graph &  G, NodeArray< SListPure< adjEntry > > &  entireEmbedding, NodeArray< SListIterator< adjEntry > > &  adjMarker, NodeArray< bool > &  mark, node  v  )

private

isPlanar()

virtual bool ogdf::BoothLueker::isPlanar ( const Graph &  G )

overridevirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarityModule.

isPlanarDestructive()

virtual bool ogdf::BoothLueker::isPlanarDestructive ( Graph &  G )

overridevirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarityModule.

planarEmbed()

virtual bool ogdf::BoothLueker::planarEmbed ( Graph &  G )

inlineoverridevirtual

Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.

Implements ogdf::PlanarityModule.

Definition at line 64 of file BoothLueker.h.

planarEmbedPlanarGraph()

virtual bool ogdf::BoothLueker::planarEmbedPlanarGraph ( Graph &  G )

inlineoverridevirtual

Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.

For BoothLueker, this procedure is exactly the same as planarEmbed. (See PlanarityModule or BoyerMyrvold for the rationale of this function's existence.

Implements ogdf::PlanarityModule.

Definition at line 71 of file BoothLueker.h.

preparation()

bool ogdf::BoothLueker::preparation ( Graph &  G, bool  embed  )

private

Prepares the planarity test and the planar embedding.

prepareParallelEdges()

void ogdf::BoothLueker::prepareParallelEdges ( Graph &  G )

private

Member Data Documentation

m_isParallel

EdgeArray<bool> ogdf::BoothLueker::m_isParallel

private

Definition at line 102 of file BoothLueker.h.

m_parallelCount

int ogdf::BoothLueker::m_parallelCount

private

Definition at line 103 of file BoothLueker.h.

m_parallelEdges

EdgeArray<ListPure<edge> > ogdf::BoothLueker::m_parallelEdges

private

Definition at line 101 of file BoothLueker.h.

---

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

• include/ogdf/planarity/BoothLueker.h