From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.0 required=5.0 tests=HTML_00_10,HTML_MESSAGE, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id E09C2BC6B for ; Wed, 10 Oct 2007 18:52:39 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAEugDEdA6ba5kGdsb2JhbACCcotWAgEBBwQEExEH X-IronPort-AV: E=Sophos;i="4.21,255,1188770400"; d="scan'208";a="17808454" Received: from nf-out-0910.google.com ([64.233.182.185]) by mail4-smtp-sop.national.inria.fr with ESMTP; 10 Oct 2007 18:52:39 +0200 Received: by nf-out-0910.google.com with SMTP id e27so212199nfd for ; Wed, 10 Oct 2007 09:52:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type; bh=qB7SGqJJ53PPvQhXT2i9Vxyb8JYpEfxQO8MSqgqSp54=; b=sWBNPQIqM3WU7hnOWqaqUWPf76fbyH2xSkdFDBcd0TZAKxr2sSGsC9981c8EOoLKm7DbGCQRypmvjuUjrEOJjFDtaStF3VaqfZjvBOUZzI3lxteJ9LZn9MvUe4GeeOMfuThrFv6uYz20EiVNgTHnCeideRHgRP4OZpIdUc+qayc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:mime-version:content-type; b=Pt0s1jU+cGp3McAbmP7QcE9Iz6SjHyFwh1AQwhF6/KaBuqRZA1sTuhWVLGEu1zZN0BsU0Q/5h6yzDfaJC6spuwX6zk+5n7W+zrXFrtDbDNHKsPDiueMG8KXYgVFsKTyB/gtSOL4EyY7ywWxA+DtDu9K9LYH3aKZwUO0MfFiREtc= Received: by 10.82.107.15 with SMTP id f15mr1929878buc.1192035158269; Wed, 10 Oct 2007 09:52:38 -0700 (PDT) Received: by 10.82.120.16 with HTTP; Wed, 10 Oct 2007 09:52:38 -0700 (PDT) Message-ID: Date: Wed, 10 Oct 2007 12:52:38 -0400 From: "Orlin Grigorov" To: caml-list@yquem.inria.fr Subject: Data structure for a directed bipartite graph MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_13804_24417314.1192035158257" X-Spam: no; 0.00; nodes:01 node:01 nodes:01 ocaml:01 node:01 ocaml:01 resp:01 resp:01 graph:01 graph:01 thesis:01 thesis:01 edges:01 edges:01 imperative:01 ------=_Part_13804_24417314.1192035158257 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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! ------=_Part_13804_24417314.1192035158257 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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!
------=_Part_13804_24417314.1192035158257--