# commons-dev mailing list archives

##### Site index · List index
Message view
Top
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject [Graph] On graph weight type(s)
Date Mon, 12 Dec 2011 00:07:10 GMT
```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}}).

Claudio

--
Claudio Squarcella
PhD student at Roma Tre University