PreviousUpNext

15.3.360  src/lib/src/digraph-strongly-connected-components.api

## digraph-strongly-connected-components.api
## author: Matthias Blume

# Compiled by:
#     src/lib/std/standard.lib



#   Calculate the strongly-connected components (SCC)
#   of a directed graph.
#
#   The graph can have nodes with self-loops.


api Digraph_Strongly_Connected_Components {

    package nd:  Key;           # Key   is from   src/lib/src/key.api

    Node = nd::Key;

    Component   =   SIMPLE     Node                     #  singleton, no self-loop 
                |   RECURSIVE  List( Node );

    topological_order' : { roots: List( Node ), follow: Node -> List( Node ) }
                         -> List( Component );
        # Input: root node (s) and follow function.
        # Result: List of topologically sorted strongly-connected components.
        #         The component that contains the first of the given "roots"
        #         goes first.


    topological_order:  { root: Node, follow: Node -> List( Node ) }
                        -> List( Component );

        # For backward compatibility.           XXX BUGGO FIXME
        # AXIOM: topologicalOrder { root, follow } == topologicalOrder'{ roots=[root], follow }


};


## COPYRIGHT (c) 1999 Lucent Bell Laboratories.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext