|
|||
|
|
|
|||
|
|
Specialised tree representation for Har-Peled. More...
#include <ogdf/graphalg/SeparatorHarPeled.h>
Inheritance diagram for ogdf::planar_separators::BFSTreeHP:Public Member Functions | |
| BFSTreeHP (GraphCopy &G, node rootNode) | |
| Constructor. | |
| void | calculateDescendants () |
| Calculates the number of children of each node in the tree. | |
| void | construct () |
| Builds the tree by performing BFS search. | |
| void | reconstruct (const Cycle &cycle) |
| Reconstructs the tree, rooting it at root of cycle. | |
| Public Member Functions inherited from ogdf::planar_separators::ArrayBFSTree | |
| ArrayBFSTree (GraphCopy &G, node rootNode) | |
| Constructor. | |
| adjEntry | getAdjToParent (node n) const override |
Returns the adjEntry that leads up to the parent of n. | |
| List< node > | getChildrenOfNode (node n) const override |
| Returns all (immediate) children of a node. | |
| int | getDescendantsOfNode (node n) const override |
| Returns the total number of children, grandchildren etc. | |
| GraphCopy * | getGraph () const override |
| Allows access to a copy of the graph. | |
| int | getGraphSize () const override |
| Gets the number of nodes of the graph. | |
| int | getLevelOfNode (node n) const override |
| Returns the level (=depth in the tree) for a node. | |
| node | getParentOfNode (node n) const override |
Returns the node that is the parent of n in the tree. | |
| node | getRoot () const override |
| Gets the current root node of the tree. | |
| void | init () |
| Initializes all internal arrays. | |
| bool | isInTree (edge e) const override |
| Checks if an edge is a tree-edge. | |
| Public Member Functions inherited from ogdf::planar_separators::BFSTree | |
| virtual | ~BFSTree ()=default |
Additional Inherited Members | |
| Protected Attributes inherited from ogdf::planar_separators::ArrayBFSTree | |
| NodeArray< List< node > > | childrenOfNode |
| NodeArray< int > | descendantsOfNode |
| NodeArray< adjEntry > | edgeToParent |
| EdgeArray< bool > | inTree |
| NodeArray< int > | levelOfNode |
| NodeArray< bool > | mark |
| NodeArray< node > | parentOfNode |
| GraphCopy * | pGraph |
| node | root |
Specialised tree representation for Har-Peled.
Once a 2/3-separator cycle has been found, his tree can be reconstructed so that it is rooted at the root of the separator.
Definition at line 46 of file SeparatorHarPeled.h.
Constructor.
| G | the GraphCopy generated by the separator that uses this tree |
| rootNode | the initial root for the tree (usually, a random node) |
Definition at line 54 of file SeparatorHarPeled.h.
| void ogdf::planar_separators::BFSTreeHP::calculateDescendants | ( | ) |
Calculates the number of children of each node in the tree.
| void ogdf::planar_separators::BFSTreeHP::construct | ( | ) |
Builds the tree by performing BFS search.
Reconstructs the tree, rooting it at root of cycle.
| cycle | the cycle based on which we reconstruct. |
