ext/OGDF/src/layered/acyclic_subgraph.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 Implementation of algorithms for computing an
  11  * acyclic subgraph (DfsAcyclicSubgraph, GreedyCycleRemovel)
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #include <ogdf/layered/DfsAcyclicSubgraph.h>
  46 #include <ogdf/layered/GreedyCycleRemoval.h>
  47 #include <ogdf/basic/simple_graph_alg.h>
  48 #include <ogdf/basic/SList.h>
  49 #include <ogdf/basic/GraphAttributes.h>
  50 #include <ogdf/basic/Queue.h>
  51
  52
  53 namespace ogdf {
  54
  55
  56 //---------------------------------------------------------
  57 // DfsAcyclicSubgraph
  58 // computes a maximal acyclic subgraph by deleting all DFS
  59 // backedges (linear-time)
  60 //---------------------------------------------------------
  61
  62 void DfsAcyclicSubgraph::call (const Graph &G, List<edge> &arcSet)
  63 {
  64         isAcyclic(G,arcSet);
  65 }
  66
  67
  68 void DfsAcyclicSubgraph::callUML (
  69         const GraphAttributes &AG,
  70         List<edge> &arcSet)
  71 {
  72         const Graph &G = AG.constGraph();
  73
  74         // identify hierarchies
  75         NodeArray<int> hierarchy(G,-1);
  76         int count = 0;
  77         int treeNum = -1;
  78
  79         node v;
  80         forall_nodes(v,G)
  81         {
  82                 if(hierarchy[v] == -1) {
  83                         int n = dfsFindHierarchies(AG,hierarchy,count,v);
  84                         if(n > 1) treeNum = count;
  85                         ++count;
  86                 }
  87         }
  88
  89         arcSet.clear();
  90
  91         // perform DFS on the directed graph formed by generalizations
  92         NodeArray<int> number(G,0), completion(G);
  93         int nNumber = 0, nCompletion = 0;
  94
  95         forall_nodes(v,G) {
  96                 if(number[v] == 0)
  97                         dfsBackedgesHierarchies(AG,v,number,completion,nNumber,nCompletion);
  98         }
  99
 100         // collect all backedges within a hierarchy
 101         // and compute outdeg of each vertex within its hierarchy
 102         EdgeArray<bool> reversed(G,false);
 103         NodeArray<int> outdeg(G,0);
 104
 105         edge e;
 106         forall_edges(e,G) {
 107                 if(AG.type(e) != Graph::generalization || e->isSelfLoop())
 108                         continue;
 109
 110                 node src = e->source(), tgt = e->target();
 111
 112                 outdeg[src]++;
 113
 114                 if (hierarchy[src] == hierarchy[tgt] &&
 115                         number[src] >= number[tgt] && completion[src] <= completion[tgt])
 116                         reversed[e] = true;
 117         }
 118
 119         // topologial numbering of nodes within a hierarchy (for each hierarchy)
 120         NodeArray<int> numV(G);
 121         Queue<node> Q;
 122         int countV = 0;
 123
 124         forall_nodes(v,G)
 125                 if(outdeg[v] == 0)
 126                         Q.append(v);
 127
 128         while(!Q.empty()) {
 129                 v = Q.pop();
 130
 131                 numV[v] = countV++;
 132
 133                 forall_adj_edges(e,v) {
 134                         node w = e->source();
 135                         if(w != v) {
 136                                 if(--outdeg[w] == 0)
 137                                         Q.append(w);
 138                         }
 139                 }
 140         }
 141
 142         // "direct" associations
 143         forall_edges(e,G) {
 144                 if(AG.type(e) == Graph::generalization || e->isSelfLoop())
 145                         continue;
 146
 147                 node src = e->source(), tgt = e->target();
 148
 149                 if(hierarchy[src] == hierarchy[tgt]) {
 150                         if (numV[src] < numV[tgt])
 151                                 reversed[e] = true;
 152                 } else {
 153                         if(hierarchy[src] == treeNum || (hierarchy[tgt] != treeNum &&
 154                                 hierarchy[src] > hierarchy[tgt]))
 155                                 reversed[e] = true;
 156                 }
 157         }
 158
 159         // collect reversed edges
 160         forall_edges(e,G)
 161                 if(reversed[e])
 162                         arcSet.pushBack(e);
 163 }
 164
 165
 166 int DfsAcyclicSubgraph::dfsFindHierarchies(
 167         const GraphAttributes &AG,
 168         NodeArray<int> &hierarchy,
 169         int i,
 170         node v)
 171 {
 172         int count = 1;
 173         hierarchy[v] = i;
 174
 175         edge e;
 176         forall_adj_edges(e,v) {
 177                 if(AG.type(e) != Graph::generalization)
 178                         continue;
 179
 180                 node w = e->opposite(v);
 181                 if(hierarchy[w] == -1)
 182                         count += dfsFindHierarchies(AG,hierarchy,i,w);
 183         }
 184
 185         return count;
 186 }
 187
 188
 189 void DfsAcyclicSubgraph::dfsBackedgesHierarchies(
 190         const GraphAttributes &AG,
 191         node v,
 192         NodeArray<int> &number,
 193         NodeArray<int> &completion,
 194         int &nNumber,
 195         int &nCompletion)
 196 {
 197         number[v] = ++nNumber;
 198
 199         edge e;
 200         forall_adj_edges(e,v)
 201         {
 202                 if(AG.type(e) != Graph::generalization)
 203                         continue;
 204
 205                 node w = e->target();
 206
 207                 if (number[w] == 0)
 208                         dfsBackedgesHierarchies(AG,w,number,completion,nNumber,nCompletion);
 209         }
 210
 211         completion[v] = ++nCompletion;
 212 }
 213
 214
 215
 216
 217 //---------------------------------------------------------
 218 // GreedyCycleRemoval
 219 // greedy heuristic for computing a maximal acyclic
 220 // subgraph (linear-time)
 221 //---------------------------------------------------------
 222
 223 void GreedyCycleRemoval::dfs (node v, const Graph &G)
 224 {
 225         m_visited[v] = true;
 226
 227         int i;
 228         if (v->outdeg() == 0) i = m_min;
 229         else if (v->indeg() == 0) i = m_max;
 230         else i = v->outdeg() - v->indeg();
 231
 232         m_item[v] = m_B[m_index[v] = i].pushBack(v);
 233         m_in [v] = v->indeg();
 234         m_out[v] = v->outdeg();
 235         m_counter++;
 236
 237         edge e;
 238         forall_adj_edges(e,v) {
 239                 node u = e->opposite(v);
 240                 if (!m_visited[u])
 241                         dfs(u,G);
 242         }
 243 }
 244
 245
 246 void GreedyCycleRemoval::call (const Graph &G, List<edge> &arcSet)
 247 {
 248         arcSet.clear();
 249
 250         node u, v, w;
 251         edge e;
 252
 253         m_max = m_min = 0;
 254         forall_nodes(v,G) {
 255                 if (-v->indeg () < m_min) m_min = -v->indeg ();
 256                 if ( v->outdeg() > m_max) m_max =  v->outdeg();
 257         }
 258
 259         if (G.numberOfEdges() == 0) return;
 260
 261         m_visited.init(G,false); m_item.init(G);
 262         m_in     .init(G);       m_out .init(G);
 263         m_index  .init(G);       m_B   .init(m_min,m_max);
 264
 265         SListPure<node> S_l, S_r;
 266         NodeArray<int> pos(G);
 267
 268         m_counter = 0;
 269         forall_nodes(v,G) {
 270                 if (m_visited[v]) continue;
 271                 dfs(v,G);
 272
 273                 int i, max_i = m_max-1, min_i = m_min+1;
 274
 275                 for ( ; m_counter > 0; m_counter--) {
 276                         if (!m_B[m_min].empty()) {
 277                                 u = m_B[m_min].front(); m_B[m_min].popFront();
 278                                 S_r.pushFront(u);
 279
 280                         } else if (!m_B[m_max].empty()) {
 281                                 u = m_B[m_max].front(); m_B[m_max].popFront();
 282                                 S_l.pushBack(u);
 283
 284                         } else {
 285                                 while (m_B[max_i].empty())
 286                                         max_i--;
 287                                 while (m_B[min_i].empty())
 288                                         min_i++;
 289
 290                                 if (abs(max_i) > abs(min_i)) {
 291                                         u = m_B[max_i].front(); m_B[max_i].popFront();
 292                                         S_l.pushBack(u);
 293                                 } else {
 294                                         u = m_B[min_i].front(); m_B[min_i].popFront();
 295                                         S_r.pushFront(u);
 296                                 }
 297                         }
 298
 299                         m_item[u] = ListIterator<node>();
 300
 301                         forall_adj_edges(e,u) {
 302                                 if (e->target() == u) {
 303                                         w = e->source();
 304                                         if (m_item[w].valid()) {
 305                                                 m_out[w]--; i = m_index[w];
 306                                                 m_B[i].del(m_item[w]);
 307                                                 if (m_out[w] == 0) i = m_min;
 308                                                 else if (m_in[w] == 0) i = m_max;
 309                                                 else i--;
 310                                                 m_item[w] = m_B[m_index[w] = i].pushBack(w);
 311
 312                                                 if (m_index[w] < min_i)
 313                                                         min_i = m_index[w];
 314                                         }
 315                                 } else {
 316                                         w = e->target();
 317                                         if (m_item[w].valid()) {
 318                                                 m_in[w]--; i = m_index[w];
 319                                                 m_B[i].del(m_item[w]);
 320                                                 if (m_out[w] == 0) i = m_min;
 321                                                 else if (m_in[w] == 0) i = m_max;
 322                                                 else i++;
 323                                                 m_item[w] = m_B[m_index[w] = i].pushBack(w);
 324
 325                                                 if (m_index[w] > max_i)
 326                                                         max_i = m_index[w];
 327                                         }
 328                                 }
 329                         }
 330                 }
 331
 332                 SListConstIterator<node> it;
 333                 for(i = 0, it = S_l.begin(); it.valid(); ++it)
 334                         pos[*it] = i++;
 335                 for(it = S_r.begin(); it.valid(); ++it)
 336                         pos[*it] = i++;
 337
 338                 S_l.clear(); S_r.clear();
 339         }
 340
 341         forall_edges(e,G)
 342                 if (pos[e->source()] >= pos[e->target()])
 343                         arcSet.pushBack(e);
 344
 345         m_visited.init(); m_item.init();
 346         m_in     .init(); m_out .init();
 347         m_index  .init(); m_B.init();
 348 }
 349
 350
 351 } // end namespace ogdf