Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first. More...

#include <ogdf/graphalg/SeparatorDualFC.h>

Inheritance diagram for ogdf::SeparatorDualFC:

Public Member Functions
	SeparatorDualFC (bool useTriBFS=false)
	Constructor. More...

virtual double	getMaxSeparatorSize (int n) const override
	Maximum separator size depends on diameter of graph, so returns -1. More...

Public Member Functions inherited from ogdf::SeparatorLiptonTarjanFC
	SeparatorLiptonTarjanFC (bool useTriBFS=false)
	Constructor. More...

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. More...

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

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

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

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

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

void	setStartIndex (int index)

Protected Member Functions
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. More...

virtual bool	findCycle (List< node > &separator, List< node > &first, List< node > &second) override
	Finds a suitable cycle by performing a DFS over the faces of the dual of the graph. More...

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

void	makeTree ()
	Builds the BFS tree. More...

Protected Member Functions inherited from ogdf::SeparatorLiptonTarjanFC
edge	chooseEdge () const
	Randomly selects the initial edge for the first cycle. More...

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. More...

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

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

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

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. More...

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. More...

Protected Attributes
std::shared_ptr< ArrayBFSTree >	tree

bool	useTriangulatingBFS

Protected Attributes inherited from ogdf::SeparatorLiptonTarjanFC
std::shared_ptr< ArrayBFSTree >	tree

bool	useTriangulatingBFS

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

std::shared_ptr< GraphCopy >	graph

std::vector< Postprocessor * >	postProcessors

int	startNodeIndex = -1

Detailed Description

Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first.

Definition at line 53 of file SeparatorDualFC.h.

Constructor & Destructor Documentation

◆ SeparatorDualFC()

ogdf::SeparatorDualFC::SeparatorDualFC ( bool useTriBFS = false )

inline

Constructor.

Parameters

useTriBFS whether to use triangulating BFS or not

Definition at line 60 of file SeparatorDualFC.h.

Member Function Documentation

◆ doSeparate()

virtual bool ogdf::SeparatorDualFC::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

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

◆ findCycle()

virtual bool ogdf::SeparatorDualFC::findCycle	(	List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)

overrideprotectedvirtual

Finds a suitable cycle by performing a DFS over the faces of the dual of the graph.

Parameters

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

Returns: true on success

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

◆ getMaxSeparatorSize()

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

inlineoverridevirtual

Maximum separator size depends on diameter of graph, so returns -1.

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

Definition at line 63 of file SeparatorDualFC.h.

◆ getSpecificName()

virtual std::string ogdf::SeparatorDualFC::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

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

Definition at line 87 of file SeparatorDualFC.h.

◆ makeTree()

void ogdf::SeparatorDualFC::makeTree ( )

protected

Builds the BFS tree.

Member Data Documentation

◆ tree

std::shared_ptr<ArrayBFSTree> ogdf::SeparatorDualFC::tree

protected

Definition at line 67 of file SeparatorDualFC.h.

◆ useTriangulatingBFS

bool ogdf::SeparatorDualFC::useTriangulatingBFS

protected

Definition at line 66 of file SeparatorDualFC.h.

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

include/ogdf/graphalg/SeparatorDualFC.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SeparatorDualFC()

Member Function Documentation

◆ doSeparate()

◆ findCycle()

◆ getMaxSeparatorSize()

◆ getSpecificName()

◆ makeTree()

Member Data Documentation

◆ tree

◆ useTriangulatingBFS

Open
Graph Drawing
Framework