ext/OGDF/src/layered/CoffmanGrahamRanking.cpp

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