Hey Simone,
On 12/12/2011 18:35, Simone Tripodi wrote:
Hi James!
yes, actual Dijkstra implementation[1] uses Double number to
accumulating the total path weights...
I think Having an accumulator would be helpful! How do you would
modify the current implementation - even with pseudo-code?
trying to put it all together (thanks James, Matthew):
* Weighted<W> is fully generic without restrictions on the type of
weight W
* different properties of weights are specified with interfaces: e.g.
Summable, HasZero, Comparable...
* each algorithm requires the weights to implement one or more of the
above interfaces based on needs, and only works with related methods
abstracting from the actual type of weight. For example sum(W
weight) for Summable.
Now, IFF you like that... what shall we do with Double, Integer, etc?
Claudio
TIA, all the best,
-Simo
[1]
https://svn.apache.org/repos/asf/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Mon, Dec 12, 2011 at 6:27 PM, James Carman
<ja...@carmanconsulting.com> wrote:
Why do you need doubles for Dijkstra? Accumulating the total path
weights? Why not introduce an Accumulator interface?
On Dec 12, 2011 9:32 AM, "Claudio Squarcella"<squar...@dia.uniroma3.it>
wrote:
Hi,
On 12/12/2011 05:39, James Carman 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.
ok it definitely makes sense, thanks :)
The thing is: in case the weight is actually a number I would really like
to keep it simple on the user side, i.e. it should be usable with something
like {{Weighted<Double>}}, or {{Weighted<Integer>}}, etc. On the other
hand, some of the implemented algorithms would need to expose one method
per number type: e.g. Dijkstra (which also sums weights, so it needs
numbers) would need a method for Doubles, one for Integers, etc.
Alternatively one could use the abstract class {{Number}} once for all --
but that would not make things easier, because there is no way to do maths
directly with it (see e.g. http://stackoverflow.com/**
questions/2721390/how-to-add-**two-java-lang-numbers<http://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers>
).
Summing up:
* {{public interface Weighted<W>}} with method {{public W getWeight()}}
* weighted "things" ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdge<E,W> extends
Edge<E>, Weighted<W>}}
* each algorithm specifies the type of weight needed. E.g. Prim would
only require edges to have {{Comparable}} weights or a
{{Comparator}}, while Dijkstra needs edges with weights as real
numbers (maybe just {{Double}} for now), etc.
How does that sound?
Ciao,
Claudio
On Sun, Dec 11, 2011 at 8:01 PM, James Carman
<ja...@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<squar...@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<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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~**squarcel<http://www.dia.uniroma3.it/~squarcel>
------------------------------**------------------------------**
---------
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.org<dev-unsubscr...@commons.apache.org>
For additional commands, e-mail: dev-h...@commons.apache.org
------------------------------**------------------------------**
---------
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.org<dev-unsubscr...@commons.apache.org>
For additional commands, e-mail: dev-h...@commons.apache.org
--
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<http://www.dia.uniroma3.it/~squarcel>
------------------------------**------------------------------**---------
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.org<dev-unsubscr...@commons.apache.org>
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--
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
