links 0.9.2 · OCaml Package

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 -> 'a -> 'b -> 'b

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 -> 'a -> 'b -> unit

val (*->) : ('a, 'b) Links_core.Utility.Hashtbl.t -> 'a -> 'b -> 'b

val (|->) : ('a -> 'b) -> 'a -> 'b

val (*+>) : 
  ('a, 'b Links_core.Utility.List.t) Links_core.Utility.Hashtbl.t ->
  'a ->
  'b ->
  unit

val (++=) : ('a -> 'b) -> 'a -> 'b

val hashtbl_invert : 
  ('a, 'b) Links_core.Utility.Hashtbl.t ->
  ('b, 'a Links_core.Utility.List.t) Links_core.Utility.Hashtbl.t

val hashtbl_values : 
  ('a, 'b) Links_core.Utility.Hashtbl.t ->
  'b Links_core.Utility.List.t

val hashtbl_regions : 
  ('a, 'b) Links_core.Utility.Hashtbl.t ->
  'a Links_core.Utility.List.t Links_core.Utility.List.t

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 ->
  ('a * 'b) Links_core.Utility.List.t

val unroll_edges : ('a * 'b list) list -> ('a * 'b) 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 ->
  ('a * 'a) list ->
  ('a, int) Links_core.Utility.Hashtbl.t
  * ('a, int) Links_core.Utility.Hashtbl.t
  * ('a, 'a option) Links_core.Utility.Hashtbl.t

Depth-first search

val topological_sort' : 'a list -> ('a * 'a) list -> ('a * int) list

val topological_sort : 'a list -> ('a * 'a) list -> 'a list

val transpose_edges : ('a * 'b) list -> ('b * 'a) list

val string_of_parent_tree : (string * string option) list -> string

val flatten_forest : ('a * 'a option) list -> 'a 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 * 'b) -> int

val strongly_connected_components : 'a list -> ('a * 'a) list -> 'a list list

val topo_sort_sccs : ('a * 'a list) list -> 'a 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.

package links