Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
BitonicOrdering.h
Go to the documentation of this file.
1
34#pragma once
35
40
41#include <sstream>
42
43namespace ogdf {
44
46public:
47 // constructs a bitonic st ordering for G and embeds G accordingly.
48 // Requires G to be planar, embedded, biconnected
50
51#ifdef OGDF_DEBUG
54#endif
55
56 // returns the index in the st order of v
57 int getIndex(node v) const { return m_orderIndex[v]; }
58
59 // returns the i-th node in the bitonic st order
60 node getNode(int i) const { return m_indexToNode[i]; }
61
62private:
63 // used to distinguish between the three cases below
65
66 // helper function that finds the st-adjEntry in the skeleton of v_T
68
69 // the S-node case
71
72 // the P-node case
74
75 // transforms the result of the canonical ordering into two arrays,
76 // one holding the index in the temporary order for a node,
77 // the other is the reverse map. Function assumes proper init for indices and vertices
79 Array<node>& vertices) const;
80
81 // the R-node case
83
84 // label a new node
86 // the real graph node
88
89 // set the label
91
92 // and update the other map
94 }
95
96 // returns the label of a node v in the skeleton of v_T
97 int getLabel(node v_T, node v) const {
98 // the real graph node
100
101 // return the index
102 return m_orderIndex[v_G];
103 }
104
105 // mark a skeleton as temporarily flipped
107
108 // returns true if a skeleton is temporarily flipped
109 bool isFlipped(node v_T) const { return m_flipped[v_T]; }
110
111 // the graph
113
114 // the curr label index
116
117 // index in the order for all graph nodes
119
120 // maps an index to the node
122
123 // flag for keeping track of if a node has been temporary flipped
125
126 // the SPQR tree
128};
129
130}
Declaration and implementation of AdjEntryArray class.
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Declares the class LeftistOrdering...
Declaration of class StaticPlanarSPQRTree.
Class for adjacency list elements.
Definition Graph_d.h:79
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
void setFlipped(node v_T, bool flag)
int getIndex(node v) const
adjEntry getAdjST(node v_T) const
void handleParallelCase(node v_T)
node getNode(int i) const
void partitionToOrderIndices(const List< List< node > > &partitionlist, NodeArray< int > &indices, Array< node > &vertices) const
StaticPlanarSPQRTree m_tree
Array< node > m_indexToNode
bool isFlipped(node v_T) const
void handleCase(node v_T)
BitonicOrdering(Graph &G, adjEntry adj_st_edge)
NodeArray< int > m_orderIndex
void handleSerialCase(node v_T)
void handleRigidCase(node v_T)
NodeArray< bool > m_flipped
void assignLabel(node v_T, node v)
int getLabel(node v_T, node v) const
Stores additional attributes of a graph (like layout information).
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
virtual node original(node v) const =0
Returns the vertex in the original graph G that corresponds to v.
SPQR-trees of planar graphs.
Skeleton & skeleton(node v) const override
Returns the skeleton of node v.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.