Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SeparatorHarPeled Class Reference

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< BFSTreeHPtree
 A special tree that can be reconstructed, see above. More...
 
- Protected Attributes inherited from ogdf::PlanarSeparatorModule
std::string exitPoint
 
std::shared_ptr< GraphCopygraph
 
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< adjEntrymainSeparator
 
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 88 of file SeparatorHarPeled.h.

Constructor & Destructor Documentation

◆ SeparatorHarPeled()

ogdf::SeparatorHarPeled::SeparatorHarPeled ( )
inline

Constructor.

Definition at line 96 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
cyclethe 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
regionthe list of nodes that form the border of the region
cyclethe separator cycle
innerthe inner ring
outerthe 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
Dualthe graph that should contain the dual
oldEdgearray 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
Gthe Graph to be separated
separatorlist of nodes that will contain the separator nodes
firstlist of nodes that will contain the first half of the separation
secondlist 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
exitthe identifier of the exit point
regionthe separator nodes in the copy
separatorseparator nodes in the original graph
firstfirst half of the separation
secondsecond 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
deltathe 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
rootthe 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
regionthe list of nodes that form the border of the region
cyclethe separator cycle
innerthe inner ring
outerthe outer ring
insidewhether 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
regionthe list that will contain the border (i.e. the resulting separator)
cyclethe 2/3-separator found in an earlier phase
innerthe inner ring of R1 / R2
outerIdxthe 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
nthe number of nodes of the graph
Returns
the maximal separator size

Implements ogdf::PlanarSeparatorModule.

Definition at line 98 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 100 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
startNodea node on the region border
regionBorderan EdgeArray that is true if that edge is on the border
insidewhether we want the inside of the region or its outside
regionSizethe 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
ringthe ring to be walked
firstSectionwhether we walk from in to out (true, "normal") or out to in (false)
invertwhether we invert all adjEntries of the section
regionBorderstores whether an edge belongs to the border or not
regioncontains 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
startNodethe node at which the walk starts
endNodethe node at which the walk ends
regionBorderstores whether an edge is part of the region border
regionlist 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 90 of file SeparatorHarPeled.h.

Member Data Documentation

◆ border

EdgeArray<int> ogdf::SeparatorHarPeled::border
private

Definition at line 266 of file SeparatorHarPeled.h.

◆ E

ConstCombinatorialEmbedding ogdf::SeparatorHarPeled::E
private

Definition at line 262 of file SeparatorHarPeled.h.

◆ faceFrontiers

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

Definition at line 267 of file SeparatorHarPeled.h.

◆ faceLevels

FaceArray<int> ogdf::SeparatorHarPeled::faceLevels
private

Definition at line 265 of file SeparatorHarPeled.h.

◆ isMultiNode

NodeArray<bool> ogdf::SeparatorHarPeled::isMultiNode
private

Definition at line 275 of file SeparatorHarPeled.h.

◆ mainSeparator

NodeArray<adjEntry> ogdf::SeparatorHarPeled::mainSeparator
private

Definition at line 279 of file SeparatorHarPeled.h.

◆ psi

node ogdf::SeparatorHarPeled::psi
private

Definition at line 263 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 273 of file SeparatorHarPeled.h.

◆ ringOut

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

Definition at line 274 of file SeparatorHarPeled.h.

◆ rings

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

Definition at line 277 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 122 of file SeparatorHarPeled.h.


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