Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
LeftistOrdering.h
Go to the documentation of this file.
1
34#pragma once
35
38
39namespace ogdf {
40
41// context class for the leftist canonical ordering algorithm
43protected:
44 // struct for a candidate aka belt item
45 struct Candidate {
47
48 // the edges in the belt item
50
51 // a possible stopper of the candidate
53 };
54
55public:
56 // computes the leftist canonical order. Requires that G is simple, triconnected and embedded.
57 // adj_v1n is the adjEntry at v_1 looking towards v_n, the outerface is choosen such that v_2 is the cyclic pred
58 // of v_n. the result is saved in result, a list of list of nodes, first set is v_1, v_2, last one is v_n.
59 bool call(const Graph& G, adjEntry adj_v1n, List<List<node>>& result);
60
61private:
62 // the leftmost feasible candidate function from the paper
64
65 // this is used to check a candidate for a singleton copy
66 bool isSingletonWith(const Candidate& c, node v) const;
67
68 // update belt function from the paper
69 void updateBelt();
70
71 // belt extension function from the paper
73
74 // returns true if v is forbidde
75 bool forbidden(node v) const {
76 // too many cut faces?
77 return m_cutFaces[v] > m_cutEdges[v] + 1;
78 }
79
80 // returns true if v is singular
81 bool singular(node v) const {
82 // not more cutfaces then cut edges plus one ?
83 return m_cutFaces[v] > 2 && m_cutFaces[v] == m_cutEdges[v] + 1;
84 }
85
86 // the belt
88
89 // the curr candidate in the belt
91
92 // number of cutfaces incident to a vertex
94
95 // number of cutedges incident to a vertex
97
98 // flag for marking directed edges
100
101public:
102 // this is a custom class to have a more convienent way to access a canonical ordering
103 // used somewhere
105 public:
107
109
110 void buildFromResult(const Graph& G, const List<List<node>>& lco);
111
112 // returns the adjEntry to the left node in G_k-1
113 adjEntry left(int k) const {
114 if (m_ears[k][0]) {
115 return m_ears[k][0]->twin();
116 } else {
117 return nullptr;
118 }
119 }
120
121 // returns the adjEntry to the left node in G_k-1
122 adjEntry right(int k) const { return m_ears[k][m_ears[k].size() - 1]; }
123
124 // returns the edge from v_i to v_i+1 in the k-th partition
125 adjEntry getChainAdj(int k, int i) const { return m_ears[k][i + 1]; }
126
127 adjEntry getPathAdj(int k, int i) const { return m_ears[k][i]; }
128
129 node getNode(int k, int i) const { return m_ears[k][i + 1]->theNode(); }
130
131 // returns the number of all partitions
132 int numPartitions() const { return m_ears.size(); }
133
134 // returns the number of nodes in partition k
135 int numNodes(int k) const { return m_ears[k].size() - 1; }
136
137 int pathLength(int k) const { return m_ears[k].size(); }
138
139 bool isSingleton(int k) const { return numNodes(k) == 1; }
140
141 private:
142 // keeps for every partition the path from left, v_1, ... v_k, right
144 };
145
146 bool call(const Graph& G, adjEntry adj_v1n, Partitioning& partition) {
147 // the simple result
148 List<List<node>> result;
149 // compute it
150 if (!call(G, adj_v1n, result)) {
151 return false;
152 }
153
154 // generate the comfortable partitioning
155 partition.buildFromResult(G, result);
156
157 // success hopefully..
158 return true;
159 }
160};
161
162}
Declaration and implementation of AdjEntryArray class.
Declares the base class ShellingOrderModule for modules that compute a shelling order of a graph.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition Graph_d.h:109
Dynamic arrays indexed with adjacency entries.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
void buildFromResult(const Graph &G, const List< List< node > > &lco)
adjEntry getPathAdj(int k, int i) const
Partitioning(const Graph &G, const List< List< node > > &lco)
adjEntry getChainAdj(int k, int i) const
Array< Array< adjEntry > > m_ears
bool call(const Graph &G, adjEntry adj_v1n, List< List< node > > &result)
bool call(const Graph &G, adjEntry adj_v1n, Partitioning &partition)
NodeArray< int > m_cutFaces
List< Candidate >::iterator m_currCandidateIt
AdjEntryArray< bool > m_marked
void beltExtension(List< Candidate > &extension)
NodeArray< int > m_cutEdges
List< Candidate > m_belt
bool leftmostFeasibleCandidate(List< node > &result)
bool singular(node v) const
bool isSingletonWith(const Candidate &c, node v) const
bool forbidden(node v) const
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.