Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /smlnj-lib/trunk/Util/graph-scc-sig.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/Util/graph-scc-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 816 - (view) (download)
Original Path: sml/trunk/src/smlnj-lib/Util/graph-scc-sig.sml

1 : monnier 496 (* graph-scc-sig.sml
2 :     *
3 :     * COPYRIGHT (c) 1999 Lucent Bell Laboratories.
4 :     *
5 :     * Calculate strongly-connected components of directed graph.
6 :     * The graph can have nodes with self-loops.
7 :     *
8 :     * author: Matthias Blume
9 :     *)
10 :    
11 :     signature GRAPH_SCC =
12 :     sig
13 :    
14 :     structure Nd : ORD_KEY
15 :    
16 :     type node = Nd.ord_key
17 :    
18 :     datatype component
19 :     = SIMPLE of node (* singleton, no self-loop *)
20 :     | RECURSIVE of node list
21 :    
22 : jhr 816 val topOrder': { roots: node list, follow: node -> node list }
23 :     -> component list
24 :     (* take root node(s) and follow function and return
25 : monnier 496 * list of topologically sorted strongly-connected components;
26 : jhr 816 * the component that contains the first of the given "roots"
27 :     * goes first
28 : monnier 496 *)
29 :    
30 : jhr 816 val topOrder : { root: node, follow: node -> node list }
31 :     -> component list
32 :     (* for backward compatibility;
33 :     * AXIOM: topOrder{root,follow}==topOrder'{roots=[root],follow=follow}
34 :     *)
35 :    
36 : monnier 496 end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0