On Dec 22, 2011 8:39 AM, "Claudio Squarcella" <squar...@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: squar...@dia.uniroma3.it > Phone: +39-06-57333215 > Fax: +39-06-57333612 > http://www.dia.uniroma3.it/~squarcel > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org >