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
