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 <simonetripodi@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
> overengineering 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
> <turingatemyhamster@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 wellbehaved 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 springfriendly resource. The
> > bruteforce 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 <squarcel@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 rethink.
> >>>
> >>
> >> 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 "HasPropertyvsProperty" 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
> >> Email address: squarcel@dia.uniroma3.it
> >> Phone: +390657333215
> >> Fax: +390657333612
> >> http://www.dia.uniroma3.it/~**squarcel<
> http://www.dia.uniroma3.it/~squarcel>
> >>
> >>
> >>
> ****
> >> To unsubscribe, email: devunsubscribe@commons.**apache.org<
> devunsubscribe@commons.apache.org>
> >> For additional commands, email: devhelp@commons.apache.org
> >>
> >>
> >
> >
> > 
> > Dr Matthew Pocock
> > Integrative Bioinformatics Group, School of Computing Science, Newcastle
> > University
> > mailto: turingatemyhamster@gmail.com
> > gchat: turingatemyhamster@gmail.com
> > msn: matthew_pocock@yahoo.co.uk
> > irc.freenode.net: drdozer
> > skype: matthew.pocock
> > tel: (0191) 2566550
> > mob: +447535664143
>
> 
> To unsubscribe, email: devunsubscribe@commons.apache.org
> For additional commands, email: devhelp@commons.apache.org
>
>

Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
