15.3.316  src/lib/graph/graph-dfs.api

# Some simple routines for performing depth first search.
# 
# -- Allen Leung

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



###             "God is a hacker, not an engineer."
###                            -- Francis Crick



stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
    package rwv =  rw_vector;                                           # rw_vector             is from   src/lib/std/src/rw-vector.pkg
herein


    api Graph_Depth_First_Search {
        #
        # Depth first search:

        dfs:   odg::Digraph (N,E,G)  -> 
                 (odg::Node_Id -> Void) ->
                 (odg::Edge( E ) -> Void) -> 
                 List( odg::Node_Id ) -> Void;

        dfsfold:   odg::Digraph (N,E,G)  -> 
                     ((odg::Node_Id, X) -> X) ->
                     ((odg::Edge( E ), Y) -> Y) -> 
                      List( odg::Node_Id ) -> (X, Y) -> (X, Y);

        dfsnum:   odg::Digraph (N,E,G) ->
                      List( odg::Node_Id ) ->
                     { dfsnum:   rwv::Rw_Vector( Int ),  #  Dfs numbering 
                       compnum:  rwv::Rw_Vector( Int )   #  Completion time 
                     };

        # Preorder/postorder numbering: 
        preorder_numbering:   odg::Digraph (N,E,G) -> Int -> rwv::Rw_Vector Int;
        postorder_numbering:  odg::Digraph (N,E,G) -> Int -> rwv::Rw_Vector Int;

    };
end;