commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [Graph] On graph weight type(s)
Date Mon, 26 Dec 2011 21:09:49 GMT
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,  <squarcel@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 <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
>

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


Mime
View raw message