1/** \file
2 * \brief Definition of coffman graham ranking algorithm for Sugiyama
3 *
4 * \author Till Schäfer
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <ogdf/layered/CoffmanGrahamRanking.h>
33#include <ogdf/layered/DfsAcyclicSubgraph.h>
34#include <ogdf/basic/GraphCopy.h>
35
36namespace ogdf {
37
38CoffmanGrahamRanking::CoffmanGrahamRanking() : m_w(3)
39{
40 m_subgraph.reset(new DfsAcyclicSubgraph());
41}
42
43
44void CoffmanGrahamRanking::call (const Graph& G, NodeArray<int>& rank)
45{
46 rank.init(G);
47 GraphCopy gc(G);
48
49 m_subgraph->callAndReverse(gc);
50 removeTransitiveEdges(gc);
51
52 List<Tuple2<node, int> > ready_nodes;
53 NodeArray<int> deg(gc);
54 NodeArray<int> pi(gc);
55 m_s.init(gc);
56
57 List<edge> edges;
58
59 for(node v : gc.nodes) {
60 edges.clear();
61 v->inEdges(edges);
62 deg[v] = edges.size();
63 if (deg[v] == 0) {
64 ready_nodes.pushBack(Tuple2<node,int>(v,0));
65 }
66 m_s[v].init(deg[v]);
67 }
68
69 int i = 1;
70 while(!ready_nodes.empty()) {
71 node v = ready_nodes.popFrontRet().x1();
72 pi[v] = i++;
73
74 for(adjEntry adj : v->adjEntries) {
75 if ((adj->theEdge()->source()) == v) {
76 node u = adj->twinNode();
77 m_s[u].insert(pi[v]);
78 if (--deg[u] == 0) {
79 insert(u,ready_nodes);
80 }
81 }
82 }
83 }
84
85
86 List<node> ready, waiting;
87
88 for(node v : gc.nodes) {
89 edges.clear();
90 v->outEdges(edges);
91 deg[v] = edges.size();
92 if (deg[v] == 0) {
93 insert(v,ready,pi); // ready.append(v);
94 }
95 }
96
97 int k;
98 // for all ranks
99 for (k = 1; !ready.empty(); k++) {
100
101 for (i = 1; i <= m_w && !ready.empty(); i++) {
102 node u = ready.popFrontRet();
103 rank[gc.original(u)] = k;
104
105 u->inEdges<List<edge>>(edges);
106 for (edge e : edges) {
107 if (--deg[e->source()] == 0){
108 waiting.pushBack(e->source());
109 }
110 }
111 }
112
113 while (!waiting.empty()) {
114 insert(waiting.popFrontRet(), ready, pi);
115 }
116 }
117
118 k--;
119 for(node v : G.nodes) {
120 rank[v] = k - rank[v];
121 }
122
123 m_s.init();
124}
125
126
127void CoffmanGrahamRanking::insert (node u, List<Tuple2<node,int> > &ready_nodes)
128{
129 int j = 0;
130
131 for( ListReverseIterator<Tuple2<node,int> > it = ready_nodes.rbegin(); it.valid(); ++it) {
132 node v = (*it).x1();
133 int sigma = (*it).x2();
134
135 if (sigma < j) {
136 ready_nodes.insertAfter(Tuple2<node,int>(u,j), it);
137 return;
138 }
139
140 if (sigma > j) continue;
141
142 const _int_set &x = m_s[u], &y = m_s[v];
143 int k = min(x.length(), y.length());
144
145 while (j < k && x[j] == y[j]) {
146 j++;
147 }
148
149 if (j == k) {
150 if (x.length() < y.length()) continue;
151
152 (*it).x2() = k;
153 ready_nodes.insertAfter(Tuple2<node,int>(u,sigma), it);
154 return;
155 }
156
157 if (x[j] < y[j]) continue;
158
159 (*it).x2() = j;
160 ready_nodes.insert(Tuple2<node,int>(u,sigma), it);
161 return;
162 }
163
164 ready_nodes.pushFront(Tuple2<node,int>(u,j));
165}
166
167
168void CoffmanGrahamRanking::insert (node v, List<node> &ready, const NodeArray<int> &pi)
169{
170 for( ListReverseIterator<node> it = ready.rbegin(); it.valid(); ++it) {
171 if (pi[v] <= pi[*it]) {
172 ready.insertAfter(v, it);
173 return;
174 }
175 }
176
177 ready.pushFront(v);
178}
179
180
181void CoffmanGrahamRanking::dfs(node v)
182{
183 ArrayBuffer<node> stack;
184 stack.push(v);
185
186 while (!stack.empty()) {
187 node w = stack.popRet();
188 m_mark[w] |= 1; // Mark w as visited.
189
190 // Set 4-bit for every successor u of w with set 2-bit.
191 for (adjEntry adj : w->adjEntries) {
192 if (adj->isSource()) {
193 node u = adj->twinNode();
194 if (m_mark[u] & 2) {
195 m_mark[u] |= 4;
196 }
197
198 // If u is unvisited, push it to the stack.
199 if ((m_mark[u] & 1) == 0) {
200 stack.push(u);
201 }
202 }
203 }
204 }
205}
206
207
208void CoffmanGrahamRanking::removeTransitiveEdges(Graph& G)
209{
210 List<edge> vout;
211
212 m_mark.init(G,0);
213 ArrayBuffer<node> visited;
214
215 for (node v : G.nodes) {
216 v->outEdges<List<edge>>(vout);
217
218 // Mark all successors of v with the 2-bit.
219 for (edge e : vout) {
220 node w = e->target();
221 m_mark[w] = 2;
222 }
223
224 // Call dfs for all unvisited successors of v.
225 for (edge e : vout) {
226 node w = e->target();
227 if ((m_mark[w] & 1) == 0) {
228 dfs(w);
229 }
230 }
231
232 // Delete all edges from v to nodes with set 4-bit.
233 for (edge e : vout) {
234 node w = e->target();
235 if (m_mark[w] & 4) {
236 G.delEdge(e);
237 }
238 }
239
240 // Reset mark-bits for all visited nodes.
241 while (!visited.empty()) {
242 m_mark[visited.popRet()] = 0;
243 }
244 }
245
246 m_mark.init();
247}
248
249}
250