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 <s...@jdns.org> wrote: > 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 >> --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
