# commons-dev mailing list archives

##### Site index · List index
Message view
Top
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [Graph] On graph weight type(s)
Date Mon, 12 Dec 2011 14:38:22 GMT
```

On 12/12/2011 15:34, Simone Tripodi wrote:
> Terrific feedback Matthew, thanks a lot!
> and glad to see researchers here :)

Thank you indeed :)
I'll take that as valuable input.

Claudio

> best,
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> 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.
>>
>>
--
Claudio Squarcella
PhD student at Roma Tre University