15.3.327  src/lib/graph/shortest-paths.api

# shortest-paths.api
#
# Apis for shortest paths problems
#
# -- Allen Leung

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

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 Single_Source_Shortest_Paths {
        #
        package num:  Abelian_Group_With_Infinity;                      # Abelian_Group_With_Infinity   is from   src/lib/graph/group.api

        single_source_shortest_paths
            :
            { graph:   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.
              weight:  odg::Edge(E) -> num::Element,
              s:       odg::Node_Id
            } -> 
            { dist:   rwv::Rw_Vector( num::Element ),
              prior:  rwv::Rw_Vector( odg::Node_Id )
            };
    };
end;



stipulate
    package odg =  oop_digraph;                                         # oop_digraph           is from   src/lib/graph/oop-digraph.pkg
    package rwm =  rw_matrix;                                           # rw_matrix                     is from   src/lib/std/src/rw-matrix.pkg
herein

    api All_Pairs_Shortest_Paths {
        #
        package num:  Abelian_Group_With_Infinity;                      # Abelian_Group_With_Infinity   is from   src/lib/graph/group.api

        all_pairs_shortest_paths:   
                     { graph:    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.
                       weight:   odg::Edge(E) -> num::Element
                     } -> 
                     { dist:     rwm::Rw_Matrix( num::Element ),
                       prior:    rwm::Rw_Matrix( odg::Node_Id )
                     };
    };
end;