Data structure for a directed bipartite graph

Data structure for a directed bipartite graph

[Orlin Grigorov]

[-- Attachment #1: Type: text/plain, Size: 1210 bytes --]

A bipartite graph is a graph, which has two kinds of nodes, and every node
is connected only to nodes from the other kind.  In other words, if the two
types of nodes are A and B, then there can be an edge between nodes of type
A to nodes of type B (resp. edge from B to A), but never an edge between A
and A, or B and B.

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:

1) an array, which holds all the nodes and the information about them (e.g.
type of the node, other info contained in it)

2) a two dimensional array, indicating existence of an edge between each two
nodes.

Maybe it's worth mentioning that the number of nodes for my particular
purposes will never be more than 200, so I don't think the matrix will take
up too much memory?!

Thank you in advance.   I am in the process of producing my Master's thesis
in Canada, and I am just starting to make an implementation in OCaml, which,
even though newly discovered language by me, for a very short time became my
favorite!

[-- Attachment #2: Type: text/html, Size: 1281 bytes --]

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

[Vincent Aravantinos]

Le 10 oct. 07 à 18:52, Orlin Grigorov a écrit :

> A bipartite graph is a graph, which has two kinds of nodes, and  
> every node is connected only to nodes from the other kind.  In  
> other words, if the two types of nodes are A and B, then there can  
> be an edge between nodes of type A to nodes of type B (resp. edge  
> from B to A), but never an edge between A and A, or B and B.
>
> 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:
>
> 1) an array, which holds all the nodes and the information about  
> them (e.g. type of the node, other info contained in it)
>
> 2) a two dimensional array, indicating existence of an edge between  
> each two nodes.
>
> Maybe it's worth mentioning that the number of nodes for my  
> particular purposes will never be more than 200, so I don't think  
> the matrix will take up too much memory?!
>
> Thank you in advance.   I am in the process of producing my  
> Master's thesis in Canada, and I am just starting to make an  
> implementation in OCaml, which, even though newly discovered  
> language by me, for a very short time became my favorite!

Do you know this:

http://www.lri.fr/~filliatr/ocamlgraph/

?

V.

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

[Jean-Christophe Filliatre]

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