15.3.318  src/lib/graph/graph-strongly-connected-components.api

# graph-strongly-connected-components.api
#
# This module computes strongly connected components
# (SCC) of a graph.
#
# Each SCC is represented as a list of nodes.
# All nodes are folded together with a user supplied function.
#
# -- Allen Leung

# Compiled by:
#     src/lib/graph/graphs.lib



stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
herein

    api Graph_Strongly_Connected_Components {
        #
        # Strongly connected components:

        scc:  odg::Digraph (N,E,G) ->                                   # Here N,E,G stand stead for the types of client-package-supplied records associated with (respectively) nodes, edges and graphs.
                   ((List( odg::Node_Id ), X) -> X) -> X -> X;

        scc' : { n:          Int,
                 nodes:      List( odg::Node_Id ),
                 out_edges:  odg::Node_Id ->  List( odg::Edge( E ) )
               }
               ->
               ((List( odg::Node_Id ), X) -> X) -> X -> X;

    };
end;