Re: [Caml-list] Data structure for a directed bipartite graph

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

Hi,

Orlin Grigorov writes:
 > A bipartite graph is a graph [...]
 > So, I was thinking about a data structure in OCaml, in which I want to store
 > such graph, and also to allow me easy access to elements, as well as adding
 > new nodes and edges (therefore, the structure would be imperative, that is,
 > will have a state). So, how about this:

As already mentionned by somebody else, there exists at least one
graph library for ocaml at http://ocamlgraph.lri.fr/

It provides several data structures for graph, including matrix
representations as the one you are mentioning, but also others more
suitable for sparse graphs.

Note that the ability to add new nodes and new edges does not enforce
the use of an imperative data structure. A persistent one is equally
fine; you simply get a new graph when you add a node or an edge, the
previous one being unchanged (with a logarithmic time and space
overhead, typically). 

Ocamlgraph makes heavy use of ocaml module system to provide great
genericity and thus may appear as somewhat heavy for a newcomer. You
should start by having a look at module Pack, which provides an easy
access to the library (imperative data structure with nodes and edges
labeled with integers; see http://ocamlgraph.lri.fr/doc/Pack.html

Regarding the ability to attach information to nodes (or edges) you
may indeed use an additional data structure for that purpose (a hash
table, typically) but you may also use ocamlgraph to define your own
graph data structure with any kind of information associated to nodes
and edges. That is precisely why ocamlgraph was designed in a highly
generic way. See ocamlgraph's FAQ for an example of such instantiation.

Note that Ocamlgraph's documentation includes an article "Designing a
Generic Graph Library using ML Functors" which can be seen as an
introduction to ocamlgraph's design.

Hope this helps,
-- 
Jean-Christophe