Hi Claudio! just make your proposal and attach it to a jira Issue :) Hope to hear from you soon, all the best! -Simo
http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Fri, Dec 23, 2011 at 6:02 PM, <squar...@dia.uniroma3.it> wrote: > 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 > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
