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, 12 Dec 2011 14:34:14 GMT
Terrific feedback Matthew, thanks a lot!
and glad to see researchers here :)
best,
-Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Mon, Dec 12, 2011 at 3:27 PM, Matthew Pocock
<turingatemyhamster@gmail.com> wrote:
> Hi,
>
> I have tended to find that edge weights always follow the following laws:
>
> They have a monoid:
>  There is a zero (0) constant and a |+| operator for combining two weights.
> They have an equivalence and (compatible) ordering relations (>, =):
> The ordering is compatible with the monoid. For example,
>  a |+| 0 = 0
>  a |+| b >= a
>  a |+| b = b |+| a
>  a >= 0
>  a != 0, b != 0 => a |+| b > a
>
> Taken together, the algorithms for things like shortest-path or
> weighted-k-neighbourhood can all be expressed, abstracted away from the
> weight datatype, the operations for combining weights, and the operations
> for comparing weights.
>
> If you choose your ordering then you can derive the compatible min monoid
> where a |+| b = min(a, b). If you use the natural ordering on numbers then
> you commonly use the monoids (0, +) or (1, *).
>
> However, I've had cases where the individual weights and accumulated
> path-traversal weights are complex structures. This isn't a problem, as
> long as there's a zero and |+| for these 'weight' structures, and a
> well-behaved ordering over these structures.
>
> On 12 December 2011 04:39, James Carman <james@carmanconsulting.com> wrote:
>
>> Sorry, I was on my phone before when I sent that.  Let me elaborate a
>> bit more.  I would just allow the weights to be of any type.  However,
>> you can create two different types of scenarios where you either use a
>> Comparable derivative or you use whatever you want, but you have to
>> supply a custom Comparator.
>>
>> On Sun, Dec 11, 2011 at 8:01 PM, James Carman
>> <james@carmanconsulting.com> wrote:
>> > I wouldn't restrict the weight to Comparable.  What if the user wanted to
>> > provide their own Comparator?
>> >
>> > On Dec 11, 2011 7:07 PM, "Claudio Squarcella" <squarcel@dia.uniroma3.it>
>> > wrote:
>> >>
>> >> Hi all,
>> >>
>> >> I explored a bit more the (rather philosophical) dilemma that came from
>> a
>> >> thread from last week, quoted below
>> >>>
>> >>> One step further. A weight is not necessarily a double: in some cases
>> not
>> >>> even a number, but rather a "comparable" of some sort. So I would
>> suggest to
>> >>> make use of generics in some way, possibly the smartest. Suggestions
>> are
>> >>> welcome :-)
>> >>
>> >>
>> >> The question is: *what do we mean by weight when dealing with graphs?*
>> >>
>> >> "Real number" is a standard answer in graph theory: see, e.g.,
>> >> http://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf (pag.
>> 15).
>> >> What we have now in the code is a {{getWeight()}} method that returns a
>> >> double. That serves well for all the algorithms currently implemented,
>> and
>> >> probably for many more to come. However it is also true that:
>> >>
>> >>  * some domains of interest and/or algorithms might be more restrictive
>> >>   on the type and sign of "real number" for the weights: integers,
>> >>   non-negative rationals, etc.
>> >>  * strictly speaking, the basic operations associated with weights are
>> >>   usually just a few. Comparison and sum are enough at least for the
>> >>   algorithms implemented so far in the project (please correct me if I
>> >>   am wrong). Maybe scaling? Additive inverse?
>> >>  * each algorithm is aware of the subset of required operations. E.g.
>> >>   Prim's algorithm for minimum spanning trees only requires edge
>> >>   weights to be comparable, so they could even be Strings or whatever...
>> >>  * some very abstract user might want to use a new class (not
>> >>   necessarily a number) as a weight, provided that it meets the
>> >>   requirements of the domain.
>> >>
>> >> So here is a high-level view of what I propose:
>> >>
>> >>  * the basic weight is nothing more than a {{Comparable}}, which is
>> >>   hopefully generic enough;
>> >>  * where needed, algorithms define more specific constraints on the
>> >>   input graph in their signature (e.g. Dijkstra can use {{Double}}).
>> >>
>> >>
>> >> Looking forward for comments,
>> >> 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
>> >>
>> >>
>> >> ---------------------------------------------------------------------
>> >> 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
>>
>>
>
>
> --
> 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


Mime
View raw message