Auxiliary data structure to represent Cycles in planar graphs. More...
#include <ogdf/graphalg/PlanarSeparatorModule.h>
Classes | |
class | Iterator |
Special iterator to walk over the inward-pointing edges of the cycle. More... | |
Public Member Functions | |
Cycle (BFSTree *tree, edge startEdge) | |
Constructor. More... | |
Cycle (Cycle &&other) | |
Cycle | expandCycle () |
Expands the cycle, as described by Lipton and Tarjan 1979, by examining the triangle adjacent to the current expand edge on the inside of the cycle and integrating it into the cycle. More... | |
void | fillLists (List< node > &separator, List< node > &first, List< node > &second, bool useRoot=false) |
Fills the lists of nodes, by putting all nodes on this cycle into the list of separator nodes and putting the nodes on the sides of the cycle into first and second, respectively. More... | |
bool | getClockwise () const |
Checks if the cycle is clockwise, i.e. More... | |
const List< adjEntry > & | getEdges () const |
Gets the adjEntries on the cycle. More... | |
int | getInsideCost () const |
Gets the cost on the inside of the cycle. More... | |
const List< node > & | getNodes () const |
Gets the nodes on the cycle. More... | |
int | getOutsideCost () const |
Gets the cost on the outside of the cycle. More... | |
const node & | getRoot () const |
Gives access to the root node of the cycle. More... | |
int | getSize () const |
Returns the size of the cycle = the number of nodes on the cycle. More... | |
Cycle & | operator= (Cycle &&other) |
void | print () const |
Utility method for printing the cycle to the console. More... | |
Private Member Functions | |
Cycle (BFSTree *tree, bool clockwise) | |
Constructor. More... | |
Cycle (BFSTree *tree, List< node > &nodeList, List< adjEntry > &edgeList, node root, bool clockwise) | |
Constructor. More... | |
Iterator | begin () const |
Iterators for clockwise iteration over edges on the "inside", starting and ending at currentExpandEdge. More... | |
void | collectChildrenOfNode (const node no, NodeArray< bool > &marked, List< node > &list, bool useRoot=false) const |
Recursively creates a list containing all descendants of a node. More... | |
void | computeCosts () |
Computes the costs on both sides of the cycle. More... | |
Iterator | end () const |
Cycle | expandWithoutTreeEdges (node y, const node v, const node w, const adjEntry vy, const adjEntry yw) |
Expand the cycle if none of the inner edges of the triangle is a tree edge. More... | |
void | expandWithTreeEdge (node y, node v, node w, adjEntry vy, adjEntry yw) |
Expand the Cycle when one of the inner edges of the triangle is a tree edge. More... | |
bool | findAlphaCycle (Cycle &cyc, const List< node > &pathNodes, const List< adjEntry > &pathAdjEntries, const node z, const node propRoot, const adjEntry yw, List< node > &oldNodes, List< adjEntry > &oldEdges) const |
Used during expansion without tree edges. More... | |
void | findBetaCycle (Cycle &cyc, const List< node > &pathNodes, const List< adjEntry > &pathAdjEntries, const node z, const node propRoot, const adjEntry vy, List< node > &oldNodes, List< adjEntry > &oldEdges, bool foundRootOnAlpha) const |
Used during expansion without tree edges. More... | |
std::pair< node, node > | findPathToCycle (node &y, List< node > &pathNodes, List< adjEntry > &pathAdjEntries) const |
Used during expansion without tree edges. More... | |
adjEntry | getCurrentExpandEdge () const |
Gets the current non-tree edge on the cycle, which is the one that will be used to expand the cycle further. More... | |
void | increaseCost (adjEntry adj, bool clockwise) |
Increases the cost on the inside of this cycle by following the given adjEntry and adding the cost of the node on the other end of the adjEntry. More... | |
void | init (List< node > &nodeList, List< adjEntry > &edgeList, node root) |
Initializes the cycle (used by constructors). More... | |
void | popBackEdge () |
void | popBackNode () |
Access methods for adding and removing nodes from the cycle. More... | |
void | popFrontEdge () |
void | popFrontNode () |
void | pushFrontEdge (adjEntry adj) |
Private Attributes | |
int | costClock {0} |
int | costCounter {0} |
node | cycleRoot |
List< adjEntry > | edges |
bool | isClockwise |
EdgeArray< bool > | isEdgeOnCycle |
NodeArray< bool > | isOnCycle |
List< node > | nodes |
BFSTree * | tree |
Auxiliary data structure to represent Cycles in planar graphs.
Definition at line 526 of file PlanarSeparatorModule.h.
Constructor.
Cycles are created from a tree and a non-tree edge.
tree | the tree |
startEdge | the non-tree start edge |
|
inline |
Definition at line 553 of file PlanarSeparatorModule.h.
|
private |
Constructor.
Creates a Cycle from a complete description (used by the expansion procedure)
tree | the tree to create this cycle from |
nodeList | list of nodes that should be on the cycle |
edgeList | list of adjEntries that should be on the cycle |
root | the root node of the cycle (= node with lowest level) |
clockwise | whether the cycle is clockwise or not |
|
private |
Constructor.
Creates an empty cycle (used only during the expansion procedure).
tree | the tree |
clockwise | whether the cycle is clockwise |
|
inlineprivate |
Iterators for clockwise iteration over edges on the "inside", starting and ending at currentExpandEdge.
Definition at line 780 of file PlanarSeparatorModule.h.
|
private |
Recursively creates a list containing all descendants of a node.
Collects the nodes in the original graph, not those in the copy.
no | the node whose children should be collected |
marked | holds which nodes were visited already |
list | the list containing all children |
useRoot | whether to treat the root as a normal node or not |
|
private |
Computes the costs on both sides of the cycle.
Costs are stored in the respective variables.
|
inlineprivate |
Definition at line 782 of file PlanarSeparatorModule.h.
Cycle ogdf::planar_separators::Cycle::expandCycle | ( | ) |
Expands the cycle, as described by Lipton and Tarjan 1979, by examining the triangle adjacent to the current expand edge on the inside of the cycle and integrating it into the cycle.
|
private |
Expand the cycle if none of the inner edges of the triangle is a tree edge.
This method does not change this cycle, but creates a new one (because during the process, two candidates are created and one of them is selected).
y | the tip of the triangle, inside of the cycle |
v | the starting point of the triangle-edge |
w | the end point of the triangle-edge |
vy | the edge that leads to the tip |
yw | the edge that leads away from the tip |
|
private |
Expand the Cycle when one of the inner edges of the triangle is a tree edge.
This method changes this cycle to expand it.
y | the tip of the triangle, inside of the cycle |
v | the starting point of the triangle-edge |
w | the end point of the triangle-edge |
vy | the edge that leads to the tip |
yw | the edge that leads away from the tip |
void ogdf::planar_separators::Cycle::fillLists | ( | List< node > & | separator, |
List< node > & | first, | ||
List< node > & | second, | ||
bool | useRoot = false |
||
) |
Fills the lists of nodes, by putting all nodes on this cycle into the list of separator nodes and putting the nodes on the sides of the cycle into first and second, respectively.
(Of course only once a suitable cycle is found).
separator | the separator nodes |
first | the first component |
second | the second component |
useRoot | whether to add the root node as well - sometimes, the root node is artificial and should be ignored instead of being added |
|
private |
Used during expansion without tree edges.
Finds the first cycle bounded by the path from y to z and the cycle itself.
cyc | the original cycle |
pathNodes | the nodes on the path from y to z |
pathAdjEntries | the adjEntries on the path from y to z |
z | the node z where the path meets the cycle |
propRoot | the proposed root node = the root node of the old cycle, which may be improved on |
yw | the side of the triangle |
oldNodes | nodes on old cycle |
oldEdges | edges on old cycle |
|
private |
Used during expansion without tree edges.
Finds the second cycle bounded by the path from y to z and the cycle itself.
cyc | the original cycle |
pathNodes | the nodes on the path from y to z |
pathAdjEntries | the adjEntries on the path from y to z |
z | the node z where the path meets the cycle |
propRoot | the proposed root node = the root node of the old cycle, which may be improved on |
vy | the side of the triangle |
oldNodes | nodes on old cycle |
oldEdges | edges on old cycle |
foundRootOnAlpha | whether the alpha cycle found the old root node |
|
private |
Used during expansion without tree edges.
Finds a path from y back to the cycle by following parent pointers. Returns a pair of nodes (z, r) where z = the node on the cycle in which the path beginning at y enters the cycle, and r = the node on the cycle with the shortest distance to overall root
y | the tip of the triangle |
pathNodes | the nodes on the path |
pathAdjEntries | the adjEntries on the path |
|
inline |
Checks if the cycle is clockwise, i.e.
you get the inward-pointing edges of each node on the cycle by rotating clockwise from cycle-edge to cycle-edge.
Definition at line 580 of file PlanarSeparatorModule.h.
|
private |
Gets the current non-tree edge on the cycle, which is the one that will be used to expand the cycle further.
Gets the adjEntries on the cycle.
Definition at line 594 of file PlanarSeparatorModule.h.
int ogdf::planar_separators::Cycle::getInsideCost | ( | ) | const |
Gets the cost on the inside of the cycle.
(=the number of nodes on the inside of the cycle, where the inside is defined as the larger side.)
Gets the nodes on the cycle.
Definition at line 587 of file PlanarSeparatorModule.h.
int ogdf::planar_separators::Cycle::getOutsideCost | ( | ) | const |
Gets the cost on the outside of the cycle.
(=the number of nodes on the outside of the cycle, where the inside is defined as the larger side.)
|
inline |
Gives access to the root node of the cycle.
Definition at line 601 of file PlanarSeparatorModule.h.
|
inline |
Returns the size of the cycle = the number of nodes on the cycle.
Definition at line 572 of file PlanarSeparatorModule.h.
|
private |
Increases the cost on the inside of this cycle by following the given adjEntry and adding the cost of the node on the other end of the adjEntry.
adj | the adjEntry whose cost should be added |
clockwise | whether the cost should be added to the clockwise cost |
|
private |
Initializes the cycle (used by constructors).
nodeList | the list of nodes on the cycle |
edgeList | the list of adjEntries on the cycle |
root | the root node of the cycle |
Definition at line 536 of file PlanarSeparatorModule.h.
|
private |
|
private |
Access methods for adding and removing nodes from the cycle.
|
private |
|
private |
void ogdf::planar_separators::Cycle::print | ( | ) | const |
Utility method for printing the cycle to the console.
For debugging only.
|
private |
|
private |
Definition at line 747 of file PlanarSeparatorModule.h.
|
private |
Definition at line 748 of file PlanarSeparatorModule.h.
|
private |
Definition at line 745 of file PlanarSeparatorModule.h.
Definition at line 741 of file PlanarSeparatorModule.h.
|
private |
Definition at line 749 of file PlanarSeparatorModule.h.
|
private |
Definition at line 743 of file PlanarSeparatorModule.h.
|
private |
Definition at line 742 of file PlanarSeparatorModule.h.
Definition at line 740 of file PlanarSeparatorModule.h.
|
private |
Definition at line 738 of file PlanarSeparatorModule.h.