ext/OGDF/src/basic/stNumber.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of st-numbering algorithm
  11  *
  12  * \author Sebastian Leipert
  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
  44 #include <ogdf/basic/simple_graph_alg.h>
  45 #include <ogdf/basic/Stack.h>
  46 #include <ogdf/basic/EdgeArray.h>
  47 #include <ogdf/basic/NodeArray.h>
  48
  49 namespace ogdf {
  50
  51 // Needed by the function stNumber
  52 void stSearch(
  53         const Graph       &C,
  54         node                      sink,
  55         int                       &count,
  56         NodeArray<int>  &low,
  57         NodeArray<int>  &dfn,
  58         NodeArray<edge> &dfsInEdge,
  59         NodeArray<edge> &followLowPath);
  60
  61 // Needed by the function stNumber
  62 bool stPath(
  63         StackPure<node> &path,
  64         node                    v,
  65         adjEntry                &adj,
  66         NodeArray<bool> &markedNode,
  67         EdgeArray<bool> &markedEdge,
  68         NodeArray<int>  &dfn,
  69         NodeArray<edge> &dfsInEdge,
  70         NodeArray<edge> &followLowPath);
  71
  72 // Computes an st-Numbering.
  73 // Precondition: G must be biconnected and simple.
  74 // Exception: the Graph is allowed to have isolated nodes.
  75 // The st-numbers are stored in NodeArray. Return value is
  76 // the number t. It is 0, if the computation was unsuccessful.
  77 // The nodes s and t may be specified. In this case
  78 // s and t have to be adjacent.
  79 // If s and t are set 0 and parameter randomized is set to true,
  80 // the st edge is chosen to be a random edge in G.
  81
  82 int stNumber(const Graph &G,
  83         NodeArray<int> &numbering,
  84         node s,
  85         node t,
  86         bool randomized)
  87 {
  88
  89         int    count       = 1;
  90
  91         // Stores for every vertex its LOW number
  92         NodeArray<int> low(G,0);
  93         // Stores for every vertex ist DFN number
  94         NodeArray<int> dfn(G,0);
  95
  96         // Stores for every vertex if it has been visited dsuring the st-numbering
  97         NodeArray<bool> markedNode(G,false);
  98         // Stores for every edge if it has been visited dsuring the st-numbering
  99         EdgeArray<bool> markedEdge(G,false);
 100
 101         // Stores for every node its ingoing edge of the dfs tree.
 102         NodeArray<edge> dfsInEdge(G,0);
 103
 104         // Stores a path of vertices that have not been visited.
 105         StackPure<node> path;
 106
 107         //Stores for every node the outgoing, first edge on the
 108         // path that defines the low number of the node.
 109         NodeArray<edge> followLowPath(G,0);
 110
 111         edge st;
 112         node v;
 113
 114         if (s && t)
 115         {
 116                 bool found = false;
 117                 forall_adj_edges(st,s)
 118                         if (st->opposite(s) == t)
 119                         {
 120                                 found = true;
 121                                 break;
 122                         }
 123                 if (!found)
 124                         return 0;
 125         }
 126         else if (s)
 127         {
 128                 st = s->firstAdj()->theEdge();
 129                 t = st->opposite(s);
 130         }
 131         else if (t)
 132         {
 133                 st = t->firstAdj()->theEdge();
 134                 s = st->opposite(t);
 135         }
 136         else
 137         {
 138                 if(randomized) {
 139                         // chose a random edge in G
 140                         st = G.chooseEdge();
 141                         if(!st) // graph is empty?
 142                                 return 0;
 143                         s = st->source();
 144                         t = st->target();
 145
 146                 } else {
 147                         forall_nodes(s,G)
 148                         {
 149                                 if (s->degree() > 0)
 150                                 {
 151                                         st = s->firstAdj()->theEdge();
 152                                         t = st->opposite(s);
 153                                         break;
 154                                 }
 155                         }
 156                 }
 157         }
 158         if (!s || !t)
 159                 return 0;
 160
 161         // Compute the DFN and LOW numbers
 162         // of the block.
 163         dfn[t] = count++;
 164         low[t] = dfn[t];
 165         stSearch(G,s,count,low,dfn,dfsInEdge,followLowPath);
 166         if (low[t] > low[s])
 167                 low[t] = low[s];
 168
 169         markedNode[s] = true;
 170         markedNode[t] = true;
 171         markedEdge[st] = true;
 172
 173         StackPure<node> nodeStack;      // nodeStack stores the vertices during the
 174                                                                 // computation of the st-numbering.
 175         nodeStack.push(t);
 176         nodeStack.push(s);
 177         count = 1;
 178         v = nodeStack.pop();
 179         adjEntry adj = 0;
 180         while (v != t)
 181         {
 182                 if (!stPath(path,v,adj,markedNode,markedEdge,dfn,dfsInEdge,followLowPath))
 183                 {
 184                         numbering[v] = count;
 185                         count++;
 186                         adj = 0;
 187                 }
 188                 else
 189                 {
 190                         while (!path.empty())
 191                                 nodeStack.push(path.pop());
 192                 }
 193                 v = nodeStack.pop();
 194         }
 195         numbering[t] = count;
 196         return count;
 197 }
 198
 199
 200 // Computes the DFN and LOW numbers of a biconnected component
 201 // Uses DFS strategy
 202 void stSearch(
 203         const Graph             &G,
 204         node                            v,
 205         int                             &count,
 206         NodeArray<int>  &low,
 207         NodeArray<int>  &dfn,
 208         NodeArray<edge> &dfsInEdge,
 209         NodeArray<edge> &followLowPath)
 210 {
 211         dfn[v] = count;
 212         count++;
 213         low[v] = dfn[v];
 214
 215         node adj = 0;
 216         edge e;
 217         forall_adj_edges(e,v)
 218         {
 219                 adj = e->opposite(v);
 220
 221                 if(!dfn[adj]) // node not visited yet
 222                 {
 223                         dfsInEdge[adj] = e;
 224                         stSearch(G,adj,count,low,dfn,dfsInEdge,followLowPath);
 225                         if (low[v] > low[adj])
 226                         {
 227                                 low[v] = low[adj];
 228                                 followLowPath[v] = e;
 229                         }
 230                 }
 231                 else if (low[v] > dfn[adj])
 232                 {
 233                         low[v] = dfn[adj];
 234                         followLowPath[v] = e;
 235                 }
 236         }
 237 }
 238
 239
 240 bool stPath(StackPure<node>     &path,
 241                         node                    v,
 242                         adjEntry                &adj,
 243                         NodeArray<bool> &markedNode,
 244                         EdgeArray<bool> &markedEdge,
 245                         NodeArray<int>  &dfn,
 246                         NodeArray<edge> &dfsInEdge,
 247                         NodeArray<edge> &followLowPath)
 248 {
 249         edge e;
 250         node w;
 251         path.clear();
 252
 253         if (!adj)
 254                 adj = v->firstAdj(); // no edge has been visited yet
 255         do {
 256                 e = adj->theEdge();
 257                 adj = adj->succ();
 258                 if (markedEdge[e])
 259                         continue;
 260                 markedEdge[e] = true;
 261
 262                 w = e->opposite(v);
 263
 264                 if (dfsInEdge[w] == e)
 265                 {
 266                         path.push(v);
 267                         while (!markedNode[w])
 268                         {
 269                                 e = followLowPath[w];
 270                                 path.push(w);
 271                                 markedNode[w] = true;
 272                                 markedEdge[e] = true;
 273                                 w = e->opposite(w);
 274                         }
 275                         return true;
 276                 }
 277                 else if (dfn[v] < dfn[w])
 278                 {
 279                         path.push(v);
 280                         while (!markedNode[w])
 281                         {
 282                                 e = dfsInEdge[w];
 283                                 path.push(w);
 284                                 markedNode[w] = true;
 285                                 markedEdge[e] = true;
 286                                 w = e->opposite(w);
 287                         }
 288                         return true;
 289                 }
 290
 291         }while (adj != 0);
 292
 293         return false;
 294 }
 295
 296
 297 bool testSTnumber(const Graph &G, NodeArray<int> &st_no,int max)
 298 {
 299         bool   foundLow = false;
 300         bool   foundHigh = false;
 301         bool   it_is = true;
 302         node   v;
 303
 304         forall_nodes(v,G)
 305         {
 306                 if (v->degree() == 0)
 307                         continue;
 308
 309                 foundHigh = foundLow = 0;
 310                 if (st_no[v] == 1)
 311                 {
 312                         adjEntry adj;
 313                         forall_adj(adj,v)
 314                         {
 315                                 if (st_no[adj->theEdge()->opposite(v)] == max)
 316                                         foundLow = foundHigh = 1;
 317                         }
 318                 }
 319
 320                 else if (st_no[v] == max)
 321                 {
 322                         adjEntry adj;
 323                         forall_adj(adj,v)
 324                         {
 325                                 if (st_no[adj->theEdge()->opposite(v)] == 1)
 326                                         foundLow = foundHigh = 1;
 327                         }
 328                 }
 329
 330                 else
 331                 {
 332                         adjEntry adj;
 333                         forall_adj(adj,v)
 334                         {
 335                                 if (st_no[adj->theEdge()->opposite(v)] < st_no[v])
 336                                         foundLow = 1;
 337                                 else if (st_no[adj->theEdge()->opposite(v)] > st_no[v])
 338                                         foundHigh = 1;
 339                         }
 340                 }
 341                 if (!foundLow || !foundHigh)
 342                         it_is = 0;
 343         }
 344         return it_is;
 345 }
 346
 347
 348 }