commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <>
Subject Re: [Graph] On graph weight type(s)
Date Thu, 22 Dec 2011 16:39:15 GMT

> 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 Squarcella
PhD student at Roma Tre University
E-mail address:
Phone: +39-06-57333215
Fax: +39-06-57333612

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message