Computes planar separators according to Har-Peled. More...
#include <ogdf/graphalg/SeparatorHarPeled.h>
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 > ®ion, 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 > ®ion, 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 > ®ion, const Cycle &cycle, const Ring &inner, const Ring &outer, bool inside) const |
Builds the region R1 or R2. More... | |
bool | findRegions (List< node > ®ion, 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 > ®ionBorder, 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 > ®ionBorder, List< node > ®ion) 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 > ®ionBorder, List< node > ®ion) 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... | |
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.
|
inline |
Constructor.
Definition at line 96 of file SeparatorHarPeled.h.
|
protected |
Constructs the array of concentric rings of nodes formed by the (potentially partial) borders of the regions found by findFaceLevels.
cycle | the 2/3-separator found in the initial phase |
|
protected |
Builds the region K.
region | the list of nodes that form the border of the region |
cycle | the separator cycle |
inner | the inner ring |
outer | the outer ring |
|
protected |
Creates the dual of the graph to help find a separator edge.
Dual | the graph that should contain the dual |
oldEdge | array that maps dual edges back to original edges |
|
overrideprotectedvirtual |
Entry point for the core of the algorithm.
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 |
Implements ogdf::PlanarSeparatorModule.
|
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.
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 |
|
protected |
Finds i0, the first step of the first "ladder" of rings that is not larger than n / delta nodes.
delta | the delta-parameter, ceil(sqrt( n / 2 )) |
|
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.
root | the root node of the tree |
|
protected |
Builds the region R1 or R2.
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) |
|
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.
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) |
|
protected |
Finds a non-tree edge that, together with the tree, forms a (possibly too large) 2/3-separator.
|
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.
n | the number of nodes of the graph |
Implements ogdf::PlanarSeparatorModule.
Definition at line 98 of file SeparatorHarPeled.h.
|
inlineoverridevirtual |
Returns the unique name of the core algorithm, to be combined with postprocessors later.
Override this in inheriting methods.
Implements ogdf::PlanarSeparatorModule.
Definition at line 100 of file SeparatorHarPeled.h.
|
protectedvirtual |
Constructs the BFSTreeHP from a random node.
|
overrideprotectedvirtual |
Resets all fields, clears lists and re-initializes arrays to enable reuse of the module.
Reimplemented from ogdf::PlanarSeparatorModule.
|
protected |
Checks whether the inside [outside] of the region defined by regionBorder is greater or smaller than 1/3 f.
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 |
|
protected |
|
protected |
Used in region construction: Walks along a Ring and stores nodes and edges of the section.
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 |
|
protected |
Used in region construction: Walks along the 2/3-separator from startNode
to endNode
.
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 |
|
friend |
We will need a set of nested rings of nodes, see below.
Definition at line 90 of file SeparatorHarPeled.h.
|
private |
Definition at line 266 of file SeparatorHarPeled.h.
|
private |
Definition at line 262 of file SeparatorHarPeled.h.
Definition at line 267 of file SeparatorHarPeled.h.
|
private |
Definition at line 265 of file SeparatorHarPeled.h.
|
private |
Definition at line 275 of file SeparatorHarPeled.h.
Definition at line 279 of file SeparatorHarPeled.h.
|
private |
Definition at line 263 of file SeparatorHarPeled.h.
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.
Definition at line 274 of file SeparatorHarPeled.h.
Definition at line 277 of file SeparatorHarPeled.h.
|
protected |
A special tree that can be reconstructed, see above.
Definition at line 122 of file SeparatorHarPeled.h.