Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Data structure for a directed bipartite graph
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-10-10 (16:52)
From: Orlin Grigorov <ogrigorov@g...>
Subject: Data structure for a directed bipartite graph
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

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