commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Matthew Pocock <turingatemyhams...@gmail.com>
Subject Re: [Graph] On graph weight type(s)
Date Fri, 23 Dec 2011 11:32:27 GMT
On 23 December 2011 10:38, Simone Tripodi <simonetripodi@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
> <turingatemyhamster@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 <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
> >> 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
> >> <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 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 <
> 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 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: squarcel@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-unsubscribe@commons.apache.org>
> >> >> For additional commands, e-mail: dev-help@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, e-mail: dev-unsubscribe@commons.apache.org
> >> For additional commands, e-mail: dev-help@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, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message