(* Strongly connected components, headers.
   Copyright (C) 2003 Jean Goubault-Larrecq and LSV, CNRS UMR 8643 & ENS Cachan.

   This file is part of h1.

   h1 is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   h1 is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with h1; see the file COPYING.  If not, write to
   the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*)

open "digraph_h";

extern val scc : ''_node digraph * ''_node -> (''_node -m> int) * (int -m> ''_node set);
(* scc (G, root):
 Tarjan's algorithm for computing strongly connected components of
 graph G with given root (only marks the parts of G reachable from root).
 Returns (dfsnum, cc), where:
 - dfsnum maps each node to its depth-first traversal number;
 - cc maps each 'low' num to the set of nodes having it as 'low'.
 There is one 'low' num for each strongly connected component,
 and this is the least dfsnum of all nodes in the component.
 *)

extern val scc_condense : ''_node digraph * ''_node
	   * (int -m> ''_node set)
	   -> int digraph * int;
(*
 scc_condense (G, root, cc).
 Build the condensed graph; each node in the condensed graph
 is the 'low' of nodes in the original graph.
 *)
