Computes planar separators according to Lipton and Tarjan 1979. More...

#include <ogdf/graphalg/SeparatorLiptonTarjan.h>

Inheritance diagram for ogdf::SeparatorLiptonTarjan:

Public Member Functions
	SeparatorLiptonTarjan (bool useTriangulatingBFS=false, unsigned int treeHeightIt=0)
	Constructor.

virtual double	getMaxSeparatorSize (int n) const override
	Provides the maximal separator size that this algorithm guarantees as a function of the number of nodes of the graph, or a negative value if the guarantee cannot be expressed through such a function.

Public Member Functions inherited from ogdf::PlanarSeparatorModule
	PlanarSeparatorModule ()

virtual	~PlanarSeparatorModule ()

void	addPostProcessor (Postprocessor &post)
	Adds a postprocessor to this separator, which will always be applied.

void	clearPostProcessors ()
	Deletes all appended postprocessors from this separator.

std::string	getExitPoint () const
	Returns the exitPoint, i.e.

virtual std::string	getName () const
	Returns the full name of this algorithm.

virtual bool	separate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second, bool checkPreconditions=true) final
	Separates a planar graph.

virtual bool	separate (const Graph &G, NodeArray< short > &assignments, bool checkPreconditions=true) final
	Separates a planar graph.

void	setStartIndex (int index)

Protected Member Functions
edge	chooseEdge () const
	Chooses the initial edge for the very first cycle.

virtual bool	doSeparate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) override
	Core of the specific separation algorithm - override this in inheriting classes.

void	fillLists (List< node > &separator, List< node > &first, List< node > &second) const
	Fills the lists with the cycle / inside / outside once the cycle is ready.

virtual std::string	getSpecificName () const override
	Returns the unique name of the core algorithm, to be combined with postprocessors later.

virtual void	makeTree ()
	Creates the BFS tree used by the algorithm.

Protected Member Functions inherited from ogdf::PlanarSeparatorModule
bool	cleanup (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)
	Performs built-in post-processing: For small instances, it can happen that all nodes are assigned to the separator, while both components are empty, which can be fixed by moving half of the nodes to the first list.

node	getStartNode (const Graph &G) const
	Selects the starting node for the BFS.

bool	postProcess (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)
	Apply all postprocessors.

virtual void	reset ()
	Reset everything to enable reuse of the module.

bool	separateComponents (GraphCopy &G, List< node > &separator, List< node > &first, List< node > &second, bool skip=false) const
	Checks if the graph consists of multiple connected components, takes necessary steps for fixing that, returns true if this already solved the graph, false if the core algorithm still needs to run.

bool	setup (const Graph &G, List< node > &separator, List< node > &first, List< node > &second, bool checkPreconditions=true)
	Performs some initial setup to ensure that all preconditions hold and takes trivial steps to separate the graph.

Protected Attributes
std::shared_ptr< BFSTreeClassical >	tree

unsigned int	treeHeightIterations

bool	useTriBFS

Protected Attributes inherited from ogdf::PlanarSeparatorModule
std::string	exitPoint

std::shared_ptr< GraphCopy >	graph

std::vector< Postprocessor * >	postProcessors

int	startNodeIndex = -1

Friends
class	Cycle

Detailed Description

Computes planar separators according to Lipton and Tarjan 1979.

Computes separators according to the paper "A Separator Theorem for Planar Graphs" by Richard J. Lipton and Robert Endre Tarjan, published in the SIAM Journal on Applied Mathematics, 1979.

Definition at line 46 of file SeparatorLiptonTarjan.h.

Constructor & Destructor Documentation

◆ SeparatorLiptonTarjan()

ogdf::SeparatorLiptonTarjan::SeparatorLiptonTarjan	(	bool	useTriangulatingBFS = `false`,
		unsigned int	treeHeightIt = `0`
	)

inline

Constructor.

Parameters

useTriangulatingBFS	whether to use triangulating BFS or not
treeHeightIt	how many iterations of tree height maximization to perform

Definition at line 56 of file SeparatorLiptonTarjan.h.

Member Function Documentation

◆ chooseEdge()

edge ogdf::SeparatorLiptonTarjan::chooseEdge ( ) const

protected

Chooses the initial edge for the very first cycle.

Returns: a random edge

◆ doSeparate()

virtual bool ogdf::SeparatorLiptonTarjan::doSeparate	(	const Graph &	G,
		List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)

overrideprotectedvirtual

Core of the specific separation algorithm - override this in inheriting classes.

Precondition: G is planar, simple-undirected, connected and represents a Combinatorial Embedding = is planarly embedded already.

Parameters

G	the graph to be separated
separator	the separator nodes
first	the first component
second	the second component

Returns: true on success

Implements ogdf::PlanarSeparatorModule.

Reimplemented in ogdf::SeparatorDual.

◆ fillLists()

void ogdf::SeparatorLiptonTarjan::fillLists	(	List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)		const

protected

Fills the lists with the cycle / inside / outside once the cycle is ready.

Parameters

separator	the separator nodes
first	the first component
second	the second component

◆ getMaxSeparatorSize()

virtual double ogdf::SeparatorLiptonTarjan::getMaxSeparatorSize ( int n ) const

inlineoverridevirtual

Provides the maximal separator size that this algorithm guarantees as a function of the number of nodes of the graph, or a negative value if the guarantee cannot be expressed through such a function.

See e.g. SeparatorHarPeled or SeparatorDualFC for examples.

Parameters

n	the number of nodes of the graph

Returns: the maximal separator size

Implements ogdf::PlanarSeparatorModule.

Reimplemented in ogdf::SeparatorDual.

Definition at line 59 of file SeparatorLiptonTarjan.h.

◆ getSpecificName()

virtual std::string ogdf::SeparatorLiptonTarjan::getSpecificName ( ) const

inlineoverrideprotectedvirtual

Returns the unique name of the core algorithm, to be combined with postprocessors later.

Override this in inheriting methods.

Returns: the specific name as a string

Implements ogdf::PlanarSeparatorModule.

Reimplemented in ogdf::SeparatorDual.

Definition at line 71 of file SeparatorLiptonTarjan.h.

◆ makeTree()

virtual void ogdf::SeparatorLiptonTarjan::makeTree ( )

protectedvirtual

Creates the BFS tree used by the algorithm.

Reimplemented in ogdf::SeparatorDual.

Friends And Related Symbol Documentation

◆ Cycle

friend class Cycle

friend

Definition at line 47 of file SeparatorLiptonTarjan.h.

Member Data Documentation

◆ tree

std::shared_ptr<BFSTreeClassical> ogdf::SeparatorLiptonTarjan::tree

protected

Definition at line 69 of file SeparatorLiptonTarjan.h.

◆ treeHeightIterations

unsigned int ogdf::SeparatorLiptonTarjan::treeHeightIterations

protected

Definition at line 64 of file SeparatorLiptonTarjan.h.

◆ useTriBFS

bool ogdf::SeparatorLiptonTarjan::useTriBFS

protected

Definition at line 63 of file SeparatorLiptonTarjan.h.

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

include/ogdf/graphalg/SeparatorLiptonTarjan.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SeparatorLiptonTarjan()

Member Function Documentation

◆ chooseEdge()

◆ doSeparate()

◆ fillLists()

◆ getMaxSeparatorSize()

◆ getSpecificName()

◆ makeTree()

Friends And Related Symbol Documentation

◆ Cycle

Member Data Documentation

◆ tree

◆ treeHeightIterations

◆ useTriBFS

Open
Graph Drawing
Framework