/*******************************************************************************
+
+  LEDA 3.5
+
+  _bicomponents.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.
+ 
*******************************************************************************/

//------------------------------------------------------------------------------
// BICONNECTED COMPONENTS                                                      
//                                                                              
// Michael Meiser (1991)                                                       
//------------------------------------------------------------------------------


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



static void bcc_dfs(const graph& G,node v,edge_array<int>& compnum,
                    node_array<int>& dfsnum,node_array<int>& lowpt,
                    node_array<node>& father,stack<node>& current,
                    int& count1,int& count2);


int BICONNECTED_COMPONENTS(const graph& G, edge_array<int>& compnum)
{
  // computes the biconnected components of the underlying  undirected
  // graph,  returns m = number of biconnected components and 
  // in edge_array<int> compnum for each edge an integer with
  // compnum[x] = compnum[y] iff edges x and y belong to the same component 
  // and 0 <= compnum[e] <= m-1 for all edges e
  // running time : O(|V|+|E|)
  //
  // (problem  with self-loops ? )

  stack<node> current;
  node_array<int> dfsnum(G,-1);
  node_array<int> lowpt(G,0);
  node_array<node> father(G,nil);
  int count1 = 0; 
  int count2 = 0;
  node v;

  forall_nodes(v,G)
   if (dfsnum[v] == -1)
    { dfsnum[v] = ++count1;
      current.push(v);
      bcc_dfs(G,v,compnum,dfsnum,lowpt,father,current,count1,count2);
     }

  return(count2);

 } // BI_COMPONENTS



static void bcc_dfs(const graph& G,node v,edge_array<int>& compnum,
                    node_array<int>& dfsnum,node_array<int>& lowpt,
                    node_array<node>& father,stack<node>& current,
                    int& count1,int& count2)
 {

  lowpt[v] = dfsnum[v];

  edge e;
  forall_inout_edges(e,v)
  { node w = G.opposite(v,e);
    if (dfsnum[w] == -1)
    { dfsnum[w] = ++count1;
      current.push(w);
      father[w] = v;
      bcc_dfs(G,w,compnum,dfsnum,lowpt,father,current,count1,count2);
      lowpt[v] = Min(lowpt[v],lowpt[w]);
     }
    else
     lowpt[v] = Min(lowpt[v],dfsnum[w]);
   }

  if (father[v] && (lowpt[v] == dfsnum[father[v]]))
  { node w;
    do { w = current.pop();
         edge e;
         forall_inout_edges(e,w)
         if (dfsnum[w] > dfsnum[G.opposite(w,e)]) compnum[e] = count2;
        } while (w != v);

    count2++;
  }

 } // bcc_dfs


