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

//------------------------------------------------------------------------------
// Connected Components
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------


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

static int count;

static void dfs(const graph& G, node v, node_array<int>& compnum)
{ 
  stack<node>  S;

  S.push(v);
  compnum[v] = count;

  while (!S.empty())
   { v = S.pop(); 
     edge e;
     forall_inout_edges(e,v) 
     { node w = G.opposite(v,e);
        if (compnum[w] == -1)
        { compnum[w] = count;
          S.push(w);
         }
      }
    }
 
} 

int COMPONENTS(const graph& G, node_array<int>& compnum)
{ // computes the connected components of the underlying undirected graph
  // compnum[v] = i  iff v in component i
  // number of components is returned

  node v;

  forall_nodes(v,G) compnum[v] = -1;

  count = 0;

  forall_nodes(v,G) 
    if (compnum[v] == -1) 
    { dfs(G,v,compnum);
      count++; 
     }

  return count;
}



int COMPONENTS1(const graph& G, node_array<int>& compnum)
{ 
  // an alternative implementation using node partitions (union-find)

  //Partition<node> P;
  node_partition P(G);
  edge e;
  node v;

  forall_nodes(v,G) compnum[v] = -1;

  //node_array<partition_item> It(G,nil);
  //forall_nodes(v,G) It[v] = P.make_block(v);
  //forall_edges(e,G) P.union_blocks(It[source(e)],It[target(e)]);

  forall_edges(e,G) P.union_blocks(source(e),target(e));


  int count = 0;
  forall_nodes(v,G) 
   { //node w = P.inf(P.find(It[v]));
     node w = P.find(v);
     if (compnum[w]==-1) compnum[w] = count++;
     compnum[v] = compnum[w];
    }

  return count;
}


