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

[Vincent Aravantinos <vincent.aravantinos@yahoo.fr>]

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.