Hi, I like the idea of external weights. Actually that could work for other properties of the graph as well. I see a couple of use cases there.
As for lazy implementations, I like them too but with much less priority for now. Anyway, first things first: guys should I infer an implicit 'yes' from your answers and go ahead with the proposed change for weights? Anyone else has a word on this? I am just applying some lazy pattern here -- discuss before coding ;) Claudio > On 23 December 2011 10:38, Simone Tripodi <simonetrip...@apache.org> > wrote: > >> Hi Matthew! >> > > >> Usually algorithms (like Dijkstra) already have clear enunciates and >> steps are known, so we could safety expose 1 APIs that hide all that >> details to clients wrapping your proposals. >> > > That's what façades are for. I totally agree with providing users with > utility methods that hide all the guts. > > >> >> WDYT? Thanks again!!! >> -Simo >> >> http://people.apache.org/~simonetripodi/ >> http://simonetripodi.livejournal.com/ >> http://twitter.com/simonetripodi >> http://www.99soft.org/ >> >> >> >> On Fri, Dec 23, 2011 at 10:44 AM, Matthew Pocock >> <turingatemyhams...@gmail.com> wrote: >> > Hi Simo, >> > >> > I guess the 5 minutes to run example would be: >> > >> > ShortestPathFunction.dijkstra >> > .makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble) >> > .findShortestPath(source, target); >> > >> > I was assuming that there would be standard pallets of all the >> strategies >> > available statically in the obvious places. Actually, now I see the >> code >> > written out in full like that, I'd perhaps consider renaming >> makeResult >> to >> > `calculate` or `prepare` or some other verb. >> > >> > Matthew >> > >> > On 23 December 2011 08:47, Simone Tripodi <simonetrip...@apache.org> >> wrote: >> > >> >> Hi Matthew! >> >> >> >> at a first looks it is really interesting, just give me the time to >> >> digest because at the same time I had the feeling of a little >> >> over-engineering activity, I am worried that "5 minutes to run" users >> >> would find it not so immediate. >> >> >> >> Thanks for providing stuff to learn from! >> >> All the 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:25 PM, Matthew Pocock >> >> <turingatemyhams...@gmail.com> wrote: >> >> > Hi, >> >> > >> >> > Just thought I'd throw something out here. My experience is that I >> often >> >> > take the same graph (as in the exact same data, same objects) but >> at >> >> > different times want to use different weights. So, rather than >> having >> >> Edge >> >> > extend Weighted<W>, I'd factor weights out into their own >> interface: >> >> > >> >> > /** >> >> > * An edge weight function. >> >> > * >> >> > * note: perhaps this should more generally just be a Function1<A, >> B>, if >> >> > we have such a thing handy. >> >> > * >> >> > * @tparam E edge type >> >> > * @tparam W weight type >> >> > */ >> >> > public interface EdgeWeight<E, W> { >> >> > public W getWeight(E: Edge); >> >> > } >> >> > >> >> > /** >> >> > * A combination of a monoid and comparator that satisfy >> monotinicity >> of >> >> > the addition operation with respect to the comparator. >> >> > * >> >> > * âa: m.compare(m.zero, a) <= 0 >> >> > * âa,b: m.compare(a, m.append(a, b)) <= 0 >> >> > */ >> >> > public interface Monotonic<W> extends Monoid<W>, Comparator<W> >> >> > >> >> > Also, some algorithms calculate all shortest paths at once, while >> others >> >> > calculate them individually and independently. It's probably even >> >> possible >> >> > to calculate some lazily. So, the interfaces for shortest paths >> should >> >> > decouple setting up a strategy for all shortest paths from an >> object >> that >> >> > can be used to fetch a specific shortest path. >> >> > >> >> > /** >> >> > * An algorithm for finding shortest paths between vertices of a >> graph, >> >> > given some edge weighting function and >> >> > * a well-behaved combinator for edges between connected vertices. >> >> > */ >> >> > public interface ShortestPathFunction<V extends Vertex, E extends >> >> Edge<E>, >> >> > G extends DirectedGraph<V, E>, W> { >> >> > public ShortestPathResult<V, E, W> makeResult(G graph, >> EdgeWeight<E, >> W> >> >> > weighting, Monotonic<W> combineWith); >> >> > } >> >> > >> >> > /** >> >> > * The shortest paths between vertices in a graph. >> >> > */ >> >> > public interface ShortestPathResult<V extends Vertex, E extends >> Edge<E>, >> >> W> >> >> > { >> >> > public WeightedPath<V, E, W> findShortestPath(V source, V target); >> >> > } >> >> > >> >> > How does that look? You can then have standard implementations of >> these >> >> > things in some static utility class or a spring-friendly resource. >> The >> >> > brute-force algorithms that compute all paths at once would do all >> the >> >> work >> >> > in makeResult() and simply store this in some state within the >> returned >> >> > ShortestPathResult. Those that calculate individual pairs on the >> fly >> (or >> >> > all shortest paths from some vertex) would capture state in >> makeResult() >> >> > and perform the actual computation in findShortestPath(). >> >> > >> >> > Matthew >> >> > >> >> > On 22 December 2011 16:39, 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. >> >> >> >> >> >> >> >> >> 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< >> >> http://www.dia.uniroma3.it/~squarcel> >> >> >> >> >> >> >> >> >> >> >> >> ------------------------------**------------------------------**--------- >> >> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org< >> >> dev-unsubscr...@commons.apache.org> >> >> >> For additional commands, e-mail: dev-h...@commons.apache.org >> >> >> >> >> >> >> >> > >> >> > >> >> > -- >> >> > Dr Matthew Pocock >> >> > Integrative Bioinformatics Group, School of Computing Science, >> Newcastle >> >> > University >> >> > mailto: turingatemyhams...@gmail.com >> >> > gchat: turingatemyhams...@gmail.com >> >> > msn: matthew_poc...@yahoo.co.uk >> >> > irc.freenode.net: drdozer >> >> > skype: matthew.pocock >> >> > tel: (0191) 2566550 >> >> > mob: +447535664143 >> >> >> >> --------------------------------------------------------------------- >> >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> >> For additional commands, e-mail: dev-h...@commons.apache.org >> >> >> >> >> > >> > >> > -- >> > Dr Matthew Pocock >> > Integrative Bioinformatics Group, School of Computing Science, >> Newcastle >> > University >> > mailto: turingatemyhams...@gmail.com >> > gchat: turingatemyhams...@gmail.com >> > msn: matthew_poc...@yahoo.co.uk >> > irc.freenode.net: drdozer >> > skype: matthew.pocock >> > tel: (0191) 2566550 >> > mob: +447535664143 >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> For additional commands, e-mail: dev-h...@commons.apache.org >> >> > > > -- > Dr Matthew Pocock > Integrative Bioinformatics Group, School of Computing Science, Newcastle > University > mailto: turingatemyhams...@gmail.com > gchat: turingatemyhams...@gmail.com > msn: matthew_poc...@yahoo.co.uk > irc.freenode.net: drdozer > skype: matthew.pocock > tel: (0191) 2566550 > mob: +447535664143 > ----------------------------------------- This email was sent using SquirrelMail. https://email.dia.uniroma3.it Web Site: http://www.squirrelmail.org --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
