commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Ring <>
Subject Re: [Graph] On graph weight type(s)
Date Thu, 22 Dec 2011 17:06:53 GMT
On Dec 22, 2011 8:39 AM, "Claudio Squarcella" <>
> 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
> }
> 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:
> Phone: +39-06-57333215
> Fax: +39-06-57333612
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message