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
