Computes planar separators according to Har-Peled. More...

#include <ogdf/graphalg/SeparatorHarPeled.h>

Inheritance diagram for ogdf::SeparatorHarPeled:

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

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

virtual std::string	getSpecificName () const override
	Returns the unique name of the core algorithm, to be combined with postprocessors later. 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
void	buildRings (const Cycle &cycle)
	Constructs the array of concentric rings of nodes formed by the (potentially partial) borders of the regions found by findFaceLevels. More...

bool	constructK (List< node > &region, const Cycle &cycle, const Ring &inner, const Ring &outer) const
	Builds the region K. More...

void	createDual (Graph &Dual, EdgeArray< edge > &oldEdge) const
	Creates the dual of the graph to help find a separator edge. More...

virtual bool	doSeparate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) override
	Entry point for the core of the algorithm. More...

bool	finalize (std::string exit, const List< node > &region, List< node > &separator, List< node > &first, List< node > &second)
	Takes a list of nodes of the GraphCopy and removes their counterparts from the original graph, thereby separating the graph. More...

int	find_i0 (int delta) const
	Finds i0, the first step of the first "ladder" of rings that is not larger than n / delta nodes. More...

void	findFaceLevels (const node root)
	Performs a BFS over the faces of the embedding (more or less) to assign a level to each face and find the borders of each nested area of faces. More...

bool	findRegion (List< node > &region, const Cycle &cycle, const Ring &inner, const Ring &outer, bool inside) const
	Builds the region R1 or R2. More...

bool	findRegions (List< node > &region, const Cycle &cycle, const Ring &inner, int outerIdx) const
	Finds the regions R1 and R2 formed by the separator cycle and an inner and outer ring. More...

edge	findSeparatorEdge () const
	Finds a non-tree edge that, together with the tree, forms a (possibly too large) 2/3-separator. More...

virtual void	makeTree ()
	Constructs the BFSTreeHP from a random node. More...

virtual void	reset () override
	Resets all fields, clears lists and re-initializes arrays to enable reuse of the module. More...

bool	testRegionSize (node startNode, const EdgeArray< bool > &regionBorder, bool inside, int regionSize) const
	Checks whether the inside [outside] of the region defined by regionBorder is greater or smaller than 1/3 f. More...

void	verifyRing (const Ring &ring) const

void	walkAlongRing (const Ring &ring, bool firstSection, bool invert, EdgeArray< bool > &regionBorder, List< node > &region) const
	Used in region construction: Walks along a Ring and stores nodes and edges of the section. More...

void	walkAlongSeparator (node startNode, node endNode, EdgeArray< bool > &regionBorder, List< node > &region) const
	Used in region construction: Walks along the 2/3-separator from `startNode` to `endNode`. 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...

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< BFSTreeHP >	tree
	A special tree that can be reconstructed, see above. More...

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

std::shared_ptr< GraphCopy >	graph

std::vector< Postprocessor * >	postProcessors

int	startNodeIndex = -1

Private Attributes
EdgeArray< int >	border

ConstCombinatorialEmbedding	E

List< List< face > >	faceFrontiers

FaceArray< int >	faceLevels

NodeArray< bool >	isMultiNode

NodeArray< adjEntry >	mainSeparator

node	psi

NodeArray< List< adjEntry > >	ringIn
	hold for every node the segment of the border between levels i-1 and i that runs through this node (this has to be a list because there might be more than 2) More...

NodeArray< List< adjEntry > >	ringOut

Array< Ring, int >	rings

Friends
struct	planar_separators::Ring
	We will need a set of nested rings of nodes, see below. More...

Detailed Description

Computes planar separators according to Har-Peled.

Computes planar separators based on the algorithm presented by Sariel Har-Peled and Amir Nayyeri in "A Simple Algorithm for Computing a Cycle Separator", arXiv preprint at arXiv:1709.08122v2.

Definition at line 97 of file SeparatorHarPeled.h.

Constructor & Destructor Documentation

◆ SeparatorHarPeled()

ogdf::SeparatorHarPeled::SeparatorHarPeled ( )

inline

Constructor.

Definition at line 105 of file SeparatorHarPeled.h.

Member Function Documentation

◆ buildRings()

void ogdf::SeparatorHarPeled::buildRings ( const Cycle & cycle )

protected

Constructs the array of concentric rings of nodes formed by the (potentially partial) borders of the regions found by findFaceLevels.

Parameters

cycle the 2/3-separator found in the initial phase

◆ constructK()

bool ogdf::SeparatorHarPeled::constructK	(	List< node > &	region,
		const Cycle &	cycle,
		const Ring &	inner,
		const Ring &	outer
	)		const

protected

Builds the region K.

Parameters

region	the list of nodes that form the border of the region
cycle	the separator cycle
inner	the inner ring
outer	the outer ring

Returns: true if everything worked

◆ createDual()

void ogdf::SeparatorHarPeled::createDual	(	Graph &	Dual,
		EdgeArray< edge > &	oldEdge
	)		const

protected

Creates the dual of the graph to help find a separator edge.

Parameters

Dual	the graph that should contain the dual
oldEdge	array that maps dual edges back to original edges

◆ doSeparate()

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

overrideprotectedvirtual

Entry point for the core of the algorithm.

Parameters

G	the Graph to be separated
separator	list of nodes that will contain the separator nodes
first	list of nodes that will contain the first half of the separation
second	list of nodes that will contain the second half of the separation

Returns: whether the algorithm was successful or not

Implements ogdf::PlanarSeparatorModule.

◆ finalize()

bool ogdf::SeparatorHarPeled::finalize	(	std::string	exit,
		const List< node > &	region,
		List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)

protected

Takes a list of nodes of the GraphCopy and removes their counterparts from the original graph, thereby separating the graph.

Also sets the exitPoint.

Parameters

exit	the identifier of the exit point
region	the separator nodes in the copy
separator	separator nodes in the original graph
first	first half of the separation
second	second half of the separation

Returns: true if everything worked

◆ find_i0()

int ogdf::SeparatorHarPeled::find_i0 ( int delta ) const

protected

Finds i0, the first step of the first "ladder" of rings that is not larger than n / delta nodes.

Parameters

delta the delta-parameter, ceil(sqrt( n / 2 ))

Returns: i0, the index of the first ring of the ladder

◆ findFaceLevels()

void ogdf::SeparatorHarPeled::findFaceLevels ( const node root )

protected

Performs a BFS over the faces of the embedding (more or less) to assign a level to each face and find the borders of each nested area of faces.

Parameters

root	the root node of the tree

◆ findRegion()

bool ogdf::SeparatorHarPeled::findRegion	(	List< node > &	region,
		const Cycle &	cycle,
		const Ring &	inner,
		const Ring &	outer,
		bool	inside
	)		const

protected

Builds the region R1 or R2.

Parameters

region	the list of nodes that form the border of the region
cycle	the separator cycle
inner	the inner ring
outer	the outer ring
inside	whether we want R1 (true = the inside of the cycle) or R2 (false = the outside of the cycle)

Returns: true if it found a region that was large enough

◆ findRegions()

bool ogdf::SeparatorHarPeled::findRegions	(	List< node > &	region,
		const Cycle &	cycle,
		const Ring &	inner,
		int	outerIdx
	)		const

protected

Finds the regions R1 and R2 formed by the separator cycle and an inner and outer ring.

Fills region with the border nodes if R1 or R2 was big enough.

Parameters

region	the list that will contain the border (i.e. the resulting separator)
cycle	the 2/3-separator found in an earlier phase
inner	the inner ring of R1 / R2
outerIdx	the index of the outer ring (which is potentially degenerate)

Returns: true if a large enough region was found

◆ findSeparatorEdge()

edge ogdf::SeparatorHarPeled::findSeparatorEdge ( ) const

protected

Finds a non-tree edge that, together with the tree, forms a (possibly too large) 2/3-separator.

Returns: a non-tree edge that forms a 2/3-separator

◆ getMaxSeparatorSize()

virtual double ogdf::SeparatorHarPeled::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.

Definition at line 107 of file SeparatorHarPeled.h.

◆ getSpecificName()

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

inlineoverridevirtual

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.

Definition at line 109 of file SeparatorHarPeled.h.

◆ makeTree()

virtual void ogdf::SeparatorHarPeled::makeTree ( )

protectedvirtual

Constructs the BFSTreeHP from a random node.

◆ reset()

virtual void ogdf::SeparatorHarPeled::reset ( )

overrideprotectedvirtual

Resets all fields, clears lists and re-initializes arrays to enable reuse of the module.

Reimplemented from ogdf::PlanarSeparatorModule.

◆ testRegionSize()

bool ogdf::SeparatorHarPeled::testRegionSize	(	node	startNode,
		const EdgeArray< bool > &	regionBorder,
		bool	inside,
		int	regionSize
	)		const

protected

Checks whether the inside [outside] of the region defined by regionBorder is greater or smaller than 1/3 f.

Parameters

startNode	a node on the region border
regionBorder	an EdgeArray that is true if that edge is on the border
inside	whether we want the inside of the region or its outside
regionSize	the number of nodes on the region border

Returns: true if the region is greater than 1/3 f

◆ verifyRing()

void ogdf::SeparatorHarPeled::verifyRing ( const Ring & ring ) const

protected

◆ walkAlongRing()

void ogdf::SeparatorHarPeled::walkAlongRing	(	const Ring &	ring,
		bool	firstSection,
		bool	invert,
		EdgeArray< bool > &	regionBorder,
		List< node > &	region
	)		const

protected

Used in region construction: Walks along a Ring and stores nodes and edges of the section.

Parameters

ring	the ring to be walked
firstSection	whether we walk from in to out (true, "normal") or out to in (false)
invert	whether we invert all adjEntries of the section
regionBorder	stores whether an edge belongs to the border or not
region	contains the border nodes

◆ walkAlongSeparator()

void ogdf::SeparatorHarPeled::walkAlongSeparator	(	node	startNode,
		node	endNode,
		EdgeArray< bool > &	regionBorder,
		List< node > &	region
	)		const

protected

Used in region construction: Walks along the 2/3-separator from startNode to endNode.

Parameters

startNode	the node at which the walk starts
endNode	the node at which the walk ends
regionBorder	stores whether an edge is part of the region border
region	list to which the border nodes are added

Friends And Related Function Documentation

◆ planar_separators::Ring

friend struct planar_separators::Ring

friend

We will need a set of nested rings of nodes, see below.

Definition at line 99 of file SeparatorHarPeled.h.

Member Data Documentation

◆ border

EdgeArray<int> ogdf::SeparatorHarPeled::border

private

Definition at line 275 of file SeparatorHarPeled.h.

◆ E

ConstCombinatorialEmbedding ogdf::SeparatorHarPeled::E

private

Definition at line 271 of file SeparatorHarPeled.h.

◆ faceFrontiers

List<List<face> > ogdf::SeparatorHarPeled::faceFrontiers

private

Definition at line 276 of file SeparatorHarPeled.h.

◆ faceLevels

FaceArray<int> ogdf::SeparatorHarPeled::faceLevels

private

Definition at line 274 of file SeparatorHarPeled.h.

◆ isMultiNode

NodeArray<bool> ogdf::SeparatorHarPeled::isMultiNode

private

Definition at line 284 of file SeparatorHarPeled.h.

◆ mainSeparator

NodeArray<adjEntry> ogdf::SeparatorHarPeled::mainSeparator

private

Definition at line 288 of file SeparatorHarPeled.h.

◆ psi

node ogdf::SeparatorHarPeled::psi

private

Definition at line 272 of file SeparatorHarPeled.h.

◆ ringIn

NodeArray<List<adjEntry> > ogdf::SeparatorHarPeled::ringIn

private

hold for every node the segment of the border between levels i-1 and i that runs through this node (this has to be a list because there might be more than 2)

Definition at line 282 of file SeparatorHarPeled.h.

◆ ringOut

NodeArray<List<adjEntry> > ogdf::SeparatorHarPeled::ringOut

private

Definition at line 283 of file SeparatorHarPeled.h.

◆ rings

Array<Ring, int> ogdf::SeparatorHarPeled::rings

private

Definition at line 286 of file SeparatorHarPeled.h.

◆ tree

std::shared_ptr<BFSTreeHP> ogdf::SeparatorHarPeled::tree

protected

A special tree that can be reconstructed, see above.

Definition at line 131 of file SeparatorHarPeled.h.

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

include/ogdf/graphalg/SeparatorHarPeled.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SeparatorHarPeled()

Member Function Documentation

◆ buildRings()

◆ constructK()

◆ createDual()

◆ doSeparate()

◆ finalize()

◆ find_i0()

◆ findFaceLevels()

◆ findRegion()

◆ findRegions()

◆ findSeparatorEdge()

◆ getMaxSeparatorSize()

◆ getSpecificName()

◆ makeTree()

◆ reset()

◆ testRegionSize()

◆ verifyRing()

◆ walkAlongRing()

◆ walkAlongSeparator()

Friends And Related Function Documentation

◆ planar_separators::Ring

Member Data Documentation

◆ border

◆ E

◆ faceFrontiers

◆ faceLevels

◆ isMultiNode

◆ mainSeparator

◆ psi

◆ ringIn

◆ ringOut

◆ rings

◆ tree

Open
Graph Drawing
Framework