15.4.780  src/lib/graph/node-partition.pkg

# node-partition.pkg
#
# This implenments node partitions (i.e. a union-find data package)
# on nodes.
#
# -- 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 Node_Partition {
        #
        Node_Partition(N);

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

        !!   : Node_Partition(N) -> odg::Node_Id -> odg::Node(N);

        ====   : Node_Partition(N) -> (odg::Node_Id, odg::Node_Id) -> Bool;

        union:  Node_Partition(N) -> ((odg::Node(N), odg::Node(N)) -> odg::Node(N))
                                  ->  (odg::Node_Id, odg::Node_Id)
                                  -> Bool;

        union': Node_Partition(N) -> (odg::Node_Id, odg::Node_Id) -> Bool;

    };
end;



stipulate
    package djs =  disjoint_sets_with_constant_time_union;                                      # disjoint_sets_with_constant_time_union        is from   src/lib/src/disjoint-sets-with-constant-time-union.pkg
    package odg =  oop_digraph;                                                                 # oop_digraph                                   is from   src/lib/graph/oop-digraph.pkg
    package ht  =  hashtable;                                                                   # hashtable                                     is from   src/lib/src/hashtable.pkg
herein

    package node_partition
    :       Node_Partition                                                                      # Node_Partition                                is from   src/lib/graph/node-partition.pkg
    {
        Node_Partition( N )
            =
            ht::Hashtable (odg::Node_Id, djs::Disjoint_Set( odg::Node( N ) ) );

        fun node_partition (odg::DIGRAPH dig)
            =
            {   ppp =  ht::make_hashtable (unt::from_int, (==)) { size_hint => dig.order () * 2, not_found_exception => odg::NOT_FOUND };
                ins =  ht::set ppp;

                dig.forall_nodes
                    (\\ n as (i, _) =  ins (i, djs::make_singleton_disjoint_set n));

                ppp;
            };

        fun !! ppp x           =  djs::get      (ht::look_up ppp x);
        fun ==== ppp (x, y)    =  djs::equal    (ht::look_up ppp x, ht::look_up ppp y);
        fun union ppp f (x, y) =  djs::unify f  (ht::look_up ppp x, ht::look_up ppp y);
        fun union' ppp (x, y)  =  djs::union    (ht::look_up ppp x, ht::look_up ppp y);
    };
end;