commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From squar...@dia.uniroma3.it
Subject Re: [Graph] On graph weight type(s)
Date Fri, 23 Dec 2011 17:02:37 GMT
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 <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
>



-----------------------------------------
This email was sent using SquirrelMail.
https://email.dia.uniroma3.it
Web Site: http://www.squirrelmail.org


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message