You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Claudio Squarcella <sq...@dia.uniroma3.it> on 2011/12/12 01:07:10 UTC
[Graph] On graph weight type(s)
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
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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
> <tu...@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: 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
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Terrific feedback Matthew, thanks a lot!
and glad to see researchers here :)
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
<tu...@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.
>
> On 12 December 2011 04:39, James Carman <ja...@carmanconsulting.com> 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.
>>
>> 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" <sq...@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 (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
>> >>
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Matthew Pocock <tu...@gmail.com>.
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.
On 12 December 2011 04:39, James Carman <ja...@carmanconsulting.com> 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.
>
> 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" <sq...@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 (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
> >>
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
Well if you wanna get all mathematical about it, what you're actually
talking about is in addition operation. In functor-speak it would be a
binary function.
On Dec 12, 2011 12:35 PM, "Simone Tripodi" <si...@apache.org> 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?
> 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" <sq...@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<sq...@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: squarcel@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-unsubscribe@commons.apache.org>
> >>>>> For additional commands, e-mail: dev-help@commons.apache.org
> >>>>>
> >>>>> ------------------------------**------------------------------**
> >>> ---------
> >>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> dev-unsubscribe@commons.apache.org>
> >>> For additional commands, e-mail: dev-help@commons.apache.org
> >>>
> >>>
> >> --
> >> 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<
> http://www.dia.uniroma3.it/~squarcel>
> >>
> >>
> >>
> ------------------------------**------------------------------**---------
> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> dev-unsubscribe@commons.apache.org>
> >> For additional commands, e-mail: dev-help@commons.apache.org
> >>
> >>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
>> 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.
> this is interesting - at a first read looked like an over engineered
> layer, but it perfectly model the weight domain... can you provide a
> patch containing such classes and see them in action in current
> implemented algos?
of course I can, hopefully later this week.
And you're right, it sounds over-engineered. But it also gives much more
freedom to the end user, so maybe in the future someone could say
"thanks" ;)
>> Now, IFF you like that... what shall we do with Double, Integer, etc?
> uhm I think we can get rid of them, this is something depending on the
> domain in which algorithms are applied.
Well, ideally the user should be able to use seamlessly all the wrappers
for primitive number types: i.e., a graph with edges that implement
Weighted<Double> should just work the way it is as an input for
Dijkstra. But of course Double & co are "legacy" that have nothing to do
with our fresh interfaces (Summable & co). So there are at least two
alternatives:
* The user has to wrap primitive types into classes that implement the
appropriate interfaces, in order to "speak the same language" of the
algorithm implementations. Some of these classes could of course be
provided in the library (e.g. DoubleWeight, IntegerWeight).
* The algorithms offer additional signatures for the same method that
are "legacy-compatible" to some extent (e.g. only for Double and
Integer), and then take care of the conversion internally.
I would go for the second one, because 'ignorance is bliss' for the user :)
Comments?
Claudio
>
> Looking forward to hear from you soon!
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
--
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
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hola Claudio!
On Tue, Dec 13, 2011 at 6:35 PM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> Hey Simone,
>
>
>
> 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.
>
this is interesting - at a first read looked like an over engineered
layer, but it perfectly model the weight domain... can you provide a
patch containing such classes and see them in action in current
implemented algos?
> Now, IFF you like that... what shall we do with Double, Integer, etc?
>
uhm I think we can get rid of them, this is something depending on the
domain in which algorithms are applied.
Looking forward to hear from you soon!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi all guys,
thanks a lot for the very hight valuable feedbacks, impressive,
without any doubt.
IMHO Matthew's stuff should be absolutely part of a commons component,
if they don't find a home in [graph] at 100%, they should be included
in [math]!!!
Discrete math has always been one of my preferred math classes and
having Matthew contributing on that topic is something I have to take
advantage to increase my knowledge :P
I personally need to digest all that proposals to elaborate mine as
well and share with you.
Thanks all again!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Dec 15, 2011 at 1:37 PM, Matthew Pocock
<tu...@gmail.com> wrote:
> Hi,
>
> On 15 December 2011 11:35, James Carman <ja...@carmanconsulting.com> wrote:
>
>
>> public interface BinaryOperation<T>
>> {
>> public T execute(T operand1, T operand2);
>> }
>>
>> Perhaps we can come up with an interface that combines the two
>> aspects. I'm trying to think of mathematically what that would be
>> called. By the way, what do you need to know "HasZero"? A sum
>> operation has to have a "zero", doesn't it?
>
>
> The mathematical hierarchy goes: semigroup -> monoid.
>
> http://en.wikipedia.org/wiki/Semigroup
> http://en.wikipedia.org/wiki/Monoid
>
> You don't need a full group here as you are only interested in a single
> operation, not a pair of interacting operations. There are several
> JVM-hosted libraries that model this hierarchy to a greater or lesser
> degree. scalaz uses:
>
> trait Semigroup[S] {
> def append(s1: S
> <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>,
> s2: => S): S <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>
> }
>
> trait Zero[Z] {
> val zero: Z <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160>
> }
>
> trait Monoid[M] extends Zero
> <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945>[M]
> with Semigroup <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>[M]
>
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html
>
> If you're not used to reading scala, here's the essentially equivalent
> definitions in Java:
>
> public interface Semigroup<S> {
> public S append(S s1, S s2);
> }
>
> public interface Zero<Z> {
>
> public Z zero();
> }
>
> public interface Monoid<M> extends
> Zero<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945><M>,
> Semigroup<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>
> <M>
>
>
> So, given that you have Ordering<O> already (or is that Comparator<C>?),
> I'd say that Weight is defined as:
>
> // insert comments here about the consistency of append and compare
> public interface Weight<W> extends Monoid<W>, Ordered<W>
>
> Of course, a sensible default implementation of Weight would delegate to
> Monoid and Ordered instances and you can then pray to the gods of hotspot
> to inline this all away.
>
> public <W> Weight<W> weight(Monoid<W> m, Ordered<W> o) {
> new Weight<W>() {
> public W zero() { return m.zero(); }
> ...
> }
> }
>
> Matthew
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi Simone,
> the patch you mentioned was something I would have asked you, before or later :P
I know I can read your mind :)
> Since we are on topic: is there any particular reason why Zero.zero()
> can not be part of Semigroup interface? Or better: is there any
> benefit we can get from keeping Zero and Semigroup separated?
basically the answer is in the following equation:
Monoid = Semigroup + Zero
And also:
OrderedMonoid = Semigroup + Zero + Comparator
The reason why we built all the stack was to allow fine granularity when
defining properties of weights. E.g. it might happen for some reason
that we need to sum weights without needing to know their "zero" value,
or viceversa. In our current implementations OrderedMonoid takes most of
the space (as expected), but also Zero and Monoid are explicitly used.
Ciao,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hola Claudio,
the patch you mentioned was something I would have asked you, before or later :P
Since we are on topic: is there any particular reason why Zero.zero()
can not be part of Semigroup interface? Or better: is there any
benefit we can get from keeping Zero and Semigroup separated?
TIA,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sun, Feb 12, 2012 at 11:36 PM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> Hi,
>
>
>>> * the mapping between primitive types and their respective default
>>> *Operations is known and kept somewhere (abstract class, etc);
>>> * each algorithm specifies only once the set of primitive types that
>>> it accepts;
>>> * with a bit of magic (?) we combine the above to provide shortcuts to
>>> the user.
>>
>> +1
>>
>> I think that a mapper can be useful.
>> we can create a default mapper between primitives and *Operations and add
>> a void API like that
>> findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( void ).
>> we can choose the correct Operation mappimng directly on the default
>> constructor using our mapper.
>>
>> so for the primitives Integer, Double etc, the user doesn't have to
>> specify anything.
>
>
> I thought about something similar. But I finally see two downsides:
>
> * we would need to use reflection for generics or some better
> alternative to actually understand the generic type of weight and
> map it to the appropriate *Operations,
> * we should throw an exception when non-primitive weights are
> incorrectly passed without a handler.
>
> Now that I have a clearer picture in mind I'm almost convinced to give up...
>
> Anyway, expect a patch soon from me that at least incorporates suggestions
> on new names for primitive implementations and variable names ;)
>
> Ciao,
>
> Claudio
>
> --
> Claudio Squarcella
> PhD student at Roma Tre University
> http://www.dia.uniroma3.it/~squarcel
> http://squarcella.com/
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
>> * the mapping between primitive types and their respective default
>> *Operations is known and kept somewhere (abstract class, etc);
>> * each algorithm specifies only once the set of primitive types that
>> it accepts;
>> * with a bit of magic (?) we combine the above to provide shortcuts to
>> the user.
> +1
>
> I think that a mapper can be useful.
> we can create a default mapper between primitives and *Operations and add a void API like that
> findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( void ).
> we can choose the correct Operation mappimng directly on the default constructor using our mapper.
>
> so for the primitives Integer, Double etc, the user doesn't have to specify anything.
I thought about something similar. But I finally see two downsides:
* we would need to use reflection for generics or some better
alternative to actually understand the generic type of weight and
map it to the appropriate *Operations,
* we should throw an exception when non-primitive weights are
incorrectly passed without a handler.
Now that I have a clearer picture in mind I'm almost convinced to give up...
Anyway, expect a patch soon from me that at least incorporates
suggestions on new names for primitive implementations and variable names ;)
Ciao,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi *,
while the idea is fine, it is not clear to me how you intend
implementing it. Please fill an issue and attach a patch so we can
discuss also about the "how" and not only "what" :)
best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sun, Feb 12, 2012 at 10:26 PM, Marco Speranza
<ma...@gmail.com> wrote:
> Hi guys,
>
>> * the mapping between primitive types and their respective default
>> *Operations is known and kept somewhere (abstract class, etc);
>> * each algorithm specifies only once the set of primitive types that
>> it accepts;
>> * with a bit of magic (?) we combine the above to provide shortcuts to
>> the user.
>
> +1
>
> I think that a mapper can be useful.
> we can create a default mapper between primitives and *Operations and add a void API like that
> findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( void ).
> we can choose the correct Operation mappimng directly on the default constructor using our mapper.
>
> so for the primitives Integer, Double etc, the user doesn't have to specify anything.
>
> for a graph that uses a custom weight's type, the user can use the findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( OrderMonoid ) ) API.
>
> WDYT ?
>
> ciao
>
>
> --
> Marco Speranza <ma...@gmail.com>
>
> Flickr: http://www.flickr.com/photos/marcosperanza79/
> Google Code: http://code.google.com/u/marco.speranza79/
>
>
>
>
> Il giorno 12/feb/2012, alle ore 21:20, Claudio Squarcella ha scritto:
>
>> Hi Simone,
>>
>>>> Would it be so terrible to maintain such redundancy?
>>> IMHO, yes, because:
>>>
>>> * it has to be applied in each class of algorithms we support;
>>>
>>> * switching to proposed APIs, would proliferate that APIs in each algorithm;
>>>
>>> * weight types are driven by generics, so users cannot bind wrong
>>> weight monoid already at compile time.
>>>
>>> more proposals? :)
>>
>> ok fair enough, you were quite convincing :)
>>
>> Before giving up, one more alternative:
>>
>> * the mapping between primitive types and their respective default
>> *Operations is known and kept somewhere (abstract class, etc);
>> * each algorithm specifies only once the set of primitive types that
>> it accepts;
>> * with a bit of magic (?) we combine the above to provide shortcuts to
>> the user.
>>
>> Note: I don't want to over-engineer, I would just like the user not to specify default *Operations, because that is also redundant from his/her point of view.
>>
>> Ciao and thanks,
>> Claudio
>>
>> --
>> Claudio Squarcella
>> PhD student at Roma Tre University
>> http://www.dia.uniroma3.it/~squarcel
>> http://squarcella.com/
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Marco Speranza <ma...@gmail.com>.
Hi guys,
> * the mapping between primitive types and their respective default
> *Operations is known and kept somewhere (abstract class, etc);
> * each algorithm specifies only once the set of primitive types that
> it accepts;
> * with a bit of magic (?) we combine the above to provide shortcuts to
> the user.
+1
I think that a mapper can be useful.
we can create a default mapper between primitives and *Operations and add a void API like that
findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( void ).
we can choose the correct Operation mappimng directly on the default constructor using our mapper.
so for the primitives Integer, Double etc, the user doesn't have to specify anything.
for a graph that uses a custom weight's type, the user can use the findMaxFlow( graph ).from( a ).to( g ).applying<Algorithm>( OrderMonoid ) ) API.
WDYT ?
ciao
--
Marco Speranza <ma...@gmail.com>
Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
Il giorno 12/feb/2012, alle ore 21:20, Claudio Squarcella ha scritto:
> Hi Simone,
>
>>> Would it be so terrible to maintain such redundancy?
>> IMHO, yes, because:
>>
>> * it has to be applied in each class of algorithms we support;
>>
>> * switching to proposed APIs, would proliferate that APIs in each algorithm;
>>
>> * weight types are driven by generics, so users cannot bind wrong
>> weight monoid already at compile time.
>>
>> more proposals? :)
>
> ok fair enough, you were quite convincing :)
>
> Before giving up, one more alternative:
>
> * the mapping between primitive types and their respective default
> *Operations is known and kept somewhere (abstract class, etc);
> * each algorithm specifies only once the set of primitive types that
> it accepts;
> * with a bit of magic (?) we combine the above to provide shortcuts to
> the user.
>
> Note: I don't want to over-engineer, I would just like the user not to specify default *Operations, because that is also redundant from his/her point of view.
>
> Ciao and thanks,
> Claudio
>
> --
> Claudio Squarcella
> PhD student at Roma Tre University
> http://www.dia.uniroma3.it/~squarcel
> http://squarcella.com/
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi Simone,
>> Would it be so terrible to maintain such redundancy?
> IMHO, yes, because:
>
> * it has to be applied in each class of algorithms we support;
>
> * switching to proposed APIs, would proliferate that APIs in each algorithm;
>
> * weight types are driven by generics, so users cannot bind wrong
> weight monoid already at compile time.
>
> more proposals? :)
ok fair enough, you were quite convincing :)
Before giving up, one more alternative:
* the mapping between primitive types and their respective default
*Operations is known and kept somewhere (abstract class, etc);
* each algorithm specifies only once the set of primitive types that
it accepts;
* with a bit of magic (?) we combine the above to provide shortcuts to
the user.
Note: I don't want to over-engineer, I would just like the user not to
specify default *Operations, because that is also redundant from his/her
point of view.
Ciao and thanks,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hola,
> Would it be so terrible to maintain such redundancy?
IMHO, yes, because:
* it has to be applied in each class of algorithms we support;
* switching to proposed APIs, would proliferate that APIs in each algorithm;
* weight types are driven by generics, so users cannot bind wrong
weight monoid already at compile time.
more proposals? :)
best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hello Marco,
>> I understand and agree with you about your doubts - I don't have a
>> strong idea, anyway I wouldn't take the *Handler as first choice,
>> since it does not drive users to an event-handler alike programming
>> model, rather *Operations makes more sense...
>
> +1
c00l :)
> Furthermore I think that name of classes are congruent. In my opinion
> Monoid, OrderMonoid and Semigroup are the right names
I agree.
> findMaxFlow( graph ).from( a ).to( g
> ).applyingEdmondsKarp.withWeightOperation( new IntegerOperation() ) or
> something like that.
I would be more radical (chic) and add one shortcut for each primitive
weight type allowed, e.g:
findMaxFlow( graph ).from( a ).to( g
).applyingEdmondsKarp().usingWeightsAsIntegers()
findMaxFlow( graph ).from( a ).to( g
).applyingEdmondsKarp().usingWeightsAsDoubles()
[...]
I know it's damn redundant. It would be nice to have a better shortcut
to automagically use primitive weight operations when available and
require an explicit *Operations otherwise, but it's not an easy task
(not for me at least).
Note also that some algorithms may impose limits on the actual types
(e.g. Ford-Fulkerson may not terminate with irrational numbers...
although with floating point representation I guess we never face that
risk), so creating explicit shortcuts could also reflect such constraints.
Would it be so terrible to maintain such redundancy?
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Marco Speranza <ma...@gmail.com>.
Hi all,
> I understand and agree with you about your doubts - I don't have a
> strong idea, anyway I wouldn't take the *Handler as first choice,
> since it does not drive users to an event-handler alike programming
> model, rather *Operations makes more sense...
+1
Furthermore I think that name of classes are congruent. In my opinion Monoid, OrderMonoid and Semigroup are the right names . In order to help the users, we can add some fluent api
i.e.:
findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp.withWeightOperation( new IntegerOperation() ) or something like that.
Ciao
--
Marco Speranza <ma...@gmail.com>
Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
Il giorno 11/feb/2012, alle ore 21:19, Simone Tripodi ha scritto:
> Ciao Claudio!
>
> I understand and agree with you about your doubts - I don't have a
> strong idea, anyway I wouldn't take the *Handler as first choice,
> since it does not drive users to an event-handler alike programming
> model, rather *Operations makes more sense...
>
> Let's take some time to think about it, excellent catch anyway :)
>
> best,
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Sat, Feb 11, 2012 at 8:53 PM, Claudio Squarcella
> <sq...@dia.uniroma3.it> wrote:
>> Hi,
>>
>>
>>> Maybe one last effort can be made to come up with more understandable
>>> names (e.g. for a user that does not know what a Semigroup or Monoid is).
>>> Suggestions are welcome.
>>
>>
>> I exhume this thread because I am still convinced that the "weight
>> architecture" would benefit from a bit of renaming. It is probably not the
>> case to touch mathematical concepts (Semigroup, Monoid), but rather the
>> actual implementations and/or variable names. Consider that with the current
>> fluent API the user has to deal with this stuff explicitly, specifying the
>> appropriate "handler" for weights.
>>
>> So for example all primitive implementations[1] would change their name from
>> FooWeight to something like FooWeightHandler, or FooWeightOperations, or
>> something like that. Variable names (like in [2]) would change from e.g.
>> orderedMonoid to weightHandler, weightOperations, etc.
>>
>> Any preference?
>>
>> Ciao
>> Claudio
>>
>> [1]
>> http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/
>> [2] line 64:
>> http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?view=markup
>>
>>
>> --
>> 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
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Ciao Claudio!
I understand and agree with you about your doubts - I don't have a
strong idea, anyway I wouldn't take the *Handler as first choice,
since it does not drive users to an event-handler alike programming
model, rather *Operations makes more sense...
Let's take some time to think about it, excellent catch anyway :)
best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sat, Feb 11, 2012 at 8:53 PM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> Hi,
>
>
>> Maybe one last effort can be made to come up with more understandable
>> names (e.g. for a user that does not know what a Semigroup or Monoid is).
>> Suggestions are welcome.
>
>
> I exhume this thread because I am still convinced that the "weight
> architecture" would benefit from a bit of renaming. It is probably not the
> case to touch mathematical concepts (Semigroup, Monoid), but rather the
> actual implementations and/or variable names. Consider that with the current
> fluent API the user has to deal with this stuff explicitly, specifying the
> appropriate "handler" for weights.
>
> So for example all primitive implementations[1] would change their name from
> FooWeight to something like FooWeightHandler, or FooWeightOperations, or
> something like that. Variable names (like in [2]) would change from e.g.
> orderedMonoid to weightHandler, weightOperations, etc.
>
> Any preference?
>
> Ciao
> Claudio
>
> [1]
> http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/
> [2] line 64:
> http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?view=markup
>
>
> --
> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Ciao Claudio,
>
> yes that would work (inverse should be replaced with negate, not
> reciprocal). We actually thought of commons-math before: it would feel like
> home for our little stack of interfaces (Semigroup, Monoid, etc).
>
+1
> However my question was more on the semantics for class and variable names.
> Any idea?
>
Not yet :(
all the best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hello Axel,
> Wouldn't it be better to use the same method signatures like in
> commons-math FieldElement?
> http://commons.apache.org/math/apidocs/org/apache/commons/math/FieldElement.html#reciprocal%28%29
>
> reciprocal instead of inverse and
> add instead of append?
yes that would work (inverse should be replaced with negate, not
reciprocal). We actually thought of commons-math before: it would feel
like home for our little stack of interfaces (Semigroup, Monoid, etc).
However my question was more on the semantics for class and variable
names. Any idea?
Thank you :)
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Axel <ax...@gmail.com>.
On Sat, Feb 11, 2012 at 8:53 PM, Claudio Squarcella <
squarcel@dia.uniroma3.it> wrote:
> ....
> Any preference?
>
Wouldn't it be better to use the same method signatures like in
commons-math FieldElement?
http://commons.apache.org/math/apidocs/org/apache/commons/math/FieldElement.html#reciprocal%28%29
reciprocal instead of inverse and
add instead of append?
--
Axel Kramer
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
> Maybe one last effort can be made to come up with more understandable
> names (e.g. for a user that does not know what a Semigroup or Monoid
> is). Suggestions are welcome.
I exhume this thread because I am still convinced that the "weight
architecture" would benefit from a bit of renaming. It is probably not
the case to touch mathematical concepts (Semigroup, Monoid), but rather
the actual implementations and/or variable names. Consider that with the
current fluent API the user has to deal with this stuff explicitly,
specifying the appropriate "handler" for weights.
So for example all primitive implementations[1] would change their name
from FooWeight to something like FooWeightHandler, or
FooWeightOperations, or something like that. Variable names (like in
[2]) would change from e.g. orderedMonoid to weightHandler,
weightOperations, etc.
Any preference?
Ciao
Claudio
[1]
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/
[2] line 64:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?view=markup
--
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
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi all,
the generic implementation of weights is finally completed, at least for
currently implemented algorithms requiring weights. Check out the latest
version of [graph] for details, and the related issue for description of
changes:
https://issues.apache.org/jira/browse/SANDBOX-356
Maybe one last effort can be made to come up with more understandable
names (e.g. for a user that does not know what a Semigroup or Monoid
is). Suggestions are welcome.
Thank you,
Claudio
On 08/01/2012 18:43, Simone Tripodi wrote:
> Hola Claudio,
>
> I just saw the issue - flawless report! - just give me the time to
> process it and I'll let you know!
>
> best,
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Sun, Jan 8, 2012 at 6:38 PM, Claudio Squarcella
> <sq...@dia.uniroma3.it> wrote:
>> Hi,
>>
>>
>> On 26/12/2011 22:09, Simone Tripodi wrote:
>>> Hi Claudio!
>>>
>>> just make your proposal and attach it to a jira Issue :)
>>
>> it took a while (you know, Xmas and stuff) but here it is, with description:
>> https://issues.apache.org/jira/browse/SANDBOX-356
>>
>> I hope it looks good -- quite a big patch, so of course all comments are
>> welcome.
>>
>> Ciao,
>> Claudio
>>
>>
>>
>>> Hope to hear from you soon, all the best!
>>> -Simo
>>>
>>> http://people.apache.org/~simonetripodi/
>>> http://simonetripodi.livejournal.com/
>>> http://twitter.com/simonetripodi
>>> http://www.99soft.org/
>>>
>> --
>> 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
>>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
--
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
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hola Claudio,
I just saw the issue - flawless report! - just give me the time to
process it and I'll let you know!
best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sun, Jan 8, 2012 at 6:38 PM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> Hi,
>
>
> On 26/12/2011 22:09, Simone Tripodi wrote:
>>
>> Hi Claudio!
>>
>> just make your proposal and attach it to a jira Issue :)
>
>
> it took a while (you know, Xmas and stuff) but here it is, with description:
> https://issues.apache.org/jira/browse/SANDBOX-356
>
> I hope it looks good -- quite a big patch, so of course all comments are
> welcome.
>
> Ciao,
> Claudio
>
>
>
>> Hope to hear from you soon, all the best!
>> -Simo
>>
>> http://people.apache.org/~simonetripodi/
>> http://simonetripodi.livejournal.com/
>> http://twitter.com/simonetripodi
>> http://www.99soft.org/
>>
>
> --
> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
On 26/12/2011 22:09, Simone Tripodi wrote:
> Hi Claudio!
>
> just make your proposal and attach it to a jira Issue :)
it took a while (you know, Xmas and stuff) but here it is, with description:
https://issues.apache.org/jira/browse/SANDBOX-356
I hope it looks good -- quite a big patch, so of course all comments are
welcome.
Ciao,
Claudio
> Hope to hear from you soon, all the best!
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
--
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
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi Claudio!
just make your proposal and attach it to a jira Issue :)
Hope to hear from you soon, all the best!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Fri, Dec 23, 2011 at 6:02 PM, <sq...@dia.uniroma3.it> wrote:
> Hi,
>
> I like the idea of external weights. Actually that could work for other
> properties of the graph as well. I see a couple of use cases there.
>
> As for lazy implementations, I like them too but with much less priority
> for now.
>
> Anyway, first things first: guys should I infer an implicit 'yes' from
> your answers and go ahead with the proposed change for weights? Anyone
> else has a word on this? I am just applying some lazy pattern here --
> discuss before coding ;)
>
> Claudio
>
>
>> On 23 December 2011 10:38, Simone Tripodi <si...@apache.org>
>> wrote:
>>
>>> Hi Matthew!
>>>
>>
>>
>>> Usually algorithms (like Dijkstra) already have clear enunciates and
>>> steps are known, so we could safety expose 1 APIs that hide all that
>>> details to clients wrapping your proposals.
>>>
>>
>> That's what façades are for. I totally agree with providing users with
>> utility methods that hide all the guts.
>>
>>
>>>
>>> WDYT? Thanks again!!!
>>> -Simo
>>>
>>> http://people.apache.org/~simonetripodi/
>>> http://simonetripodi.livejournal.com/
>>> http://twitter.com/simonetripodi
>>> http://www.99soft.org/
>>>
>>>
>>>
>>> On Fri, Dec 23, 2011 at 10:44 AM, Matthew Pocock
>>> <tu...@gmail.com> wrote:
>>> > Hi Simo,
>>> >
>>> > I guess the 5 minutes to run example would be:
>>> >
>>> > ShortestPathFunction.dijkstra
>>> > .makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble)
>>> > .findShortestPath(source, target);
>>> >
>>> > I was assuming that there would be standard pallets of all the
>>> strategies
>>> > available statically in the obvious places. Actually, now I see the
>>> code
>>> > written out in full like that, I'd perhaps consider renaming
>>> makeResult
>>> to
>>> > `calculate` or `prepare` or some other verb.
>>> >
>>> > Matthew
>>> >
>>> > On 23 December 2011 08:47, Simone Tripodi <si...@apache.org>
>>> wrote:
>>> >
>>> >> Hi Matthew!
>>> >>
>>> >> at a first looks it is really interesting, just give me the time to
>>> >> digest because at the same time I had the feeling of a little
>>> >> over-engineering activity, I am worried that "5 minutes to run" users
>>> >> would find it not so immediate.
>>> >>
>>> >> Thanks for providing stuff to learn from!
>>> >> All the best,
>>> >> -Simo
>>> >>
>>> >> http://people.apache.org/~simonetripodi/
>>> >> http://simonetripodi.livejournal.com/
>>> >> http://twitter.com/simonetripodi
>>> >> http://www.99soft.org/
>>> >>
>>> >>
>>> >>
>>> >> On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
>>> >> <tu...@gmail.com> wrote:
>>> >> > Hi,
>>> >> >
>>> >> > Just thought I'd throw something out here. My experience is that I
>>> often
>>> >> > take the same graph (as in the exact same data, same objects) but
>>> at
>>> >> > different times want to use different weights. So, rather than
>>> having
>>> >> Edge
>>> >> > extend Weighted<W>, I'd factor weights out into their own
>>> interface:
>>> >> >
>>> >> > /**
>>> >> > * An edge weight function.
>>> >> > *
>>> >> > * note: perhaps this should more generally just be a Function1<A,
>>> B>, if
>>> >> > we have such a thing handy.
>>> >> > *
>>> >> > * @tparam E edge type
>>> >> > * @tparam W weight type
>>> >> > */
>>> >> > public interface EdgeWeight<E, W> {
>>> >> > public W getWeight(E: Edge);
>>> >> > }
>>> >> >
>>> >> > /**
>>> >> > * A combination of a monoid and comparator that satisfy
>>> monotinicity
>>> of
>>> >> > the addition operation with respect to the comparator.
>>> >> > *
>>> >> > * ∀a: m.compare(m.zero, a) <= 0
>>> >> > * ∀a,b: m.compare(a, m.append(a, b)) <= 0
>>> >> > */
>>> >> > public interface Monotonic<W> extends Monoid<W>, Comparator<W>
>>> >> >
>>> >> > Also, some algorithms calculate all shortest paths at once, while
>>> others
>>> >> > calculate them individually and independently. It's probably even
>>> >> possible
>>> >> > to calculate some lazily. So, the interfaces for shortest paths
>>> should
>>> >> > decouple setting up a strategy for all shortest paths from an
>>> object
>>> that
>>> >> > can be used to fetch a specific shortest path.
>>> >> >
>>> >> > /**
>>> >> > * An algorithm for finding shortest paths between vertices of a
>>> graph,
>>> >> > given some edge weighting function and
>>> >> > * a well-behaved combinator for edges between connected vertices.
>>> >> > */
>>> >> > public interface ShortestPathFunction<V extends Vertex, E extends
>>> >> Edge<E>,
>>> >> > G extends DirectedGraph<V, E>, W> {
>>> >> > public ShortestPathResult<V, E, W> makeResult(G graph,
>>> EdgeWeight<E,
>>> W>
>>> >> > weighting, Monotonic<W> combineWith);
>>> >> > }
>>> >> >
>>> >> > /**
>>> >> > * The shortest paths between vertices in a graph.
>>> >> > */
>>> >> > public interface ShortestPathResult<V extends Vertex, E extends
>>> Edge<E>,
>>> >> W>
>>> >> > {
>>> >> > public WeightedPath<V, E, W> findShortestPath(V source, V target);
>>> >> > }
>>> >> >
>>> >> > How does that look? You can then have standard implementations of
>>> these
>>> >> > things in some static utility class or a spring-friendly resource.
>>> The
>>> >> > brute-force algorithms that compute all paths at once would do all
>>> the
>>> >> work
>>> >> > in makeResult() and simply store this in some state within the
>>> returned
>>> >> > ShortestPathResult. Those that calculate individual pairs on the
>>> fly
>>> (or
>>> >> > all shortest paths from some vertex) would capture state in
>>> makeResult()
>>> >> > and perform the actual computation in findShortestPath().
>>> >> >
>>> >> > Matthew
>>> >> >
>>> >> > On 22 December 2011 16:39, Claudio Squarcella <
>>> squarcel@dia.uniroma3.it
>>> >> >wrote:
>>> >> >
>>> >> >> Hi,
>>> >> >>
>>> >> >>
>>> >> >> I highly appreciated the last contributions (thanks guys!) but I
>>> also
>>> >> >>> agree on this point, so let's start from the end.
>>> >> >>> I think that, no matter what underlying structure we come up
>>> with,
>>> the
>>> >> >>> user should be able to specify e.g. a weighted edge with
>>> something
>>> like
>>> >> >>>
>>> >> >>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>> >> >>>
>>> >> >>> and be able to immediately use it as an input for all the
>>> algorithms,
>>> >> >>> without extra steps required. So the average user is happy, while
>>> >> "graph
>>> >> >>> geeks" can dig into advanced capabilities and forge their
>>> personalized
>>> >> >>> weights :)
>>> >> >>> I hope we all agree on this as a first step. Complexity comes
>>> after.
>>> >> >>>
>>> >> >>> I'll take my time as well to re-think.
>>> >> >>>
>>> >> >>
>>> >> >> I did think and code a bit more. First of all please take a look
>>> at
>>> the
>>> >> >> updated code: Weighted<W> is an interface (weight W can be any
>>> type)
>>> and
>>> >> >> all the algorithms require edges to implement Weighted<Double> for
>>> now
>>> >> --
>>> >> >> we did not break it that much ;)
>>> >> >>
>>> >> >> About the "HasProperty-vs-Property" question (as in Comparable vs
>>> >> >> Comparator, MonoidElement vs Monoid, etc) I would go for the
>>> second
>>> one
>>> >> >> only. That is, external classes handle all operations on weights.
>>> >> Downside:
>>> >> >> the # of method parameters would increase linearly with the number
>>> of
>>> >> >> properties, but I can live with that (how many properties would
>>> weights
>>> >> >> have anyway?). On the other hand we have a neat interface for each
>>> >> >> property/class (Zero, Semigroup, Monoid, Ordering or Comparator,
>>> etc)
>>> >> and
>>> >> >> one clean, generic implementation for each algorithm. Dijkstra's
>>> >> signature
>>> >> >> becomes something like:
>>> >> >>
>>> >> >> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
>>> >> extends
>>> >> >> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G
>>> graph,
>>> >> V
>>> >> >> source, V target, Monoid<W> weightMonoid, Comparator<W>
>>> >> weightComparator )
>>> >> >>
>>> >> >> Scary uh? But wait, default implementations for Double, Integer,
>>> etc.
>>> >> are
>>> >> >> way easier. E.g. Dijkstra's shortcut for Double:
>>> >> >>
>>> >> >> public static <V extends Vertex, WE extends WeightedEdge<Double>,
>>> G
>>> >> >> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
>>> >> findShortestPath(
>>> >> >> G graph, V source, V target )
>>> >> >> {
>>> >> >> return findShortestPath(graph, source, target, new
>>> DoubleMonoid(),
>>> >> new
>>> >> >> DoubleComparator());
>>> >> >> }
>>> >> >>
>>> >> >> where DoubleMonoid and DoubleComparator are part of the library.
>>> >> >>
>>> >> >>
>>> >> >> If you guys are fine with this, I'm ready to try and patch [graph]
>>> with
>>> >> a
>>> >> >> Christmas gift :)
>>> >> >> 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<
>>> >> http://www.dia.uniroma3.it/~squarcel>
>>> >> >>
>>> >> >>
>>> >> >>
>>> >>
>>> ------------------------------**------------------------------**---------
>>> >> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
>>> >> dev-unsubscribe@commons.apache.org>
>>> >> >> For additional commands, e-mail: dev-help@commons.apache.org
>>> >> >>
>>> >> >>
>>> >> >
>>> >> >
>>> >> > --
>>> >> > Dr Matthew Pocock
>>> >> > Integrative Bioinformatics Group, School of Computing Science,
>>> Newcastle
>>> >> > University
>>> >> > mailto: turingatemyhamster@gmail.com
>>> >> > gchat: turingatemyhamster@gmail.com
>>> >> > msn: matthew_pocock@yahoo.co.uk
>>> >> > irc.freenode.net: drdozer
>>> >> > skype: matthew.pocock
>>> >> > tel: (0191) 2566550
>>> >> > mob: +447535664143
>>> >>
>>> >> ---------------------------------------------------------------------
>>> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> >> For additional commands, e-mail: dev-help@commons.apache.org
>>> >>
>>> >>
>>> >
>>> >
>>> > --
>>> > Dr Matthew Pocock
>>> > Integrative Bioinformatics Group, School of Computing Science,
>>> Newcastle
>>> > University
>>> > mailto: turingatemyhamster@gmail.com
>>> > gchat: turingatemyhamster@gmail.com
>>> > msn: matthew_pocock@yahoo.co.uk
>>> > irc.freenode.net: drdozer
>>> > skype: matthew.pocock
>>> > tel: (0191) 2566550
>>> > mob: +447535664143
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
>>
>>
>> --
>> Dr Matthew Pocock
>> Integrative Bioinformatics Group, School of Computing Science, Newcastle
>> University
>> mailto: turingatemyhamster@gmail.com
>> gchat: turingatemyhamster@gmail.com
>> msn: matthew_pocock@yahoo.co.uk
>> irc.freenode.net: drdozer
>> skype: matthew.pocock
>> tel: (0191) 2566550
>> mob: +447535664143
>>
>
>
>
> -----------------------------------------
> This email was sent using SquirrelMail.
> https://email.dia.uniroma3.it
> Web Site: http://www.squirrelmail.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by sq...@dia.uniroma3.it.
Hi,
I like the idea of external weights. Actually that could work for other
properties of the graph as well. I see a couple of use cases there.
As for lazy implementations, I like them too but with much less priority
for now.
Anyway, first things first: guys should I infer an implicit 'yes' from
your answers and go ahead with the proposed change for weights? Anyone
else has a word on this? I am just applying some lazy pattern here --
discuss before coding ;)
Claudio
> On 23 December 2011 10:38, Simone Tripodi <si...@apache.org>
> wrote:
>
>> Hi Matthew!
>>
>
>
>> Usually algorithms (like Dijkstra) already have clear enunciates and
>> steps are known, so we could safety expose 1 APIs that hide all that
>> details to clients wrapping your proposals.
>>
>
> That's what façades are for. I totally agree with providing users with
> utility methods that hide all the guts.
>
>
>>
>> WDYT? Thanks again!!!
>> -Simo
>>
>> http://people.apache.org/~simonetripodi/
>> http://simonetripodi.livejournal.com/
>> http://twitter.com/simonetripodi
>> http://www.99soft.org/
>>
>>
>>
>> On Fri, Dec 23, 2011 at 10:44 AM, Matthew Pocock
>> <tu...@gmail.com> wrote:
>> > Hi Simo,
>> >
>> > I guess the 5 minutes to run example would be:
>> >
>> > ShortestPathFunction.dijkstra
>> > .makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble)
>> > .findShortestPath(source, target);
>> >
>> > I was assuming that there would be standard pallets of all the
>> strategies
>> > available statically in the obvious places. Actually, now I see the
>> code
>> > written out in full like that, I'd perhaps consider renaming
>> makeResult
>> to
>> > `calculate` or `prepare` or some other verb.
>> >
>> > Matthew
>> >
>> > On 23 December 2011 08:47, Simone Tripodi <si...@apache.org>
>> wrote:
>> >
>> >> Hi Matthew!
>> >>
>> >> at a first looks it is really interesting, just give me the time to
>> >> digest because at the same time I had the feeling of a little
>> >> over-engineering activity, I am worried that "5 minutes to run" users
>> >> would find it not so immediate.
>> >>
>> >> Thanks for providing stuff to learn from!
>> >> All the best,
>> >> -Simo
>> >>
>> >> http://people.apache.org/~simonetripodi/
>> >> http://simonetripodi.livejournal.com/
>> >> http://twitter.com/simonetripodi
>> >> http://www.99soft.org/
>> >>
>> >>
>> >>
>> >> On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
>> >> <tu...@gmail.com> wrote:
>> >> > Hi,
>> >> >
>> >> > Just thought I'd throw something out here. My experience is that I
>> often
>> >> > take the same graph (as in the exact same data, same objects) but
>> at
>> >> > different times want to use different weights. So, rather than
>> having
>> >> Edge
>> >> > extend Weighted<W>, I'd factor weights out into their own
>> interface:
>> >> >
>> >> > /**
>> >> > * An edge weight function.
>> >> > *
>> >> > * note: perhaps this should more generally just be a Function1<A,
>> B>, if
>> >> > we have such a thing handy.
>> >> > *
>> >> > * @tparam E edge type
>> >> > * @tparam W weight type
>> >> > */
>> >> > public interface EdgeWeight<E, W> {
>> >> > public W getWeight(E: Edge);
>> >> > }
>> >> >
>> >> > /**
>> >> > * A combination of a monoid and comparator that satisfy
>> monotinicity
>> of
>> >> > the addition operation with respect to the comparator.
>> >> > *
>> >> > * âa: m.compare(m.zero, a) <= 0
>> >> > * âa,b: m.compare(a, m.append(a, b)) <= 0
>> >> > */
>> >> > public interface Monotonic<W> extends Monoid<W>, Comparator<W>
>> >> >
>> >> > Also, some algorithms calculate all shortest paths at once, while
>> others
>> >> > calculate them individually and independently. It's probably even
>> >> possible
>> >> > to calculate some lazily. So, the interfaces for shortest paths
>> should
>> >> > decouple setting up a strategy for all shortest paths from an
>> object
>> that
>> >> > can be used to fetch a specific shortest path.
>> >> >
>> >> > /**
>> >> > * An algorithm for finding shortest paths between vertices of a
>> graph,
>> >> > given some edge weighting function and
>> >> > * a well-behaved combinator for edges between connected vertices.
>> >> > */
>> >> > public interface ShortestPathFunction<V extends Vertex, E extends
>> >> Edge<E>,
>> >> > G extends DirectedGraph<V, E>, W> {
>> >> > public ShortestPathResult<V, E, W> makeResult(G graph,
>> EdgeWeight<E,
>> W>
>> >> > weighting, Monotonic<W> combineWith);
>> >> > }
>> >> >
>> >> > /**
>> >> > * The shortest paths between vertices in a graph.
>> >> > */
>> >> > public interface ShortestPathResult<V extends Vertex, E extends
>> Edge<E>,
>> >> W>
>> >> > {
>> >> > public WeightedPath<V, E, W> findShortestPath(V source, V target);
>> >> > }
>> >> >
>> >> > How does that look? You can then have standard implementations of
>> these
>> >> > things in some static utility class or a spring-friendly resource.
>> The
>> >> > brute-force algorithms that compute all paths at once would do all
>> the
>> >> work
>> >> > in makeResult() and simply store this in some state within the
>> returned
>> >> > ShortestPathResult. Those that calculate individual pairs on the
>> fly
>> (or
>> >> > all shortest paths from some vertex) would capture state in
>> makeResult()
>> >> > and perform the actual computation in findShortestPath().
>> >> >
>> >> > Matthew
>> >> >
>> >> > On 22 December 2011 16:39, Claudio Squarcella <
>> squarcel@dia.uniroma3.it
>> >> >wrote:
>> >> >
>> >> >> Hi,
>> >> >>
>> >> >>
>> >> >> I highly appreciated the last contributions (thanks guys!) but I
>> also
>> >> >>> agree on this point, so let's start from the end.
>> >> >>> I think that, no matter what underlying structure we come up
>> with,
>> the
>> >> >>> user should be able to specify e.g. a weighted edge with
>> something
>> like
>> >> >>>
>> >> >>> public class MyEdge implements Edge, Weighted<Double> { ... }
>> >> >>>
>> >> >>> and be able to immediately use it as an input for all the
>> algorithms,
>> >> >>> without extra steps required. So the average user is happy, while
>> >> "graph
>> >> >>> geeks" can dig into advanced capabilities and forge their
>> personalized
>> >> >>> weights :)
>> >> >>> I hope we all agree on this as a first step. Complexity comes
>> after.
>> >> >>>
>> >> >>> I'll take my time as well to re-think.
>> >> >>>
>> >> >>
>> >> >> I did think and code a bit more. First of all please take a look
>> at
>> the
>> >> >> updated code: Weighted<W> is an interface (weight W can be any
>> type)
>> and
>> >> >> all the algorithms require edges to implement Weighted<Double> for
>> now
>> >> --
>> >> >> we did not break it that much ;)
>> >> >>
>> >> >> About the "HasProperty-vs-Property" question (as in Comparable vs
>> >> >> Comparator, MonoidElement vs Monoid, etc) I would go for the
>> second
>> one
>> >> >> only. That is, external classes handle all operations on weights.
>> >> Downside:
>> >> >> the # of method parameters would increase linearly with the number
>> of
>> >> >> properties, but I can live with that (how many properties would
>> weights
>> >> >> have anyway?). On the other hand we have a neat interface for each
>> >> >> property/class (Zero, Semigroup, Monoid, Ordering or Comparator,
>> etc)
>> >> and
>> >> >> one clean, generic implementation for each algorithm. Dijkstra's
>> >> signature
>> >> >> becomes something like:
>> >> >>
>> >> >> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
>> >> extends
>> >> >> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G
>> graph,
>> >> V
>> >> >> source, V target, Monoid<W> weightMonoid, Comparator<W>
>> >> weightComparator )
>> >> >>
>> >> >> Scary uh? But wait, default implementations for Double, Integer,
>> etc.
>> >> are
>> >> >> way easier. E.g. Dijkstra's shortcut for Double:
>> >> >>
>> >> >> public static <V extends Vertex, WE extends WeightedEdge<Double>,
>> G
>> >> >> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
>> >> findShortestPath(
>> >> >> G graph, V source, V target )
>> >> >> {
>> >> >> return findShortestPath(graph, source, target, new
>> DoubleMonoid(),
>> >> new
>> >> >> DoubleComparator());
>> >> >> }
>> >> >>
>> >> >> where DoubleMonoid and DoubleComparator are part of the library.
>> >> >>
>> >> >>
>> >> >> If you guys are fine with this, I'm ready to try and patch [graph]
>> with
>> >> a
>> >> >> Christmas gift :)
>> >> >> 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<
>> >> http://www.dia.uniroma3.it/~squarcel>
>> >> >>
>> >> >>
>> >> >>
>> >>
>> ------------------------------**------------------------------**---------
>> >> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
>> >> dev-unsubscribe@commons.apache.org>
>> >> >> For additional commands, e-mail: dev-help@commons.apache.org
>> >> >>
>> >> >>
>> >> >
>> >> >
>> >> > --
>> >> > Dr Matthew Pocock
>> >> > Integrative Bioinformatics Group, School of Computing Science,
>> Newcastle
>> >> > University
>> >> > mailto: turingatemyhamster@gmail.com
>> >> > gchat: turingatemyhamster@gmail.com
>> >> > msn: matthew_pocock@yahoo.co.uk
>> >> > irc.freenode.net: drdozer
>> >> > skype: matthew.pocock
>> >> > tel: (0191) 2566550
>> >> > mob: +447535664143
>> >>
>> >> ---------------------------------------------------------------------
>> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> >> For additional commands, e-mail: dev-help@commons.apache.org
>> >>
>> >>
>> >
>> >
>> > --
>> > Dr Matthew Pocock
>> > Integrative Bioinformatics Group, School of Computing Science,
>> Newcastle
>> > University
>> > mailto: turingatemyhamster@gmail.com
>> > gchat: turingatemyhamster@gmail.com
>> > msn: matthew_pocock@yahoo.co.uk
>> > irc.freenode.net: drdozer
>> > skype: matthew.pocock
>> > tel: (0191) 2566550
>> > mob: +447535664143
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
>
-----------------------------------------
This email was sent using SquirrelMail.
https://email.dia.uniroma3.it
Web Site: http://www.squirrelmail.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Matthew Pocock <tu...@gmail.com>.
On 23 December 2011 10:38, Simone Tripodi <si...@apache.org> wrote:
> Hi Matthew!
>
> Usually algorithms (like Dijkstra) already have clear enunciates and
> steps are known, so we could safety expose 1 APIs that hide all that
> details to clients wrapping your proposals.
>
That's what façades are for. I totally agree with providing users with
utility methods that hide all the guts.
>
> WDYT? Thanks again!!!
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Fri, Dec 23, 2011 at 10:44 AM, Matthew Pocock
> <tu...@gmail.com> wrote:
> > Hi Simo,
> >
> > I guess the 5 minutes to run example would be:
> >
> > ShortestPathFunction.dijkstra
> > .makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble)
> > .findShortestPath(source, target);
> >
> > I was assuming that there would be standard pallets of all the strategies
> > available statically in the obvious places. Actually, now I see the code
> > written out in full like that, I'd perhaps consider renaming makeResult
> to
> > `calculate` or `prepare` or some other verb.
> >
> > Matthew
> >
> > On 23 December 2011 08:47, Simone Tripodi <si...@apache.org>
> wrote:
> >
> >> Hi Matthew!
> >>
> >> at a first looks it is really interesting, just give me the time to
> >> digest because at the same time I had the feeling of a little
> >> over-engineering activity, I am worried that "5 minutes to run" users
> >> would find it not so immediate.
> >>
> >> Thanks for providing stuff to learn from!
> >> All the best,
> >> -Simo
> >>
> >> http://people.apache.org/~simonetripodi/
> >> http://simonetripodi.livejournal.com/
> >> http://twitter.com/simonetripodi
> >> http://www.99soft.org/
> >>
> >>
> >>
> >> On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
> >> <tu...@gmail.com> wrote:
> >> > Hi,
> >> >
> >> > Just thought I'd throw something out here. My experience is that I
> often
> >> > take the same graph (as in the exact same data, same objects) but at
> >> > different times want to use different weights. So, rather than having
> >> Edge
> >> > extend Weighted<W>, I'd factor weights out into their own interface:
> >> >
> >> > /**
> >> > * An edge weight function.
> >> > *
> >> > * note: perhaps this should more generally just be a Function1<A,
> B>, if
> >> > we have such a thing handy.
> >> > *
> >> > * @tparam E edge type
> >> > * @tparam W weight type
> >> > */
> >> > public interface EdgeWeight<E, W> {
> >> > public W getWeight(E: Edge);
> >> > }
> >> >
> >> > /**
> >> > * A combination of a monoid and comparator that satisfy monotinicity
> of
> >> > the addition operation with respect to the comparator.
> >> > *
> >> > * ∀a: m.compare(m.zero, a) <= 0
> >> > * ∀a,b: m.compare(a, m.append(a, b)) <= 0
> >> > */
> >> > public interface Monotonic<W> extends Monoid<W>, Comparator<W>
> >> >
> >> > Also, some algorithms calculate all shortest paths at once, while
> others
> >> > calculate them individually and independently. It's probably even
> >> possible
> >> > to calculate some lazily. So, the interfaces for shortest paths should
> >> > decouple setting up a strategy for all shortest paths from an object
> that
> >> > can be used to fetch a specific shortest path.
> >> >
> >> > /**
> >> > * An algorithm for finding shortest paths between vertices of a
> graph,
> >> > given some edge weighting function and
> >> > * a well-behaved combinator for edges between connected vertices.
> >> > */
> >> > public interface ShortestPathFunction<V extends Vertex, E extends
> >> Edge<E>,
> >> > G extends DirectedGraph<V, E>, W> {
> >> > public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E,
> W>
> >> > weighting, Monotonic<W> combineWith);
> >> > }
> >> >
> >> > /**
> >> > * The shortest paths between vertices in a graph.
> >> > */
> >> > public interface ShortestPathResult<V extends Vertex, E extends
> Edge<E>,
> >> W>
> >> > {
> >> > public WeightedPath<V, E, W> findShortestPath(V source, V target);
> >> > }
> >> >
> >> > How does that look? You can then have standard implementations of
> these
> >> > things in some static utility class or a spring-friendly resource. The
> >> > brute-force algorithms that compute all paths at once would do all the
> >> work
> >> > in makeResult() and simply store this in some state within the
> returned
> >> > ShortestPathResult. Those that calculate individual pairs on the fly
> (or
> >> > all shortest paths from some vertex) would capture state in
> makeResult()
> >> > and perform the actual computation in findShortestPath().
> >> >
> >> > Matthew
> >> >
> >> > On 22 December 2011 16:39, Claudio Squarcella <
> squarcel@dia.uniroma3.it
> >> >wrote:
> >> >
> >> >> Hi,
> >> >>
> >> >>
> >> >> I highly appreciated the last contributions (thanks guys!) but I
> also
> >> >>> agree on this point, so let's start from the end.
> >> >>> I think that, no matter what underlying structure we come up with,
> the
> >> >>> user should be able to specify e.g. a weighted edge with something
> like
> >> >>>
> >> >>> public class MyEdge implements Edge, Weighted<Double> { ... }
> >> >>>
> >> >>> and be able to immediately use it as an input for all the
> algorithms,
> >> >>> without extra steps required. So the average user is happy, while
> >> "graph
> >> >>> geeks" can dig into advanced capabilities and forge their
> personalized
> >> >>> weights :)
> >> >>> I hope we all agree on this as a first step. Complexity comes after.
> >> >>>
> >> >>> I'll take my time as well to re-think.
> >> >>>
> >> >>
> >> >> I did think and code a bit more. First of all please take a look at
> the
> >> >> updated code: Weighted<W> is an interface (weight W can be any type)
> and
> >> >> all the algorithms require edges to implement Weighted<Double> for
> now
> >> --
> >> >> we did not break it that much ;)
> >> >>
> >> >> About the "HasProperty-vs-Property" question (as in Comparable vs
> >> >> Comparator, MonoidElement vs Monoid, etc) I would go for the second
> one
> >> >> only. That is, external classes handle all operations on weights.
> >> Downside:
> >> >> the # of method parameters would increase linearly with the number of
> >> >> properties, but I can live with that (how many properties would
> weights
> >> >> have anyway?). On the other hand we have a neat interface for each
> >> >> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc)
> >> and
> >> >> one clean, generic implementation for each algorithm. Dijkstra's
> >> signature
> >> >> becomes something like:
> >> >>
> >> >> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
> >> extends
> >> >> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G
> graph,
> >> V
> >> >> source, V target, Monoid<W> weightMonoid, Comparator<W>
> >> weightComparator )
> >> >>
> >> >> Scary uh? But wait, default implementations for Double, Integer, etc.
> >> are
> >> >> way easier. E.g. Dijkstra's shortcut for Double:
> >> >>
> >> >> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
> >> >> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
> >> findShortestPath(
> >> >> G graph, V source, V target )
> >> >> {
> >> >> return findShortestPath(graph, source, target, new DoubleMonoid(),
> >> new
> >> >> DoubleComparator());
> >> >> }
> >> >>
> >> >> where DoubleMonoid and DoubleComparator are part of the library.
> >> >>
> >> >>
> >> >> If you guys are fine with this, I'm ready to try and patch [graph]
> with
> >> a
> >> >> Christmas gift :)
> >> >> 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<
> >> http://www.dia.uniroma3.it/~squarcel>
> >> >>
> >> >>
> >> >>
> >>
> ------------------------------**------------------------------**---------
> >> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> >> dev-unsubscribe@commons.apache.org>
> >> >> For additional commands, e-mail: dev-help@commons.apache.org
> >> >>
> >> >>
> >> >
> >> >
> >> > --
> >> > Dr Matthew Pocock
> >> > Integrative Bioinformatics Group, School of Computing Science,
> Newcastle
> >> > University
> >> > mailto: turingatemyhamster@gmail.com
> >> > gchat: turingatemyhamster@gmail.com
> >> > msn: matthew_pocock@yahoo.co.uk
> >> > irc.freenode.net: drdozer
> >> > skype: matthew.pocock
> >> > tel: (0191) 2566550
> >> > mob: +447535664143
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> >> For additional commands, e-mail: dev-help@commons.apache.org
> >>
> >>
> >
> >
> > --
> > Dr Matthew Pocock
> > Integrative Bioinformatics Group, School of Computing Science, Newcastle
> > University
> > mailto: turingatemyhamster@gmail.com
> > gchat: turingatemyhamster@gmail.com
> > msn: matthew_pocock@yahoo.co.uk
> > irc.freenode.net: drdozer
> > skype: matthew.pocock
> > tel: (0191) 2566550
> > mob: +447535664143
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi Matthew!
I think that your idea is great as a foundation for implementing
algorithms but I would not allow users use that APIs to resolve known
problems, unless they want to implement their own solutions or
contribute back to [graph] missing algorithms.
Usually algorithms (like Dijkstra) already have clear enunciates and
steps are known, so we could safety expose 1 APIs that hide all that
details to clients wrapping your proposals.
WDYT? Thanks again!!!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Fri, Dec 23, 2011 at 10:44 AM, Matthew Pocock
<tu...@gmail.com> wrote:
> Hi Simo,
>
> I guess the 5 minutes to run example would be:
>
> ShortestPathFunction.dijkstra
> .makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble)
> .findShortestPath(source, target);
>
> I was assuming that there would be standard pallets of all the strategies
> available statically in the obvious places. Actually, now I see the code
> written out in full like that, I'd perhaps consider renaming makeResult to
> `calculate` or `prepare` or some other verb.
>
> Matthew
>
> On 23 December 2011 08:47, Simone Tripodi <si...@apache.org> wrote:
>
>> Hi Matthew!
>>
>> at a first looks it is really interesting, just give me the time to
>> digest because at the same time I had the feeling of a little
>> over-engineering activity, I am worried that "5 minutes to run" users
>> would find it not so immediate.
>>
>> Thanks for providing stuff to learn from!
>> All the best,
>> -Simo
>>
>> http://people.apache.org/~simonetripodi/
>> http://simonetripodi.livejournal.com/
>> http://twitter.com/simonetripodi
>> http://www.99soft.org/
>>
>>
>>
>> On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
>> <tu...@gmail.com> wrote:
>> > Hi,
>> >
>> > Just thought I'd throw something out here. My experience is that I often
>> > take the same graph (as in the exact same data, same objects) but at
>> > different times want to use different weights. So, rather than having
>> Edge
>> > extend Weighted<W>, I'd factor weights out into their own interface:
>> >
>> > /**
>> > * An edge weight function.
>> > *
>> > * note: perhaps this should more generally just be a Function1<A, B>, if
>> > we have such a thing handy.
>> > *
>> > * @tparam E edge type
>> > * @tparam W weight type
>> > */
>> > public interface EdgeWeight<E, W> {
>> > public W getWeight(E: Edge);
>> > }
>> >
>> > /**
>> > * A combination of a monoid and comparator that satisfy monotinicity of
>> > the addition operation with respect to the comparator.
>> > *
>> > * ∀a: m.compare(m.zero, a) <= 0
>> > * ∀a,b: m.compare(a, m.append(a, b)) <= 0
>> > */
>> > public interface Monotonic<W> extends Monoid<W>, Comparator<W>
>> >
>> > Also, some algorithms calculate all shortest paths at once, while others
>> > calculate them individually and independently. It's probably even
>> possible
>> > to calculate some lazily. So, the interfaces for shortest paths should
>> > decouple setting up a strategy for all shortest paths from an object that
>> > can be used to fetch a specific shortest path.
>> >
>> > /**
>> > * An algorithm for finding shortest paths between vertices of a graph,
>> > given some edge weighting function and
>> > * a well-behaved combinator for edges between connected vertices.
>> > */
>> > public interface ShortestPathFunction<V extends Vertex, E extends
>> Edge<E>,
>> > G extends DirectedGraph<V, E>, W> {
>> > public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E, W>
>> > weighting, Monotonic<W> combineWith);
>> > }
>> >
>> > /**
>> > * The shortest paths between vertices in a graph.
>> > */
>> > public interface ShortestPathResult<V extends Vertex, E extends Edge<E>,
>> W>
>> > {
>> > public WeightedPath<V, E, W> findShortestPath(V source, V target);
>> > }
>> >
>> > How does that look? You can then have standard implementations of these
>> > things in some static utility class or a spring-friendly resource. The
>> > brute-force algorithms that compute all paths at once would do all the
>> work
>> > in makeResult() and simply store this in some state within the returned
>> > ShortestPathResult. Those that calculate individual pairs on the fly (or
>> > all shortest paths from some vertex) would capture state in makeResult()
>> > and perform the actual computation in findShortestPath().
>> >
>> > Matthew
>> >
>> > On 22 December 2011 16:39, Claudio Squarcella <squarcel@dia.uniroma3.it
>> >wrote:
>> >
>> >> Hi,
>> >>
>> >>
>> >> I highly appreciated the last contributions (thanks guys!) but I also
>> >>> agree on this point, so let's start from the end.
>> >>> I think that, no matter what underlying structure we come up with, the
>> >>> user should be able to specify e.g. a weighted edge with something like
>> >>>
>> >>> public class MyEdge implements Edge, Weighted<Double> { ... }
>> >>>
>> >>> and be able to immediately use it as an input for all the algorithms,
>> >>> without extra steps required. So the average user is happy, while
>> "graph
>> >>> geeks" can dig into advanced capabilities and forge their personalized
>> >>> weights :)
>> >>> I hope we all agree on this as a first step. Complexity comes after.
>> >>>
>> >>> I'll take my time as well to re-think.
>> >>>
>> >>
>> >> I did think and code a bit more. First of all please take a look at the
>> >> updated code: Weighted<W> is an interface (weight W can be any type) and
>> >> all the algorithms require edges to implement Weighted<Double> for now
>> --
>> >> we did not break it that much ;)
>> >>
>> >> About the "HasProperty-vs-Property" question (as in Comparable vs
>> >> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
>> >> only. That is, external classes handle all operations on weights.
>> Downside:
>> >> the # of method parameters would increase linearly with the number of
>> >> properties, but I can live with that (how many properties would weights
>> >> have anyway?). On the other hand we have a neat interface for each
>> >> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc)
>> and
>> >> one clean, generic implementation for each algorithm. Dijkstra's
>> signature
>> >> becomes something like:
>> >>
>> >> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
>> extends
>> >> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph,
>> V
>> >> source, V target, Monoid<W> weightMonoid, Comparator<W>
>> weightComparator )
>> >>
>> >> Scary uh? But wait, default implementations for Double, Integer, etc.
>> are
>> >> way easier. E.g. Dijkstra's shortcut for Double:
>> >>
>> >> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
>> >> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
>> findShortestPath(
>> >> G graph, V source, V target )
>> >> {
>> >> return findShortestPath(graph, source, target, new DoubleMonoid(),
>> new
>> >> DoubleComparator());
>> >> }
>> >>
>> >> where DoubleMonoid and DoubleComparator are part of the library.
>> >>
>> >>
>> >> If you guys are fine with this, I'm ready to try and patch [graph] with
>> a
>> >> Christmas gift :)
>> >> 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<
>> http://www.dia.uniroma3.it/~squarcel>
>> >>
>> >>
>> >>
>> ------------------------------**------------------------------**---------
>> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
>> dev-unsubscribe@commons.apache.org>
>> >> For additional commands, e-mail: dev-help@commons.apache.org
>> >>
>> >>
>> >
>> >
>> > --
>> > Dr Matthew Pocock
>> > Integrative Bioinformatics Group, School of Computing Science, Newcastle
>> > University
>> > mailto: turingatemyhamster@gmail.com
>> > gchat: turingatemyhamster@gmail.com
>> > msn: matthew_pocock@yahoo.co.uk
>> > irc.freenode.net: drdozer
>> > skype: matthew.pocock
>> > tel: (0191) 2566550
>> > mob: +447535664143
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Matthew Pocock <tu...@gmail.com>.
Hi Simo,
I guess the 5 minutes to run example would be:
ShortestPathFunction.dijkstra
.makeResult(graph, EdgeWeight.forWeightedEdge, Monotonic.sumDouble)
.findShortestPath(source, target);
I was assuming that there would be standard pallets of all the strategies
available statically in the obvious places. Actually, now I see the code
written out in full like that, I'd perhaps consider renaming makeResult to
`calculate` or `prepare` or some other verb.
Matthew
On 23 December 2011 08:47, Simone Tripodi <si...@apache.org> wrote:
> Hi Matthew!
>
> at a first looks it is really interesting, just give me the time to
> digest because at the same time I had the feeling of a little
> over-engineering activity, I am worried that "5 minutes to run" users
> would find it not so immediate.
>
> Thanks for providing stuff to learn from!
> All the best,
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
> <tu...@gmail.com> wrote:
> > Hi,
> >
> > Just thought I'd throw something out here. My experience is that I often
> > take the same graph (as in the exact same data, same objects) but at
> > different times want to use different weights. So, rather than having
> Edge
> > extend Weighted<W>, I'd factor weights out into their own interface:
> >
> > /**
> > * An edge weight function.
> > *
> > * note: perhaps this should more generally just be a Function1<A, B>, if
> > we have such a thing handy.
> > *
> > * @tparam E edge type
> > * @tparam W weight type
> > */
> > public interface EdgeWeight<E, W> {
> > public W getWeight(E: Edge);
> > }
> >
> > /**
> > * A combination of a monoid and comparator that satisfy monotinicity of
> > the addition operation with respect to the comparator.
> > *
> > * ∀a: m.compare(m.zero, a) <= 0
> > * ∀a,b: m.compare(a, m.append(a, b)) <= 0
> > */
> > public interface Monotonic<W> extends Monoid<W>, Comparator<W>
> >
> > Also, some algorithms calculate all shortest paths at once, while others
> > calculate them individually and independently. It's probably even
> possible
> > to calculate some lazily. So, the interfaces for shortest paths should
> > decouple setting up a strategy for all shortest paths from an object that
> > can be used to fetch a specific shortest path.
> >
> > /**
> > * An algorithm for finding shortest paths between vertices of a graph,
> > given some edge weighting function and
> > * a well-behaved combinator for edges between connected vertices.
> > */
> > public interface ShortestPathFunction<V extends Vertex, E extends
> Edge<E>,
> > G extends DirectedGraph<V, E>, W> {
> > public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E, W>
> > weighting, Monotonic<W> combineWith);
> > }
> >
> > /**
> > * The shortest paths between vertices in a graph.
> > */
> > public interface ShortestPathResult<V extends Vertex, E extends Edge<E>,
> W>
> > {
> > public WeightedPath<V, E, W> findShortestPath(V source, V target);
> > }
> >
> > How does that look? You can then have standard implementations of these
> > things in some static utility class or a spring-friendly resource. The
> > brute-force algorithms that compute all paths at once would do all the
> work
> > in makeResult() and simply store this in some state within the returned
> > ShortestPathResult. Those that calculate individual pairs on the fly (or
> > all shortest paths from some vertex) would capture state in makeResult()
> > and perform the actual computation in findShortestPath().
> >
> > Matthew
> >
> > On 22 December 2011 16:39, Claudio Squarcella <squarcel@dia.uniroma3.it
> >wrote:
> >
> >> Hi,
> >>
> >>
> >> I highly appreciated the last contributions (thanks guys!) but I also
> >>> agree on this point, so let's start from the end.
> >>> I think that, no matter what underlying structure we come up with, the
> >>> user should be able to specify e.g. a weighted edge with something like
> >>>
> >>> public class MyEdge implements Edge, Weighted<Double> { ... }
> >>>
> >>> and be able to immediately use it as an input for all the algorithms,
> >>> without extra steps required. So the average user is happy, while
> "graph
> >>> geeks" can dig into advanced capabilities and forge their personalized
> >>> weights :)
> >>> I hope we all agree on this as a first step. Complexity comes after.
> >>>
> >>> I'll take my time as well to re-think.
> >>>
> >>
> >> I did think and code a bit more. First of all please take a look at the
> >> updated code: Weighted<W> is an interface (weight W can be any type) and
> >> all the algorithms require edges to implement Weighted<Double> for now
> --
> >> we did not break it that much ;)
> >>
> >> About the "HasProperty-vs-Property" question (as in Comparable vs
> >> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
> >> only. That is, external classes handle all operations on weights.
> Downside:
> >> the # of method parameters would increase linearly with the number of
> >> properties, but I can live with that (how many properties would weights
> >> have anyway?). On the other hand we have a neat interface for each
> >> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc)
> and
> >> one clean, generic implementation for each algorithm. Dijkstra's
> signature
> >> becomes something like:
> >>
> >> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
> extends
> >> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph,
> V
> >> source, V target, Monoid<W> weightMonoid, Comparator<W>
> weightComparator )
> >>
> >> Scary uh? But wait, default implementations for Double, Integer, etc.
> are
> >> way easier. E.g. Dijkstra's shortcut for Double:
> >>
> >> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
> >> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
> findShortestPath(
> >> G graph, V source, V target )
> >> {
> >> return findShortestPath(graph, source, target, new DoubleMonoid(),
> new
> >> DoubleComparator());
> >> }
> >>
> >> where DoubleMonoid and DoubleComparator are part of the library.
> >>
> >>
> >> If you guys are fine with this, I'm ready to try and patch [graph] with
> a
> >> Christmas gift :)
> >> 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<
> http://www.dia.uniroma3.it/~squarcel>
> >>
> >>
> >>
> ------------------------------**------------------------------**---------
> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> dev-unsubscribe@commons.apache.org>
> >> For additional commands, e-mail: dev-help@commons.apache.org
> >>
> >>
> >
> >
> > --
> > Dr Matthew Pocock
> > Integrative Bioinformatics Group, School of Computing Science, Newcastle
> > University
> > mailto: turingatemyhamster@gmail.com
> > gchat: turingatemyhamster@gmail.com
> > msn: matthew_pocock@yahoo.co.uk
> > irc.freenode.net: drdozer
> > skype: matthew.pocock
> > tel: (0191) 2566550
> > mob: +447535664143
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi Matthew!
at a first looks it is really interesting, just give me the time to
digest because at the same time I had the feeling of a little
over-engineering activity, I am worried that "5 minutes to run" users
would find it not so immediate.
Thanks for providing stuff to learn from!
All the best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
<tu...@gmail.com> wrote:
> Hi,
>
> Just thought I'd throw something out here. My experience is that I often
> take the same graph (as in the exact same data, same objects) but at
> different times want to use different weights. So, rather than having Edge
> extend Weighted<W>, I'd factor weights out into their own interface:
>
> /**
> * An edge weight function.
> *
> * note: perhaps this should more generally just be a Function1<A, B>, if
> we have such a thing handy.
> *
> * @tparam E edge type
> * @tparam W weight type
> */
> public interface EdgeWeight<E, W> {
> public W getWeight(E: Edge);
> }
>
> /**
> * A combination of a monoid and comparator that satisfy monotinicity of
> the addition operation with respect to the comparator.
> *
> * ∀a: m.compare(m.zero, a) <= 0
> * ∀a,b: m.compare(a, m.append(a, b)) <= 0
> */
> public interface Monotonic<W> extends Monoid<W>, Comparator<W>
>
> Also, some algorithms calculate all shortest paths at once, while others
> calculate them individually and independently. It's probably even possible
> to calculate some lazily. So, the interfaces for shortest paths should
> decouple setting up a strategy for all shortest paths from an object that
> can be used to fetch a specific shortest path.
>
> /**
> * An algorithm for finding shortest paths between vertices of a graph,
> given some edge weighting function and
> * a well-behaved combinator for edges between connected vertices.
> */
> public interface ShortestPathFunction<V extends Vertex, E extends Edge<E>,
> G extends DirectedGraph<V, E>, W> {
> public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E, W>
> weighting, Monotonic<W> combineWith);
> }
>
> /**
> * The shortest paths between vertices in a graph.
> */
> public interface ShortestPathResult<V extends Vertex, E extends Edge<E>, W>
> {
> public WeightedPath<V, E, W> findShortestPath(V source, V target);
> }
>
> How does that look? You can then have standard implementations of these
> things in some static utility class or a spring-friendly resource. The
> brute-force algorithms that compute all paths at once would do all the work
> in makeResult() and simply store this in some state within the returned
> ShortestPathResult. Those that calculate individual pairs on the fly (or
> all shortest paths from some vertex) would capture state in makeResult()
> and perform the actual computation in findShortestPath().
>
> Matthew
>
> On 22 December 2011 16:39, Claudio Squarcella <sq...@dia.uniroma3.it>wrote:
>
>> Hi,
>>
>>
>> I highly appreciated the last contributions (thanks guys!) but I also
>>> agree on this point, so let's start from the end.
>>> I think that, no matter what underlying structure we come up with, the
>>> user should be able to specify e.g. a weighted edge with something like
>>>
>>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>>
>>> and be able to immediately use it as an input for all the algorithms,
>>> without extra steps required. So the average user is happy, while "graph
>>> geeks" can dig into advanced capabilities and forge their personalized
>>> weights :)
>>> I hope we all agree on this as a first step. Complexity comes after.
>>>
>>> I'll take my time as well to re-think.
>>>
>>
>> I did think and code a bit more. First of all please take a look at the
>> updated code: Weighted<W> is an interface (weight W can be any type) and
>> all the algorithms require edges to implement Weighted<Double> for now --
>> we did not break it that much ;)
>>
>> About the "HasProperty-vs-Property" question (as in Comparable vs
>> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
>> only. That is, external classes handle all operations on weights. Downside:
>> the # of method parameters would increase linearly with the number of
>> properties, but I can live with that (how many properties would weights
>> have anyway?). On the other hand we have a neat interface for each
>> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc) and
>> one clean, generic implementation for each algorithm. Dijkstra's signature
>> becomes something like:
>>
>> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends
>> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph, V
>> source, V target, Monoid<W> weightMonoid, Comparator<W> weightComparator )
>>
>> Scary uh? But wait, default implementations for Double, Integer, etc. are
>> way easier. E.g. Dijkstra's shortcut for Double:
>>
>> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
>> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath(
>> G graph, V source, V target )
>> {
>> return findShortestPath(graph, source, target, new DoubleMonoid(), new
>> DoubleComparator());
>> }
>>
>> where DoubleMonoid and DoubleComparator are part of the library.
>>
>>
>> If you guys are fine with this, I'm ready to try and patch [graph] with a
>> Christmas gift :)
>> 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<http://www.dia.uniroma3.it/~squarcel>
>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Matthew Pocock <tu...@gmail.com>.
Hi,
Just thought I'd throw something out here. My experience is that I often
take the same graph (as in the exact same data, same objects) but at
different times want to use different weights. So, rather than having Edge
extend Weighted<W>, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1<A, B>, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeight<E, W> {
public W getWeight(E: Edge);
}
/**
* A combination of a monoid and comparator that satisfy monotinicity of
the addition operation with respect to the comparator.
*
* ∀a: m.compare(m.zero, a) <= 0
* ∀a,b: m.compare(a, m.append(a, b)) <= 0
*/
public interface Monotonic<W> extends Monoid<W>, Comparator<W>
Also, some algorithms calculate all shortest paths at once, while others
calculate them individually and independently. It's probably even possible
to calculate some lazily. So, the interfaces for shortest paths should
decouple setting up a strategy for all shortest paths from an object that
can be used to fetch a specific shortest path.
/**
* An algorithm for finding shortest paths between vertices of a graph,
given some edge weighting function and
* a well-behaved combinator for edges between connected vertices.
*/
public interface ShortestPathFunction<V extends Vertex, E extends Edge<E>,
G extends DirectedGraph<V, E>, W> {
public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E, W>
weighting, Monotonic<W> combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResult<V extends Vertex, E extends Edge<E>, W>
{
public WeightedPath<V, E, W> findShortestPath(V source, V target);
}
How does that look? You can then have standard implementations of these
things in some static utility class or a spring-friendly resource. The
brute-force algorithms that compute all paths at once would do all the work
in makeResult() and simply store this in some state within the returned
ShortestPathResult. Those that calculate individual pairs on the fly (or
all shortest paths from some vertex) would capture state in makeResult()
and perform the actual computation in findShortestPath().
Matthew
On 22 December 2011 16:39, Claudio Squarcella <sq...@dia.uniroma3.it>wrote:
> Hi,
>
>
> I highly appreciated the last contributions (thanks guys!) but I also
>> agree on this point, so let's start from the end.
>> I think that, no matter what underlying structure we come up with, the
>> user should be able to specify e.g. a weighted edge with something like
>>
>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>
>> and be able to immediately use it as an input for all the algorithms,
>> without extra steps required. So the average user is happy, while "graph
>> geeks" can dig into advanced capabilities and forge their personalized
>> weights :)
>> I hope we all agree on this as a first step. Complexity comes after.
>>
>> I'll take my time as well to re-think.
>>
>
> I did think and code a bit more. First of all please take a look at the
> updated code: Weighted<W> is an interface (weight W can be any type) and
> all the algorithms require edges to implement Weighted<Double> for now --
> we did not break it that much ;)
>
> About the "HasProperty-vs-Property" question (as in Comparable vs
> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
> only. That is, external classes handle all operations on weights. Downside:
> the # of method parameters would increase linearly with the number of
> properties, but I can live with that (how many properties would weights
> have anyway?). On the other hand we have a neat interface for each
> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc) and
> one clean, generic implementation for each algorithm. Dijkstra's signature
> becomes something like:
>
> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends
> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph, V
> source, V target, Monoid<W> weightMonoid, Comparator<W> weightComparator )
>
> Scary uh? But wait, default implementations for Double, Integer, etc. are
> way easier. E.g. Dijkstra's shortcut for Double:
>
> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath(
> G graph, V source, V target )
> {
> return findShortestPath(graph, source, target, new DoubleMonoid(), new
> DoubleComparator());
> }
>
> where DoubleMonoid and DoubleComparator are part of the library.
>
>
> If you guys are fine with this, I'm ready to try and patch [graph] with a
> Christmas gift :)
> 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<http://www.dia.uniroma3.it/~squarcel>
>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
Hi James,
welcome in [graph] :)
DirectGraph is a DataStructure, Dijkstra is an algorithm and would be
better in therms of design keeping algorithms implementation separated
from DS.
Moreover, DirectGraph is an interface - users can provide their own
implementations - so no way to provide complete implementations
there...
Best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Dec 22, 2011 at 6:06 PM, James Ring <sj...@jdns.org> wrote:
> On Dec 22, 2011 8:39 AM, "Claudio Squarcella" <sq...@dia.uniroma3.it>
> wrote:
>>
>> Hi,
>>
>>
>>> I highly appreciated the last contributions (thanks guys!) but I also
> agree on this point, so let's start from the end.
>>> I think that, no matter what underlying structure we come up with, the
> user should be able to specify e.g. a weighted edge with something like
>>>
>>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>>
>>> and be able to immediately use it as an input for all the algorithms,
> without extra steps required. So the average user is happy, while "graph
> geeks" can dig into advanced capabilities and forge their personalized
> weights :)
>>> I hope we all agree on this as a first step. Complexity comes after.
>>>
>>> I'll take my time as well to re-think.
>>
>>
>> I did think and code a bit more. First of all please take a look at the
> updated code: Weighted<W> is an interface (weight W can be any type) and
> all the algorithms require edges to implement Weighted<Double> for now --
> we did not break it that much ;)
>>
>> About the "HasProperty-vs-Property" question (as in Comparable vs
> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
> only. That is, external classes handle all operations on weights. Downside:
> the # of method parameters would increase linearly with the number of
> properties, but I can live with that (how many properties would weights
> have anyway?). On the other hand we have a neat interface for each
> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc) and
> one clean, generic implementation for each algorithm. Dijkstra's signature
> becomes something like:
>>
>> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends
> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph, V
> source, V target, Monoid<W> weightMonoid, Comparator<W> weightComparator )
>>
>> Scary uh? But wait, default implementations for Double, Integer, etc. are
> way easier. E.g. Dijkstra's shortcut for Double:
>>
>> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath(
> G graph, V source, V target )
>> {
>> return findShortestPath(graph, source, target, new DoubleMonoid(), new
> DoubleComparator());
>> }
>>
>> where DoubleMonoid and DoubleComparator are part of the library.
>
> Just a disinterested third party, but wouldn't this method be better as a
> non-static method on DirectedGraph? The signature is much nicer then.
>
>>
>> If you guys are fine with this, I'm ready to try and patch [graph] with a
> Christmas gift :)
>> 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
>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by James Ring <sj...@jdns.org>.
On Dec 22, 2011 8:39 AM, "Claudio Squarcella" <sq...@dia.uniroma3.it>
wrote:
>
> Hi,
>
>
>> I highly appreciated the last contributions (thanks guys!) but I also
agree on this point, so let's start from the end.
>> I think that, no matter what underlying structure we come up with, the
user should be able to specify e.g. a weighted edge with something like
>>
>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>
>> and be able to immediately use it as an input for all the algorithms,
without extra steps required. So the average user is happy, while "graph
geeks" can dig into advanced capabilities and forge their personalized
weights :)
>> I hope we all agree on this as a first step. Complexity comes after.
>>
>> I'll take my time as well to re-think.
>
>
> I did think and code a bit more. First of all please take a look at the
updated code: Weighted<W> is an interface (weight W can be any type) and
all the algorithms require edges to implement Weighted<Double> for now --
we did not break it that much ;)
>
> About the "HasProperty-vs-Property" question (as in Comparable vs
Comparator, MonoidElement vs Monoid, etc) I would go for the second one
only. That is, external classes handle all operations on weights. Downside:
the # of method parameters would increase linearly with the number of
properties, but I can live with that (how many properties would weights
have anyway?). On the other hand we have a neat interface for each
property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc) and
one clean, generic implementation for each algorithm. Dijkstra's signature
becomes something like:
>
> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends
DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph, V
source, V target, Monoid<W> weightMonoid, Comparator<W> weightComparator )
>
> Scary uh? But wait, default implementations for Double, Integer, etc. are
way easier. E.g. Dijkstra's shortcut for Double:
>
> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath(
G graph, V source, V target )
> {
> return findShortestPath(graph, source, target, new DoubleMonoid(), new
DoubleComparator());
> }
>
> where DoubleMonoid and DoubleComparator are part of the library.
Just a disinterested third party, but wouldn't this method be better as a
non-static method on DirectedGraph? The signature is much nicer then.
>
> If you guys are fine with this, I'm ready to try and patch [graph] with a
Christmas gift :)
> 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
>
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
> I highly appreciated the last contributions (thanks guys!) but I also
> agree on this point, so let's start from the end.
> I think that, no matter what underlying structure we come up with, the
> user should be able to specify e.g. a weighted edge with something like
>
> public class MyEdge implements Edge, Weighted<Double> { ... }
>
> and be able to immediately use it as an input for all the algorithms,
> without extra steps required. So the average user is happy, while
> "graph geeks" can dig into advanced capabilities and forge their
> personalized weights :)
> I hope we all agree on this as a first step. Complexity comes after.
>
> I'll take my time as well to re-think.
I did think and code a bit more. First of all please take a look at the
updated code: Weighted<W> is an interface (weight W can be any type) and
all the algorithms require edges to implement Weighted<Double> for now
-- we did not break it that much ;)
About the "HasProperty-vs-Property" question (as in Comparable vs
Comparator, MonoidElement vs Monoid, etc) I would go for the second one
only. That is, external classes handle all operations on weights.
Downside: the # of method parameters would increase linearly with the
number of properties, but I can live with that (how many properties
would weights have anyway?). On the other hand we have a neat interface
for each property/class (Zero, Semigroup, Monoid, Ordering or
Comparator, etc) and one clean, generic implementation for each
algorithm. Dijkstra's signature becomes something like:
public static <V extends Vertex, W, WE extends WeightedEdge<W>, G
extends DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G
graph, V source, V target, Monoid<W> weightMonoid, Comparator<W>
weightComparator )
Scary uh? But wait, default implementations for Double, Integer, etc.
are way easier. E.g. Dijkstra's shortcut for Double:
public static <V extends Vertex, WE extends WeightedEdge<Double>, G
extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double>
findShortestPath( G graph, V source, V target )
{
return findShortestPath(graph, source, target, new DoubleMonoid(),
new DoubleComparator());
}
where DoubleMonoid and DoubleComparator are part of the library.
If you guys are fine with this, I'm ready to try and patch [graph] with
a Christmas gift :)
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
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
On 15/12/2011 14:20, James Carman wrote:
> We may be modeling the domain properly with all of this terminology, but is
> this going to be understandable to the common user?
I highly appreciated the last contributions (thanks guys!) but I also
agree on this point, so let's start from the end.
I think that, no matter what underlying structure we come up with, the
user should be able to specify e.g. a weighted edge with something like
public class MyEdge implements Edge, Weighted<Double> { ... }
and be able to immediately use it as an input for all the algorithms,
without extra steps required. So the average user is happy, while "graph
geeks" can dig into advanced capabilities and forge their personalized
weights :)
I hope we all agree on this as a first step. Complexity comes after.
I'll take my time as well to re-think.
Claudio
> On Dec 15, 2011 7:38 AM, "Matthew Pocock"<tu...@gmail.com>
> wrote:
>
>> Hi,
>>
>> On 15 December 2011 11:35, James Carman<ja...@carmanconsulting.com>
>> wrote:
>>
>>
>>> public interface BinaryOperation<T>
>>> {
>>> public T execute(T operand1, T operand2);
>>> }
>>>
>>> Perhaps we can come up with an interface that combines the two
>>> aspects. I'm trying to think of mathematically what that would be
>>> called. By the way, what do you need to know "HasZero"? A sum
>>> operation has to have a "zero", doesn't it?
>>
>> The mathematical hierarchy goes: semigroup -> monoid.
>>
>> http://en.wikipedia.org/wiki/Semigroup
>> http://en.wikipedia.org/wiki/Monoid
>>
>> You don't need a full group here as you are only interested in a single
>> operation, not a pair of interacting operations. There are several
>> JVM-hosted libraries that model this hierarchy to a greater or lesser
>> degree. scalaz uses:
>>
>> trait Semigroup[S] {
>> def append(s1: S
>> <
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
>>> ,
>> s2: => S): S<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
>> }
>>
>> trait Zero[Z] {
>> val zero: Z<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160
>> }
>>
>> trait Monoid[M] extends Zero
>> <
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
>>> [M]
>> with Semigroup<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
>>> [M]
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html
>>
>> If you're not used to reading scala, here's the essentially equivalent
>> definitions in Java:
>>
>> public interface Semigroup<S> {
>> public S append(S s1, S s2);
>> }
>>
>> public interface Zero<Z> {
>>
>> public Z zero();
>> }
>>
>> public interface Monoid<M> extends
>> Zero<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
>>> <M>,
>> Semigroup<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
>> <M>
>>
>>
>> So, given that you have Ordering<O> already (or is that Comparator<C>?),
>> I'd say that Weight is defined as:
>>
>> // insert comments here about the consistency of append and compare
>> public interface Weight<W> extends Monoid<W>, Ordered<W>
>>
>> Of course, a sensible default implementation of Weight would delegate to
>> Monoid and Ordered instances and you can then pray to the gods of hotspot
>> to inline this all away.
>>
>> public<W> Weight<W> weight(Monoid<W> m, Ordered<W> o) {
>> new Weight<W>() {
>> public W zero() { return m.zero(); }
>> ...
>> }
>> }
>>
>> Matthew
>>
>> --
>> Dr Matthew Pocock
>> Integrative Bioinformatics Group, School of Computing Science, Newcastle
>> University
>> mailto: turingatemyhamster@gmail.com
>> gchat: turingatemyhamster@gmail.com
>> msn: matthew_pocock@yahoo.co.uk
>> irc.freenode.net: drdozer
>> skype: matthew.pocock
>> tel: (0191) 2566550
>> mob: +447535664143
>>
--
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
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
We may be modeling the domain properly with all of this terminology, but is
this going to be understandable to the common user?
On Dec 15, 2011 7:38 AM, "Matthew Pocock" <tu...@gmail.com>
wrote:
> Hi,
>
> On 15 December 2011 11:35, James Carman <ja...@carmanconsulting.com>
> wrote:
>
>
> > public interface BinaryOperation<T>
> > {
> > public T execute(T operand1, T operand2);
> > }
> >
> > Perhaps we can come up with an interface that combines the two
> > aspects. I'm trying to think of mathematically what that would be
> > called. By the way, what do you need to know "HasZero"? A sum
> > operation has to have a "zero", doesn't it?
>
>
> The mathematical hierarchy goes: semigroup -> monoid.
>
> http://en.wikipedia.org/wiki/Semigroup
> http://en.wikipedia.org/wiki/Monoid
>
> You don't need a full group here as you are only interested in a single
> operation, not a pair of interacting operations. There are several
> JVM-hosted libraries that model this hierarchy to a greater or lesser
> degree. scalaz uses:
>
> trait Semigroup[S] {
> def append(s1: S
> <
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
> >,
> s2: => S): S <
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
> >
> }
>
> trait Zero[Z] {
> val zero: Z <
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160
> >
> }
>
> trait Monoid[M] extends Zero
> <
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
> >[M]
> with Semigroup <
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
> >[M]
>
>
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
>
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
>
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html
>
> If you're not used to reading scala, here's the essentially equivalent
> definitions in Java:
>
> public interface Semigroup<S> {
> public S append(S s1, S s2);
> }
>
> public interface Zero<Z> {
>
> public Z zero();
> }
>
> public interface Monoid<M> extends
> Zero<
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
> ><M>,
> Semigroup<
> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
> >
> <M>
>
>
> So, given that you have Ordering<O> already (or is that Comparator<C>?),
> I'd say that Weight is defined as:
>
> // insert comments here about the consistency of append and compare
> public interface Weight<W> extends Monoid<W>, Ordered<W>
>
> Of course, a sensible default implementation of Weight would delegate to
> Monoid and Ordered instances and you can then pray to the gods of hotspot
> to inline this all away.
>
> public <W> Weight<W> weight(Monoid<W> m, Ordered<W> o) {
> new Weight<W>() {
> public W zero() { return m.zero(); }
> ...
> }
> }
>
> Matthew
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
>
Re: [Graph] On graph weight type(s)
Posted by Matthew Pocock <tu...@gmail.com>.
Hi,
On 15 December 2011 11:35, James Carman <ja...@carmanconsulting.com> wrote:
> public interface BinaryOperation<T>
> {
> public T execute(T operand1, T operand2);
> }
>
> Perhaps we can come up with an interface that combines the two
> aspects. I'm trying to think of mathematically what that would be
> called. By the way, what do you need to know "HasZero"? A sum
> operation has to have a "zero", doesn't it?
The mathematical hierarchy goes: semigroup -> monoid.
http://en.wikipedia.org/wiki/Semigroup
http://en.wikipedia.org/wiki/Monoid
You don't need a full group here as you are only interested in a single
operation, not a pair of interacting operations. There are several
JVM-hosted libraries that model this hierarchy to a greater or lesser
degree. scalaz uses:
trait Semigroup[S] {
def append(s1: S
<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>,
s2: => S): S <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>
}
trait Zero[Z] {
val zero: Z <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160>
}
trait Monoid[M] extends Zero
<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945>[M]
with Semigroup <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>[M]
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html
If you're not used to reading scala, here's the essentially equivalent
definitions in Java:
public interface Semigroup<S> {
public S append(S s1, S s2);
}
public interface Zero<Z> {
public Z zero();
}
public interface Monoid<M> extends
Zero<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945><M>,
Semigroup<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>
<M>
So, given that you have Ordering<O> already (or is that Comparator<C>?),
I'd say that Weight is defined as:
// insert comments here about the consistency of append and compare
public interface Weight<W> extends Monoid<W>, Ordered<W>
Of course, a sensible default implementation of Weight would delegate to
Monoid and Ordered instances and you can then pray to the gods of hotspot
to inline this all away.
public <W> Weight<W> weight(Monoid<W> m, Ordered<W> o) {
new Weight<W>() {
public W zero() { return m.zero(); }
...
}
}
Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
It would be very similar to how we discussed either using Comparable
objects or providing a Comparator. So, you'd either use Summable (or
whatever it's called) objects or allow the user to provide a
BinaryOperation object (that matches the type of course):
public interface BinaryOperation<T>
{
public T execute(T operand1, T operand2);
}
Perhaps we can come up with an interface that combines the two
aspects. I'm trying to think of mathematically what that would be
called. By the way, what do you need to know "HasZero"? A sum
operation has to have a "zero", doesn't it? Well, I guess I'm
considering weights to be a "group" in the abstract algebra sense. If
so, then they'd have to follow the properties of a group and thus
there would exist an identity ("zero" for sum operation) element.
On Wed, Dec 14, 2011 at 7:26 AM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> Hi,
>
>
> On 14/12/2011 12:34, James Carman wrote:
>>
>> I don't like the idea of pushing the adding, comparing, etc. into the
>> weights. I like the idea of having operations external to the weights
>> that take care of that stuff.
>
>
> I would be happy with non-polluted weights, so I am with you. But I am not
> quite sure how to translate that into a good implementation. Do you have an
> idea to share?
>
> Thanks,
>
> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
On 14/12/2011 12:34, James Carman wrote:
> I don't like the idea of pushing the adding, comparing, etc. into the
> weights. I like the idea of having operations external to the weights
> that take care of that stuff.
I would be happy with non-polluted weights, so I am with you. But I am
not quite sure how to translate that into a good implementation. Do you
have an idea to share?
Thanks,
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
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
I don't like the idea of pushing the adding, comparing, etc. into the
weights. I like the idea of having operations external to the weights
that take care of that stuff.
On Tue, Dec 13, 2011 at 12:35 PM, Claudio Squarcella
<sq...@dia.uniroma3.it> wrote:
> 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"<sq...@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"<sq...@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: squarcel@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<de...@commons.apache.org>
>>>>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>>>>
>>>>>>> ------------------------------**------------------------------**
>>>>>
>>>>> ---------
>>>>> To unsubscribe, e-mail:
>>>>> dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>>
>>>>>
>>>> --
>>>> 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<http://www.dia.uniroma3.it/~squarcel>
>>>>
>>>>
>>>>
>>>> ------------------------------**------------------------------**---------
>>>> To unsubscribe, e-mail:
>>>> dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>
>>>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
> --
> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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"<sq...@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"<sq...@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: squarcel@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<de...@commons.apache.org>
>>>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>>>
>>>>>> ------------------------------**------------------------------**
>>>> ---------
>>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>
>>>>
>>> --
>>> 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<http://www.dia.uniroma3.it/~squarcel>
>>>
>>>
>>> ------------------------------**------------------------------**---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
--
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
Re: [Graph] On graph weight type(s)
Posted by Simone Tripodi <si...@apache.org>.
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?
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" <sq...@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"<sq...@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: squarcel@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<de...@commons.apache.org>
>>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>>
>>>>> ------------------------------**------------------------------**
>>> ---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
>> --
>> 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<http://www.dia.uniroma3.it/~squarcel>
>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
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" <sq...@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"<sq...@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: squarcel@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<de...@commons.apache.org>
>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>
>>>> ------------------------------**------------------------------**
>> ---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
> --
> 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<http://www.dia.uniroma3.it/~squarcel>
>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [Graph] On graph weight type(s)
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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).
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"<sq...@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 (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
>>>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
--
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
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
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.
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" <sq...@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 (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
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] On graph weight type(s)
Posted by James Carman <ja...@carmanconsulting.com>.
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" <sq...@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: squarcel@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<de...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org
>
>