commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
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}}).


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


Mime
View raw message