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=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id BE4CABC6B for ; Wed, 10 Oct 2007 20:34:28 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAEK3DEfZDAs+hWdsb2JhbACOSgEBAQgEBg8TBw X-IronPort-AV: E=Sophos;i="4.21,255,1188770400"; d="scan'208";a="2838315" Received: from smtp008.mail.ukl.yahoo.com ([217.12.11.62]) by mail2-smtp-roc.national.inria.fr with SMTP; 10 Oct 2007 20:34:28 +0200 Received: (qmail 65084 invoked from network); 10 Oct 2007 18:34:27 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.fr; h=Received:X-YMail-OSG:In-Reply-To:References:Mime-Version:Content-Type:Message-Id:Cc:Content-Transfer-Encoding:From:Subject:Date:To:X-Mailer; b=ggSdZH1pgOV5YFv71d8V9PtbJyRmyaWEMoUPEKyWeUmnCqBcONxHqWUj40f5IaJpcTY/LEOXHKoKV6h2qEZHds8kMHp+pfFroBQEtWcuFdMyOO3n0TwRmcZi/OLXVi34V5b5Q2jCUFgGGWcK7QKqunzaOmRy/GoYzREI8cuk8+E= ; Received: from unknown (HELO ?192.168.0.11?) (vincent.aravantinos@82.229.199.66 with plain) by smtp008.mail.ukl.yahoo.com with SMTP; 10 Oct 2007 18:34:27 -0000 X-YMail-OSG: 13EskmsVM1nrGAtMlxF4AnZEwETm8lBDGaHp9aKMY3NozBTRWdN7UZi2cOHm2XH4oXKEn.KIv6MiH4YoRvFDlhP7EFDYx.pGnJnKqH0lSZQ8CIHk In-Reply-To: References: Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: <4EC8DB3A-AE8B-4141-A87A-1BA4289A6313@yahoo.fr> Cc: caml-list@yquem.inria.fr Content-Transfer-Encoding: quoted-printable From: Vincent Aravantinos Subject: Re: [Caml-list] Data structure for a directed bipartite graph Date: Wed, 10 Oct 2007 20:34:25 +0200 To: "Orlin Grigorov" X-Mailer: Apple Mail (2.752.2) X-Spam: no; 0.00; nodes:01 node:01 nodes:01 ocaml:01 node:01 ocaml:01 lri:01 filliatr:01 resp:01 graph:01 graph:01 caml-list:01 thesis:01 edges:01 imperative:01 Le 10 oct. 07 =E0 18:52, Orlin Grigorov a =E9crit : > A bipartite graph is a graph, which has two kinds of nodes, and =20 > every node is connected only to nodes from the other kind. In =20 > other words, if the two types of nodes are A and B, then there can =20 > be an edge between nodes of type A to nodes of type B (resp. edge =20 > 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 =20= > to store such graph, and also to allow me easy access to elements, =20 > as well as adding new nodes and edges (therefore, the structure =20 > 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 =20 > them (e.g. type of the node, other info contained in it) > > 2) a two dimensional array, indicating existence of an edge between =20= > each two nodes. > > Maybe it's worth mentioning that the number of nodes for my =20 > particular purposes will never be more than 200, so I don't think =20 > the matrix will take up too much memory?! > > Thank you in advance. I am in the process of producing my =20 > Master's thesis in Canada, and I am just starting to make an =20 > implementation in OCaml, which, even though newly discovered =20 > language by me, for a very short time became my favorite! Do you know this: http://www.lri.fr/~filliatr/ocamlgraph/ ? V.=