Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::planar_separators::Cycle Class Reference

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 nodegetRoot () 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...
 
Cycleoperator= (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, nodefindPathToCycle (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< adjEntryedges
 
bool isClockwise
 
EdgeArray< bool > isEdgeOnCycle
 
NodeArray< bool > isOnCycle
 
List< nodenodes
 
BFSTreetree
 

Detailed Description

Auxiliary data structure to represent Cycles in planar graphs.

Definition at line 526 of file PlanarSeparatorModule.h.

Constructor & Destructor Documentation

◆ Cycle() [1/4]

ogdf::planar_separators::Cycle::Cycle ( BFSTree tree,
edge  startEdge 
)

Constructor.

Cycles are created from a tree and a non-tree edge.

Parameters
treethe tree
startEdgethe non-tree start edge

◆ Cycle() [2/4]

ogdf::planar_separators::Cycle::Cycle ( Cycle &&  other)
inline

Definition at line 553 of file PlanarSeparatorModule.h.

◆ Cycle() [3/4]

ogdf::planar_separators::Cycle::Cycle ( BFSTree tree,
List< node > &  nodeList,
List< adjEntry > &  edgeList,
node  root,
bool  clockwise 
)
private

Constructor.

Creates a Cycle from a complete description (used by the expansion procedure)

Parameters
treethe tree to create this cycle from
nodeListlist of nodes that should be on the cycle
edgeListlist of adjEntries that should be on the cycle
rootthe root node of the cycle (= node with lowest level)
clockwisewhether the cycle is clockwise or not

◆ Cycle() [4/4]

ogdf::planar_separators::Cycle::Cycle ( BFSTree tree,
bool  clockwise 
)
private

Constructor.

Creates an empty cycle (used only during the expansion procedure).

Parameters
treethe tree
clockwisewhether the cycle is clockwise

Member Function Documentation

◆ begin()

Iterator ogdf::planar_separators::Cycle::begin ( ) const
inlineprivate

Iterators for clockwise iteration over edges on the "inside", starting and ending at currentExpandEdge.

Definition at line 780 of file PlanarSeparatorModule.h.

◆ collectChildrenOfNode()

void ogdf::planar_separators::Cycle::collectChildrenOfNode ( const node  no,
NodeArray< bool > &  marked,
List< node > &  list,
bool  useRoot = false 
) const
private

Recursively creates a list containing all descendants of a node.

Collects the nodes in the original graph, not those in the copy.

Parameters
nothe node whose children should be collected
markedholds which nodes were visited already
listthe list containing all children
useRootwhether to treat the root as a normal node or not

◆ computeCosts()

void ogdf::planar_separators::Cycle::computeCosts ( )
private

Computes the costs on both sides of the cycle.

Costs are stored in the respective variables.

◆ end()

Iterator ogdf::planar_separators::Cycle::end ( ) const
inlineprivate

Definition at line 782 of file PlanarSeparatorModule.h.

◆ expandCycle()

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.

Returns
the new, expanded cycle

◆ expandWithoutTreeEdges()

Cycle ogdf::planar_separators::Cycle::expandWithoutTreeEdges ( node  y,
const node  v,
const node  w,
const adjEntry  vy,
const adjEntry  yw 
)
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).

Parameters
ythe tip of the triangle, inside of the cycle
vthe starting point of the triangle-edge
wthe end point of the triangle-edge
vythe edge that leads to the tip
ywthe edge that leads away from the tip
Returns
the next cycle

◆ expandWithTreeEdge()

void ogdf::planar_separators::Cycle::expandWithTreeEdge ( node  y,
node  v,
node  w,
adjEntry  vy,
adjEntry  yw 
)
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.

Parameters
ythe tip of the triangle, inside of the cycle
vthe starting point of the triangle-edge
wthe end point of the triangle-edge
vythe edge that leads to the tip
ywthe edge that leads away from the tip

◆ fillLists()

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

Parameters
separatorthe separator nodes
firstthe first component
secondthe second component
useRootwhether to add the root node as well - sometimes, the root node is artificial and should be ignored instead of being added

◆ findAlphaCycle()

bool ogdf::planar_separators::Cycle::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
private

Used during expansion without tree edges.

Finds the first cycle bounded by the path from y to z and the cycle itself.

Parameters
cycthe original cycle
pathNodesthe nodes on the path from y to z
pathAdjEntriesthe adjEntries on the path from y to z
zthe node z where the path meets the cycle
propRootthe proposed root node = the root node of the old cycle, which may be improved on
ywthe side of the triangle
oldNodesnodes on old cycle
oldEdgesedges on old cycle
Returns
whether we found the root node of the original cycle on our way from w to z

◆ findBetaCycle()

void ogdf::planar_separators::Cycle::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
private

Used during expansion without tree edges.

Finds the second cycle bounded by the path from y to z and the cycle itself.

Parameters
cycthe original cycle
pathNodesthe nodes on the path from y to z
pathAdjEntriesthe adjEntries on the path from y to z
zthe node z where the path meets the cycle
propRootthe proposed root node = the root node of the old cycle, which may be improved on
vythe side of the triangle
oldNodesnodes on old cycle
oldEdgesedges on old cycle
foundRootOnAlphawhether the alpha cycle found the old root node

◆ findPathToCycle()

std::pair<node, node> ogdf::planar_separators::Cycle::findPathToCycle ( node y,
List< node > &  pathNodes,
List< adjEntry > &  pathAdjEntries 
) const
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

Parameters
ythe tip of the triangle
pathNodesthe nodes on the path
pathAdjEntriesthe adjEntries on the path
Returns
nodes (z, r)

◆ getClockwise()

bool ogdf::planar_separators::Cycle::getClockwise ( ) const
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.

Returns
true if the cycle is clockwise

Definition at line 580 of file PlanarSeparatorModule.h.

◆ getCurrentExpandEdge()

adjEntry ogdf::planar_separators::Cycle::getCurrentExpandEdge ( ) const
private

Gets the current non-tree edge on the cycle, which is the one that will be used to expand the cycle further.

Returns
the current non-tree edge

◆ getEdges()

const List<adjEntry>& ogdf::planar_separators::Cycle::getEdges ( ) const
inline

Gets the adjEntries on the cycle.

Returns
read-only list of adjEntries

Definition at line 594 of file PlanarSeparatorModule.h.

◆ getInsideCost()

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

Returns
the inside cost

◆ getNodes()

const List<node>& ogdf::planar_separators::Cycle::getNodes ( ) const
inline

Gets the nodes on the cycle.

Returns
read-only list of nodes

Definition at line 587 of file PlanarSeparatorModule.h.

◆ getOutsideCost()

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

Returns
the inside cost

◆ getRoot()

const node& ogdf::planar_separators::Cycle::getRoot ( ) const
inline

Gives access to the root node of the cycle.

Returns
read-only access to the root node

Definition at line 601 of file PlanarSeparatorModule.h.

◆ getSize()

int ogdf::planar_separators::Cycle::getSize ( ) const
inline

Returns the size of the cycle = the number of nodes on the cycle.

Returns
the size

Definition at line 572 of file PlanarSeparatorModule.h.

◆ increaseCost()

void ogdf::planar_separators::Cycle::increaseCost ( adjEntry  adj,
bool  clockwise 
)
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.

Parameters
adjthe adjEntry whose cost should be added
clockwisewhether the cost should be added to the clockwise cost

◆ init()

void ogdf::planar_separators::Cycle::init ( List< node > &  nodeList,
List< adjEntry > &  edgeList,
node  root 
)
private

Initializes the cycle (used by constructors).

Parameters
nodeListthe list of nodes on the cycle
edgeListthe list of adjEntries on the cycle
rootthe root node of the cycle

◆ operator=()

Cycle& ogdf::planar_separators::Cycle::operator= ( Cycle &&  other)
inline

Definition at line 536 of file PlanarSeparatorModule.h.

◆ popBackEdge()

void ogdf::planar_separators::Cycle::popBackEdge ( )
private

◆ popBackNode()

void ogdf::planar_separators::Cycle::popBackNode ( )
private

Access methods for adding and removing nodes from the cycle.

◆ popFrontEdge()

void ogdf::planar_separators::Cycle::popFrontEdge ( )
private

◆ popFrontNode()

void ogdf::planar_separators::Cycle::popFrontNode ( )
private

◆ print()

void ogdf::planar_separators::Cycle::print ( ) const

Utility method for printing the cycle to the console.

For debugging only.

◆ pushFrontEdge()

void ogdf::planar_separators::Cycle::pushFrontEdge ( adjEntry  adj)
private

Member Data Documentation

◆ costClock

int ogdf::planar_separators::Cycle::costClock {0}
private

Definition at line 747 of file PlanarSeparatorModule.h.

◆ costCounter

int ogdf::planar_separators::Cycle::costCounter {0}
private

Definition at line 748 of file PlanarSeparatorModule.h.

◆ cycleRoot

node ogdf::planar_separators::Cycle::cycleRoot
private

Definition at line 745 of file PlanarSeparatorModule.h.

◆ edges

List<adjEntry> ogdf::planar_separators::Cycle::edges
private

Definition at line 741 of file PlanarSeparatorModule.h.

◆ isClockwise

bool ogdf::planar_separators::Cycle::isClockwise
private

Definition at line 749 of file PlanarSeparatorModule.h.

◆ isEdgeOnCycle

EdgeArray<bool> ogdf::planar_separators::Cycle::isEdgeOnCycle
private

Definition at line 743 of file PlanarSeparatorModule.h.

◆ isOnCycle

NodeArray<bool> ogdf::planar_separators::Cycle::isOnCycle
private

Definition at line 742 of file PlanarSeparatorModule.h.

◆ nodes

List<node> ogdf::planar_separators::Cycle::nodes
private

Definition at line 740 of file PlanarSeparatorModule.h.

◆ tree

BFSTree* ogdf::planar_separators::Cycle::tree
private

Definition at line 738 of file PlanarSeparatorModule.h.


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