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://twitter.com/simonetripodi
http://www.99soft.org/
On Mon, Dec 12, 2011 at 3:27 PM, Matthew Pocock
<turingatemyhams...@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
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
