From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pA1003X6023233 for ; Tue, 1 Nov 2011 01:00:07 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqECAFY2r05KfVK2kGdsb2JhbABDhHeVL48ICCIBAQEBCQkNBxQEIYFyAQEBAQIBEgIPHQEbFgYBAQMBCwYFCw0CAgUWCwICCQMCAQIBEREBBQEcEwEHAQEeh2AClzAKiwxHgmCFGz2IcAIFCoEmhj6BFASUDoUtgSyGWj2Dbw X-IronPort-AV: E=Sophos;i="4.69,435,1315173600"; d="scan'208";a="115924571" Received: from mail-wy0-f182.google.com ([74.125.82.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Nov 2011 00:59:55 +0100 Received: by wyh11 with SMTP id 11so3793494wyh.27 for ; Mon, 31 Oct 2011 16:59:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=S7UCY3OQKjMbR3VI4r1FshfC/TPbL6N5Sun3KiwsVzQ=; b=MbxZqTWkAxPbB4dPCMCXDTNR9O4V3J0nYeH9NeraZlE1KIwArEHOZUx7EkQOht192n pNn4kSxjNnQYt9HtmZeArojcFUeQiNF04DgQVzXT77Kwmb2eQKU2GezUrnnqGHeCjf+h UYPckNAekba0steMFwU4mE+/p6xJ7ME3hB0C0= Received: by 10.227.57.67 with SMTP id b3mr20829885wbh.9.1320105594918; Mon, 31 Oct 2011 16:59:54 -0700 (PDT) Received: from [192.168.1.64] (94-193-173-247.zone7.bethere.co.uk. [94.193.173.247]) by mx.google.com with ESMTPS id ei16sm35285319wbb.21.2011.10.31.16.59.52 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 31 Oct 2011 16:59:53 -0700 (PDT) Message-ID: <4EAF3677.1050301@gmail.com> Date: Mon, 31 Oct 2011 23:59:51 +0000 From: Toby Kelsey User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.23) Gecko/20110921 Lightning/1.0b2 Thunderbird/3.1.15 MIME-Version: 1.0 To: caml-list@inria.fr CC: lykimq@gmail.com References: In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Compute the equivalence classes On 31/10/11 15:36, Ly Kim Quyen wrote: > Dear group, > > I have an question about data structure and types. I have a function calculates > transitive closure of relation represented as an adjacency matrix > > let trans_closure (m: 'a array array) : 'a array array = > let last_cols = length m - 1 in > for k = 0 to last_cols do > for i = 0 to last_cols do > for j = 0 to last_cols do > m.(i).(j) <- m.(i).(j) || (m.(i).(k) && m.(k).(j)) > done; > done; > done; > m > ;; I may have misunderstood how you are using this, but I'm not sure this finds the transitive closure since you iterate over k just once in one direction. You might need to repeat this until no more relations are found. Since you're using logical operators on elements, your 'a type must be boolean (unless you override the operators). > (* transpose matrix A is the matrix A' formed by turning rows into > columns and vice versa: (A')i,j = Aj,i.*) > let transpose (m: 'a array array) : 'a array array = > let tc = trans_closure m in > let last_cols = length m - 1 in > for i = 0 to last_cols do > for j = 0 to last_cols do > tc.(j).(i) <- tc.(i).(j) > done; > done; > tc > ;; This visits each position twice and is not symmetric, so for example (a b) (c d) becomes (a b) (b d) To transpose you want to visit each non-diagonal entry once and swap, I.E. (untested): for i = 0 to last_cols-1 do for j = i+1 to last_cols do let tmp = tc.(i).(j) in begin tc.(i).(j) <- tc.(j).(i); tc.(j).(i) <- tmp end done; done; > I would like to compute equivalence classes, it is disjoint between matrix > transitive closure and matrix transpose. I would like it returns for me a > new list with the type: list of list [[]] > > I have a function convert 'a array array to 'a list list > > let to_list (m : 'a array array) : 'a list list = > List.map to_list (to_list m) > > let eq_class (m: 'a array array) : 'a list list = > let lst = length m - 1 in > for i = 0 to lst do > for j = 0 to lst do > let a = tc.(i).(j) && trans.(i).(j) in > if a > then > ??? > > I'm stuck here, I don't know how I can add the result "a" into the new list > of list. I think I should create a new list with type 'a list list, but I > don't know where I should write it? How do you want to represent your equivalence class? You could have a list of (i,j) pairs for each class, or perhaps a more complex data structure. Once you choose the data structure that will help determine what you need to do. In any case looping once over the matrix probably can't compute it. You will have to follow the equivalence relations to find all equivalent entries, so you might need a recursive 'flood-fill' style algorithm to find all the entries. > Thank you for helping me understand and give me some advises. > > Best regards, > Gwen Regards, Toby