15.3.473  src/lib/std/src/graph-by-edge-hashtable.api

# graph-by-edge-hashtable.api
#
# A graph representation in which nodes consume no space, and
# edges are stored in a hashtable.  (Nodes are represented by
# small integers.)
#
# We record only the presence or absence of and edges,
# and support essentially only edge insertion and edge
# existence-testing. (Edge deletion is implemented in
# the package but not listed in the API, oddly.)
#
# This is a space-efficient solution when nodes greatly outnumber
# edges;  it can also be time-efficient when edges greatly outnumber
# nodes, as it avoids scanning down long adjacency lists.
# 
# For one application, see codetemp_interference_graph.                 # codetemp_interference_graph   is from   src/lib/compiler/back/low/regor/codetemp-interference-graph.pkg

# Compiled by:
#     src/lib/std/src/standard-core.sublib

stipulate
    package rwv =  rw_vector;                                           # rw_vector                     is from   src/lib/std/src/rw-vector.pkg
herein

    # This api is implemented in:
    #
    #     src/lib/std/src/graph-by-edge-hashtable.pkg
    #
    api Graph_By_Edge_Hashtable {
        #
        Bucket                                                          # Hashtable buckets.  (Why are we exporting these??)
          = NIL
          | BUCKET  (Int, Int, Bucket)
          ; 

        Hashtable                                                       # Hashtable vector-of-bucketlists.
          = SMALL   (Ref( rwv::Rw_Vector( List( Unt ) ) ), Unt)         # Store each edge as a single Unt.
          | LARGE   (Ref( rwv::Rw_Vector( Bucket      ) ), Unt)         # Store each edge as a triple (node1, node2, next-in-bucketchain).
          ;
 
        Graph_By_Edge_Hashtable
          = 
          GRAPH_BY_EDGE_HASHTABLE
            { table:            Hashtable, 
              edge_count:       Ref( Int )
            };

        empty_graph:    Graph_By_Edge_Hashtable;

        get_hashchains_count:   Graph_By_Edge_Hashtable -> Int;         # I.e., how long is the primary hashtable vector?
        get_edge_count:         Graph_By_Edge_Hashtable -> Int;         # I.e., how many times has insert_edge been called?

        insert_edge:  Graph_By_Edge_Hashtable -> (Int, Int) -> Bool;    # Returns TRUE if edge was inserted, FALSE if it was not (because it was already present).
        edge_exists:  Graph_By_Edge_Hashtable -> (Int, Int) -> Bool;
    };
end;