commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [Graph] On graph weight type(s)
Date Thu, 22 Dec 2011 17:14:23 GMT
Hi James,
welcome in [graph] :)

DirectGraph is a DataStructure, Dijkstra is an algorithm and would be
better in therms of design keeping algorithms implementation separated
from DS.

Moreover, DirectGraph is an interface - users can provide their own
implementations - so no way to provide complete implementations
there...

Best,
-Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Thu, Dec 22, 2011 at 6:06 PM, James Ring <sjr@jdns.org> wrote:
> On Dec 22, 2011 8:39 AM, "Claudio Squarcella" <squarcel@dia.uniroma3.it>
> wrote:
>>
>> 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.
>
> Just a disinterested third party, but wouldn't this method be better as a
> non-static method on DirectedGraph? The signature is much nicer then.
>
>>
>> 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
>>

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


Mime
View raw message