Graphlib.Std
Graphlib
is a generic library that extends a OCamlGraph library.Graphlib
uses its own and richer Graph
interface that is isomorphic to OCamlGraph's Sigs.P
signature for persistent graphs. Two functors witnesses isomorphism of the interfaces: Graphlib
.To_ocamlgraph and Graphlib
.Of_ocamlgraph. Thanks to these functors, any algorithm written for OCamlGraph can be used on Graphlibs
graph and vice versa.
The Graph
interface provides a richer interface in a Core style. Nodes and Edges implements the Opaque
interface, i.e., they come with Maps, Sets, Hashtbls, etc, (e.g., G.Node.Set
is a set of node for graph implementation, provided by a module named G
). Graphs also implement Printable
interface, that makes them much easier to debug.
Along with graphs, auxiliary data structures are provided, like path to represent paths in graph, tree for representing different graph spannings, partition for graph partitioning, and more.
The Graphlib
module provides a set of generic graph algorithms. Contrary to OCamlGraph, each Graphlib
interface is provided using functions rather than functors. Which makes the interface easier to use, at least in simple cases. Also, Graphlib
heavily uses optional and keyword parameters. For die-hards, many algorithms still have a functor interface.
All Graphlib
algorithms accept a first-class module with graph implementation as a first argument. You can think of this parameter as an explicit type class.
A recommended way to work with Graphlib
is to bind the chosen implementation to some short name, usually G
would be a good choice:
module G = Graphlib.Make(String)(Bool)
This will bind G
to a graph implementation that has string
nodes with edges labeled by values of type bool
.
Graphs of type G.t
could be created using the generic Graphlib
.create function:
let g = Graphlib.create (module G) ~edges:[
"entry", "loop", true;
"loop", "exit", true;
"loop", "loop", false;
] ()
This will create an instance of type G.t
. Of course, it is still possible to use non-generic G.empty
, G.Node.insert
, G.Edge.insert
.
module type Node = sig ... end
module type Edge = sig ... end
Interface that every Graph edge should provide
module type Graph = sig ... end
Graph signature.
a type abbreviation for a packed module, implementing graph interface. Note: this type prenexes only 3 out of 8 type variables, so, sometimes it is not enough.
type edge_kind = [
|
`Tree
edge is a part of a tree
*)|
`Back
back edge
*)|
`Cross
cross edge
*)|
`Forward
forward edge
*) ]
Graph edges classification. For explanations see DFS.
a Tree
representation.
a type representing Frontier
s
a result of partitioning algorithms
a partition Cell
runtime witness of the equivalence class
module Tree : sig ... end
Tree is a particular subtype of a graph for which each node has only one predecessor, and there is only one path between tree root and any other node. Here is an example of a tree:
module Frontier : sig ... end
Frontier maps each node into a possibly empty set of nodes. This is used for representing dominance and post-dominance frontiers.
module Path : sig ... end
Path between two nodes.
module Partition : sig ... end
Result of a set partitioning.
module Group : sig ... end
Group is a non-empty set that is a result of partitioning of an underlying set S
into a set of non-intersecting and non-empty subsets that cover set S
. See Partition
for more information.
module Equiv : sig ... end
Ordinal for representing equivalence. Useful, for indexing elements based on their equivalence.
module type Predicate = sig ... end
A type of modules for filtering graphs. See Graphlib.filtered
or Graphlib.Filtered
module type Isomorphism = sig ... end
Isomorphism
is a bijection between type s
and t
. Useful for creating graph views and mapping graphs. See Graphlib.view
and Graphlib.Mapper
.
class type ['n, 'e, 's] dfs_visitor = object ... end
Consult OCamlGraph library for more information.
module Solution : sig ... end
A solution to a system of fixed-point equations.
module Graphlib : sig ... end
Generic Graph Library