Return-Path: 
 <dev-return-132127-apmail-commons-dev-archive=commons.apache.org@commons.apache.org>
X-Original-To: apmail-commons-dev-archive@www.apache.org
Delivered-To: apmail-commons-dev-archive@www.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
	by minotaur.apache.org (Postfix) with SMTP id B4ECC9A4B
	for <apmail-commons-dev-archive@www.apache.org>;
 Thu, 22 Dec 2011 16:39:44 +0000 (UTC)
Received: (qmail 51100 invoked by uid 500); 22 Dec 2011 16:39:44 -0000
Delivered-To: apmail-commons-dev-archive@commons.apache.org
Received: (qmail 51023 invoked by uid 500); 22 Dec 2011 16:39:44 -0000
Mailing-List: contact dev-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:dev-help@commons.apache.org>
List-Unsubscribe: <mailto:dev-unsubscribe@commons.apache.org>
List-Post: <mailto:dev@commons.apache.org>
List-Id: <dev.commons.apache.org>
Reply-To: "Commons Developers List" <dev@commons.apache.org>
Delivered-To: mailing list dev@commons.apache.org
Received: (qmail 51015 invoked by uid 99); 22 Dec 2011 16:39:44 -0000
Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 22 Dec 2011 16:39:44 +0000
X-ASF-Spam-Status: No, hits=-0.0 required=5.0
	tests=SPF_HELO_PASS,SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (nike.apache.org: domain of squarcel@dia.uniroma3.it
 designates 193.205.219.56 as permitted sender)
Received: from [193.205.219.56] (HELO mail3.dia.uniroma3.it) (193.205.219.56)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 22 Dec 2011 16:39:37 +0000
Received: from hyper.local (unknown [192.168.161.201])
	(using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits))
	(No client certificate requested)
	(Authenticated sender: squarcel)
	by mail3.dia.uniroma3.it (Postfix) with ESMTPSA id 5C30D64A96
	for <dev@commons.apache.org>; Thu, 22 Dec 2011 17:39:16 +0100 (CET)
Message-ID: <4EF35D33.4010202@dia.uniroma3.it>
Date: Thu, 22 Dec 2011 17:39:15 +0100
From: Claudio Squarcella <squarcel@dia.uniroma3.it>
Organization: Roma Tre University
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7;
 rv:8.0) Gecko/20111105 Thunderbird/8.0
MIME-Version: 1.0
To: dev@commons.apache.org
Subject: Re: [Graph] On graph weight type(s)
References: <4EDC0593.5070200@dia.uniroma3.it>
 <4EE545AE.1020906@dia.uniroma3.it>
 <CALznzY6GRWLFthfTpk=4hij3q76p+-a9E5U1FDBdGiBJX6kUtQ@mail.gmail.com>
 <CALznzY6VGNUe3ZP6aCuHzE_qNNE1LPj+hhiP3hGMXw7jYjXnRw@mail.gmail.com>
 <4EE61054.3090906@dia.uniroma3.it>
 <CALznzY7py=Df9E=-LDc+OwTmqL17wpwkrgzXuids94mpNCo5gw@mail.gmail.com>
 <CAAqLGLOXfSKq3NS8VFE9Zv=XizpRr2OjUx2mEV303FHvkPxcKA@mail.gmail.com>
 <4EE78CEC.3090403@dia.uniroma3.it>
 <CALznzY6Vj-4fGsHeoBQstwRWQ6-Tbnk9uUskEo9EBE7wj3WwEw@mail.gmail.com>
 <4EE895F4.9050802@dia.uniroma3.it>
 <CALznzY7oh4x5toZqpZSD5t0HyGXeBujy5-SSaxURcU+UWj5ApA@mail.gmail.com>
 <CAHQS_exHiJjMbnsxeKpqfPCR11WCfgh+QyZhecJ95RhfpV9kVw@mail.gmail.com>
 <CALznzY7Ri5q0=fa1qYbCYPN=gyG1yW0vt05G7zwfiFt5CyJryA@mail.gmail.com>
 <4EE9F615.6020401@dia.uniroma3.it>
In-Reply-To: <4EE9F615.6020401@dia.uniroma3.it>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Virus-Checked: Checked by ClamAV on apache.org

Hi,

> I highly appreciated the last contributions (thanks guys!) but I also 
> agree on this point, so let's start from the end.
> I think that, no matter what underlying structure we come up with, the 
> user should be able to specify e.g. a weighted edge with something like
>
> public class MyEdge implements Edge, Weighted<Double> { ... }
>
> and be able to immediately use it as an input for all the algorithms, 
> without extra steps required. So the average user is happy, while 
> "graph geeks" can dig into advanced capabilities and forge their 
> personalized weights :)
> I hope we all agree on this as a first step. Complexity comes after.
>
> I'll take my time as well to re-think.

I did think and code a bit more. First of all please take a look at the 
updated code: Weighted<W> is an interface (weight W can be any type) and 
all the algorithms require edges to implement Weighted<Double> for now 
-- we did not break it that much ;)

About the "HasProperty-vs-Property" question (as in Comparable vs 
Comparator, MonoidElement vs Monoid, etc) I would go for the second one 
only. That is, external classes handle all operations on weights. 
Downside: the # of method parameters would increase linearly with the 
number of properties, but I can live with that (how many properties 
would weights have anyway?). On the other hand we have a neat interface 
for each property/class (Zero, Semigroup, Monoid, Ordering or 
Comparator, etc) and one clean, generic implementation for each 
algorithm. Dijkstra's signature becomes something like:

public static <V extends Vertex, W, WE extends WeightedEdge<W>, G 
extends DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G 
graph, V source, V target, Monoid<W> weightMonoid, Comparator<W> 
weightComparator )

Scary uh? But wait, default implementations for Double, Integer, etc. 
are way easier. E.g. Dijkstra's shortcut for Double:

public static <V extends Vertex, WE extends WeightedEdge<Double>, G 
extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> 
findShortestPath( G graph, V source, V target )
{
     return findShortestPath(graph, source, target, new DoubleMonoid(), 
new DoubleComparator());
}

where DoubleMonoid and DoubleComparator are part of the library.


If you guys are fine with this, I'm ready to try and patch [graph] with 
a Christmas gift :)
Claudio

-- 
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squarcel@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org