package links

  1. Overview
  2. Docs

A few graph algorithms. Pure interfaces, but impure implementations. A graph is represented as node lists + adjacency list.

val hashfind_dflt : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'c -> 'd -> 'e

Crazy notation for hashtable updates. Suggestions are welcomed.

table *->! k v updates k to v in table table *-> k |-> d returns the value for k in table, or d if k is not set. table *+> k ++= newVal cons'es newVal onto the list stored under k

val (*->!) : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'c -> 'd -> unit
val (*->) : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'a -> 'b -> 'b
val (|->) : ('a -> 'b) -> 'c -> 'd
val (*+>) : ('a, 'b list) Links_core.Utility.Hashtbl.t -> 'c -> 'd -> unit
val (++=) : ('a -> 'b) -> 'c -> 'd
val hashtbl_invert : ('a, 'b) Links_core.Utility.Hashtbl.t -> ('c, 'd list) Links_core.Utility.Hashtbl.t
val hashtbl_values : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'c list
val hashtbl_regions : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'a list list

hashtbl_regions table is the list of equivalence classes of keys in table, where equivalence is determined through lookup in table. If you think of the value under each key as its "color", this gives you the list of groups having the same color.

val hashtbl_as_alist : ('a, 'b) Links_core.Utility.Hashtbl.t -> ('c * 'd) list
val unroll_edges : ('a * 'b list) list -> ('c * 'd) list

unroll_edges: given an alist that maps an x to a list nbhd(x) of the same type, return a list of all the pairs (u, v) where v \in nbhd(u)

val edge_to_str : (string * string) -> string
val reverse : 'a list -> 'a list
val dfs : 'a list -> ('b * 'c) list -> ('d, int) Links_core.Utility.Hashtbl.t * ('e, int) Links_core.Utility.Hashtbl.t * ('f, 'g option) Links_core.Utility.Hashtbl.t

Depth-first search

val topological_sort' : 'a list -> ('a * 'a) list -> ('b * int) list
val topological_sort : 'a list -> ('a * 'a) list -> 'b list
val transpose_edges : ('a * 'b) list -> ('b * 'a) list
val string_of_parent_tree : (string * string option) list -> string
val flatten_forest : ('a * 'a0 option) list -> 'a1 list list

Takes a tree given in "parent-pointer" form, and returns a list of the nodes in each tree. More or less duplicates the union-find algorithm?

val cmp_snd_desc : ('a * 'b) -> ('c * 'd) -> int
val strongly_connected_components : 'a list -> ('a0 * 'a0) list -> 'a1 list list
val topo_sort_sccs : ('a * 'a list) list -> 'a0 list list

topo_sort_sccs: given a graph in adjacency-list representation, find all the sccs and topologically sort them; return the result as a list of sccs, the sccs represented as the list of their members.