/*******************************************************************************
+
+  LEDA 3.5
+
+  _stnumb.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

//-----------------------------------------------------------------------------
//
// ST_NUMBERING(graph& G, node_array<int>& st_num, list<node>& st_list)
//
// computing an st-numbering of a biconnected and bidirected graph
//
// R. Hesse, E. Kalliwoda, S. Naeher  (1996)
//
//-----------------------------------------------------------------------------

#include <LEDA/graph_alg.h>
#include <LEDA/node_list.h>


static void ST_DFS(graph& G, node v, int& count, node_array<int>&  dfsnum, 
                                                 node_array<int>&  lownum, 
                                                 node_array<edge>& tree_in,
                                                 node_array<edge>& low_out)
{ dfsnum[v] = count;
  lownum[v] = count;
  count++;
  
  edge e;
  forall_adj_edges(e,v)
  { 
    node w = G.target(e);
  
    if (dfsnum[w] == 0 ) // first visit
      { tree_in[w] = e;
        ST_DFS(G,w,count,dfsnum,lownum,tree_in,low_out);
        if (lownum[w] < lownum[v]) 
        { lownum[v] = lownum[w]; 
          low_out[v] = e;
         }
       }
    else 
      if (w != source(tree_in[v]) && dfsnum[w] < lownum[v]) 
      { lownum[v] = dfsnum[w]; 
        low_out[v] = e;
       }
   }
 }



static void FINDPATH(graph& G, node w, node_array<bool>& used_node,
                                        edge_array<bool>& used_edge,
                                        node_array<edge>& pred_edge,
                                        node_list& PATH)
{ while ( !used_node[w] )
  { edge x = pred_edge[w];  
    PATH.push(w);
    used_node[w] = true; 
    used_edge[x] = true;
    w = G.opposite(w,x);
   } 
}
  


void ST_NUMBERING(graph& G, node_array<int>& st_num, list<node>& st_list) 
{

/*
if (!Is_Biconnected(G)) 
   error_handler(1,"st_numbering: Graph must be biconnected.");
*/

  node_array<int>  dfsnum(G,0);
  node_array<int>  lownum(G,0);
  node_array<edge> tree_in(G,nil);
  node_array<edge> low_out(G,nil);

  // choose a random first edge e

  int  r = rand_int(1,G.number_of_nodes());
  node v;
  forall_nodes(v,G)
      if (--r == 0) break;

  edge e = G.first_adj_edge(v);
  node t = G.source(e);
  node s = G.target(e);

  int count = 1;

  tree_in[t] = e;  // dummy
  
  ST_DFS(G,t,count,dfsnum,lownum,tree_in,low_out);

  edge_array<bool> used_edge(G,false);
  node_array<bool> used_node(G,false);

  used_node[s] = true;
  used_node[t] = true;
  used_edge[e] = true;
  
  st_list.clear();
  st_list.push(t);
  st_list.push(s);

  int st_count = 1;

  for (list_item top = st_list.first(); top; top = st_list.succ(top))
  { node v = st_list[top];
    st_num[v] = st_count++;

    forall_adj_edges(e,v)
    { 
      if (used_edge[e]) continue;
      used_edge[e] = true;

      node_list P;
      node w = target(e);
 
      if (tree_in[w] == e)          // unused tree edge (v,w)
         FINDPATH(G,w,used_node,used_edge,low_out,P);
      else 
         if (dfsnum[v] < dfsnum[w]) // unused back edge (w,v)
            FINDPATH(G,w,used_node,used_edge,tree_in,P);

      forall(w,P) st_list.insert(w,top);
    }
  }
}


