Re: [Graph] On graph weight type(s)
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 marco.speranz...@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 squar...@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: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org smime.p7s Description: S/MIME cryptographic signature
Re: [Graph] On graph weight type(s)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 ).applyingAlgorithm( 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 ).applyingAlgorithm( OrderMonoid ) ) API. WDYT ? ciao -- Marco Speranza marco.speranz...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org smime.p7s Description: S/MIME cryptographic signature
Re: [Graph] On graph weight type(s)
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 marco.speranz...@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 ).applyingAlgorithm( 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 ).applyingAlgorithm( OrderMonoid ) ) API. WDYT ? ciao -- Marco Speranza marco.speranz...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 ).applyingAlgorithm( 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@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 ).applyingAlgorithm( 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@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: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
On Sat, Feb 11, 2012 at 8:53 PM, Claudio Squarcella squar...@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)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@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: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org -- Claudio Squarcella PhD student at Roma Tre University E-mail address: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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, squar...@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 simonetrip...@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
turingatemyhams...@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 simonetrip...@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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own
interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A,
B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends
EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph,
EdgeWeightE,
W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends
EdgeE,
W
{
public WeightedPathV, 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
Re: [Graph] On graph weight type(s)
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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A, B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph, EdgeWeightE, W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends EdgeE, W
{
public WeightedPathV, 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 squar...@dia.uniroma3.itwrote:
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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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 WeightedEdgeW, G extends
DirectedGraphV, WE WeightedPathV, WE, W findShortestPath( G graph, V
source, V target, MonoidW weightMonoid, ComparatorW 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 WeightedEdgeDouble, G
extends DirectedGraphV, WE WeightedPathV, WE, Double findShortestPath(
G graph, V source, V target )
{
return
Re: [Graph] On graph weight type(s)
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 simonetrip...@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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A, B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends
EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph, EdgeWeightE, W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends EdgeE,
W
{
public WeightedPathV, 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 squar...@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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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,
Re: [Graph] On graph weight type(s)
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
turingatemyhams...@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 simonetrip...@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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A, B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends
EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph, EdgeWeightE, W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends EdgeE,
W
{
public WeightedPathV, 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 squar...@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, WeightedDouble { ... }
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
Re: [Graph] On graph weight type(s)
On 23 December 2011 10:38, Simone Tripodi simonetrip...@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
turingatemyhams...@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 simonetrip...@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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A,
B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends
EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph, EdgeWeightE,
W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends
EdgeE,
W
{
public WeightedPathV, 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
squar...@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, WeightedDouble { ... }
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.
Re: [Graph] On graph weight type(s)
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 simonetrip...@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
turingatemyhams...@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 simonetrip...@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
turingatemyhams...@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 WeightedW, I'd factor weights out into their own
interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A,
B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends
EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph,
EdgeWeightE,
W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends
EdgeE,
W
{
public WeightedPathV, 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
squar...@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
Re: [Graph] On graph weight type(s)
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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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 WeightedEdgeW, G
extends DirectedGraphV, WE WeightedPathV, WE, W findShortestPath( G
graph, V source, V target, MonoidW weightMonoid, ComparatorW
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 WeightedEdgeDouble, G
extends DirectedGraphV, WE WeightedPathV, 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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
On Dec 22, 2011 8:39 AM, Claudio Squarcella squar...@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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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 WeightedEdgeW, G extends
DirectedGraphV, WE WeightedPathV, WE, W findShortestPath( G graph, V
source, V target, MonoidW weightMonoid, ComparatorW 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 WeightedEdgeDouble, G
extends DirectedGraphV, WE WeightedPathV, 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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 s...@jdns.org wrote:
On Dec 22, 2011 8:39 AM, Claudio Squarcella squar...@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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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 WeightedEdgeW, G extends
DirectedGraphV, WE WeightedPathV, WE, W findShortestPath( G graph, V
source, V target, MonoidW weightMonoid, ComparatorW 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 WeightedEdgeDouble, G
extends DirectedGraphV, WE WeightedPathV, 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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 WeightedW, I'd factor weights out into their own interface:
/**
* An edge weight function.
*
* note: perhaps this should more generally just be a Function1A, B, if
we have such a thing handy.
*
* @tparam E edge type
* @tparam W weight type
*/
public interface EdgeWeightE, 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 MonotonicW extends MonoidW, ComparatorW
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 ShortestPathFunctionV extends Vertex, E extends EdgeE,
G extends DirectedGraphV, E, W {
public ShortestPathResultV, E, W makeResult(G graph, EdgeWeightE, W
weighting, MonotonicW combineWith);
}
/**
* The shortest paths between vertices in a graph.
*/
public interface ShortestPathResultV extends Vertex, E extends EdgeE, W
{
public WeightedPathV, 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 squar...@dia.uniroma3.itwrote:
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, WeightedDouble { ... }
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: WeightedW is an interface (weight W can be any type) and
all the algorithms require edges to implement WeightedDouble 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 WeightedEdgeW, G extends
DirectedGraphV, WE WeightedPathV, WE, W findShortestPath( G graph, V
source, V target, MonoidW weightMonoid, ComparatorW 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 WeightedEdgeDouble, G
extends DirectedGraphV, WE WeightedPathV, 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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~**squarcelhttp://www.dia.uniroma3.it/~squarcel
--**--**-
To unsubscribe, e-mail:
Re: [Graph] On graph weight type(s)
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 BinaryOperationT
{
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
squar...@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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
Hi,
On 15 December 2011 11:35, James Carman ja...@carmanconsulting.com wrote:
public interface BinaryOperationT
{
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 SemigroupS {
public S append(S s1, S s2);
}
public interface ZeroZ {
public Z zero();
}
public interface MonoidM extends
Zerohttp://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945M,
Semigrouphttp://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
M
So, given that you have OrderingO already (or is that ComparatorC?),
I'd say that Weight is defined as:
// insert comments here about the consistency of append and compare
public interface WeightW extends MonoidW, OrderedW
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 WeightW weight(MonoidW m, OrderedW o) {
new WeightW() {
public W zero() { return m.zero(); }
...
}
}
Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
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
turingatemyhams...@gmail.com wrote:
Hi,
On 15 December 2011 11:35, James Carman ja...@carmanconsulting.com wrote:
public interface BinaryOperationT
{
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 SemigroupS {
public S append(S s1, S s2);
}
public interface ZeroZ {
public Z zero();
}
public interface MonoidM extends
Zerohttp://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945M,
Semigrouphttp://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
M
So, given that you have OrderingO already (or is that ComparatorC?),
I'd say that Weight is defined as:
// insert comments here about the consistency of append and compare
public interface WeightW extends MonoidW, OrderedW
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 WeightW weight(MonoidW m, OrderedW o) {
new WeightW() {
public W zero() { return m.zero(); }
...
}
}
Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 turingatemyhams...@gmail.com
wrote:
Hi,
On 15 December 2011 11:35, James Carman ja...@carmanconsulting.com
wrote:
public interface BinaryOperationT
{
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 SemigroupS {
public S append(S s1, S s2);
}
public interface ZeroZ {
public Z zero();
}
public interface MonoidM 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 OrderingO already (or is that ComparatorC?),
I'd say that Weight is defined as:
// insert comments here about the consistency of append and compare
public interface WeightW extends MonoidW, OrderedW
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 WeightW weight(MonoidW m, OrderedW o) {
new WeightW() {
public W zero() { return m.zero(); }
...
}
}
Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
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, WeightedDouble { ... }
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 Pocockturingatemyhams...@gmail.com
wrote:
Hi,
On 15 December 2011 11:35, James Carmanja...@carmanconsulting.com
wrote:
public interface BinaryOperationT
{
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 SemigroupS {
public S append(S s1, S s2);
}
public interface ZeroZ {
public Z zero();
}
public interface MonoidM 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 OrderingO already (or is that ComparatorC?),
I'd say that Weight is defined as:
// insert comments here about the consistency of append and compare
public interface WeightW extends MonoidW, OrderedW
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.
publicW WeightW weight(MonoidW m, OrderedW o) {
new WeightW() {
public W zero() { return m.zero(); }
...
}
}
Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
Hi, trying to put it all together (thanks James, Matthew): * WeightedW 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 WeightedDouble 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org -- Claudio Squarcella PhD student at Roma Tre University E-mail address: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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
squar...@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):
* WeightedW 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 Squarcellasquar...@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 {{WeightedDouble}}, or {{WeightedInteger}}, 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-numbershttp://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers
).
Summing up:
* {{public interface WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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
Squarcellasquarcel@dia.**uniroma3.itsquar...@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.pdfhttp://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
Re: [Graph] On graph weight type(s)
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: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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):
* WeightedW 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 Squarcellasquar...@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 {{WeightedDouble}}, or {{WeightedInteger}}, 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-numbershttp://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers
).
Summing up:
* {{public interface WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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.comwrote:
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
Squarcellasquarcel@dia.**uniroma3.itsquar...@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.pdfhttp://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,
Re: [Graph] On graph weight type(s)
Hola Claudio! On Tue, Dec 13, 2011 at 6:35 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hey Simone, trying to put it all together (thanks James, Matthew): * WeightedW 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@dia.uniroma3.it
wrote:
Hi all,
I explored a bit more the (rather philosophical) dilemma that came from
a
thread from last week, quoted below
One step further. A weight is not necessarily a double: in some cases
not
even a number, but rather a comparable of some sort. So I would
suggest to
make use of generics in some way, possibly the smartest. Suggestions
are
welcome :-)
The question is: *what do we mean by weight when dealing with graphs?*
Real number is a standard answer in graph theory: see, e.g.,
http://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf (pag.
15).
What we have now in the code is a {{getWeight()}} method that returns a
double. That serves well for all the algorithms currently implemented,
and
probably for many more to come. However it is also true that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
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 {{WeightedDouble}}, or {{WeightedInteger}}, 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 WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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 Squarcellasquar...@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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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
turingatemyhams...@gmail.com wrote:
Hi,
I have tended to find that edge weights always follow the following laws:
They have a monoid:
There is a zero (0) constant and a |+| operator for combining two weights.
They have an equivalence and (compatible) ordering relations (, =):
The ordering is compatible with the monoid. For example,
a |+| 0 = 0
a |+| b = a
a |+| b = b |+| a
a = 0
a != 0, b != 0 = a |+| b a
Taken together, the algorithms for things like shortest-path or
weighted-k-neighbourhood can all be expressed, abstracted away from the
weight datatype, the operations for combining weights, and the operations
for comparing weights.
If you choose your ordering then you can derive the compatible min monoid
where a |+| b = min(a, b). If you use the natural ordering on numbers then
you commonly use the monoids (0, +) or (1, *).
However, I've had cases where the individual weights and accumulated
path-traversal weights are complex structures. This isn't a problem, as
long as there's a zero and |+| for these 'weight' structures, and a
well-behaved ordering over these structures.
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 squar...@dia.uniroma3.it
wrote:
Hi all,
I explored a bit more the (rather philosophical) dilemma that came from
a
thread from last week, quoted below
One step further. A weight is not necessarily a double: in some cases
not
even a number, but rather a comparable of some sort. So I would
suggest to
make use of generics in some way, possibly the smartest. Suggestions
are
welcome :-)
The question is: *what do we mean by weight when dealing with graphs?*
Real number is a standard answer in graph theory: see, e.g.,
http://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf (pag.
15).
What we have now in the code is a {{getWeight()}} method that returns a
double. That serves well for all the algorithms currently implemented,
and
probably for many more to come. However it is also true that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
Re: [Graph] On graph weight type(s)
On 12/12/2011 15:34, Simone Tripodi wrote: Terrific feedback Matthew, thanks a lot! and glad to see researchers here :) Thank you indeed :) I'll take that as valuable input. Claudio best, -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Mon, Dec 12, 2011 at 3:27 PM, Matthew Pocock turingatemyhams...@gmail.com wrote: Hi, I have tended to find that edge weights always follow the following laws: They have a monoid: There is a zero (0) constant and a |+| operator for combining two weights. They have an equivalence and (compatible) ordering relations (, =): The ordering is compatible with the monoid. For example, a |+| 0 = 0 a |+| b= a a |+| b = b |+| a a= 0 a != 0, b != 0 = a |+| b a Taken together, the algorithms for things like shortest-path or weighted-k-neighbourhood can all be expressed, abstracted away from the weight datatype, the operations for combining weights, and the operations for comparing weights. If you choose your ordering then you can derive the compatible min monoid where a |+| b = min(a, b). If you use the natural ordering on numbers then you commonly use the monoids (0, +) or (1, *). However, I've had cases where the individual weights and accumulated path-traversal weights are complex structures. This isn't a problem, as long as there's a zero and |+| for these 'weight' structures, and a well-behaved ordering over these structures. -- Claudio Squarcella PhD student at Roma Tre University E-mail address: squar...@dia.uniroma3.it Phone: +39-06-57333215 Fax: +39-06-57333612 http://www.dia.uniroma3.it/~squarcel - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
Why do you need doubles for Dijkstra? Accumulating the total path
weights? Why not introduce an Accumulator interface?
On Dec 12, 2011 9:32 AM, Claudio Squarcella squar...@dia.uniroma3.it
wrote:
Hi,
On 12/12/2011 05:39, James Carman wrote:
Sorry, I was on my phone before when I sent that. Let me elaborate a
bit more. I would just allow the weights to be of any type. However,
you can create two different types of scenarios where you either use a
Comparable derivative or you use whatever you want, but you have to
supply a custom Comparator.
ok it definitely makes sense, thanks :)
The thing is: in case the weight is actually a number I would really like
to keep it simple on the user side, i.e. it should be usable with something
like {{WeightedDouble}}, or {{WeightedInteger}}, 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-numbershttp://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers
).
Summing up:
* {{public interface WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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
Squarcellasquarcel@dia.**uniroma3.itsquar...@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.pdfhttp://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf(pag.
15).
What we have now in the code is a {{getWeight()}} method that returns a
double. That serves well for all the algorithms currently implemented,
and
probably for many more to come. However it is also true that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~**squarcelhttp://www.dia.uniroma3.it/~squarcel
--**--**
-
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.orgdev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--**--**
-
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.orgdev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address:
Re: [Graph] On graph weight type(s)
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 squar...@dia.uniroma3.it
wrote:
Hi,
On 12/12/2011 05:39, James Carman wrote:
Sorry, I was on my phone before when I sent that. Let me elaborate a
bit more. I would just allow the weights to be of any type. However,
you can create two different types of scenarios where you either use a
Comparable derivative or you use whatever you want, but you have to
supply a custom Comparator.
ok it definitely makes sense, thanks :)
The thing is: in case the weight is actually a number I would really like
to keep it simple on the user side, i.e. it should be usable with something
like {{WeightedDouble}}, or {{WeightedInteger}}, 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-numbershttp://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers
).
Summing up:
* {{public interface WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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
Squarcellasquarcel@dia.**uniroma3.itsquar...@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.pdfhttp://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf(pag.
15).
What we have now in the code is a {{getWeight()}} method that returns a
double. That serves well for all the algorithms currently implemented,
and
probably for many more to come. However it is also true that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
Re: [Graph] On graph weight type(s)
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 simonetrip...@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 squar...@dia.uniroma3.it
wrote:
Hi,
On 12/12/2011 05:39, James Carman wrote:
Sorry, I was on my phone before when I sent that. Let me elaborate a
bit more. I would just allow the weights to be of any type. However,
you can create two different types of scenarios where you either use a
Comparable derivative or you use whatever you want, but you have to
supply a custom Comparator.
ok it definitely makes sense, thanks :)
The thing is: in case the weight is actually a number I would really
like
to keep it simple on the user side, i.e. it should be usable with
something
like {{WeightedDouble}}, or {{WeightedInteger}}, 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 WeightedW}} with method {{public W getWeight()}}
* weighted things ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
implement it, e.g. {{public interface WeightedEdgeE,W extends
EdgeE, WeightedW}}
* 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 Squarcellasquarcel@dia.**
uniroma3.itsquar...@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;
*
[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: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@dia.uniroma3.it
wrote:
Hi all,
I explored a bit more the (rather philosophical) dilemma that came from a
thread from last week, quoted below
One step further. A weight is not necessarily a double: in some cases not
even a number, but rather a comparable of some sort. So I would suggest
to make use of generics in some way, possibly the smartest. Suggestions are
welcome :-)
The question is: *what do we mean by weight when dealing with graphs?*
Real number is a standard answer in graph theory: see, e.g.,
http://www.math.jussieu.fr/~**jabondy/books/gtwa/pdf/**chapter1.pdfhttp://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf(pag.
15). What we have now in the code is a {{getWeight()}} method that
returns a double. That serves well for all the algorithms currently
implemented, and probably for many more to come. However it is also true
that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~**squarcelhttp://www.dia.uniroma3.it/~squarcel
--**--**-
To unsubscribe, e-mail:
dev-unsubscribe@commons.**apache.orgdev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [Graph] On graph weight type(s)
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 squar...@dia.uniroma3.it
wrote:
Hi all,
I explored a bit more the (rather philosophical) dilemma that came from a
thread from last week, quoted below
One step further. A weight is not necessarily a double: in some cases not
even a number, but rather a comparable of some sort. So I would suggest to
make use of generics in some way, possibly the smartest. Suggestions are
welcome :-)
The question is: *what do we mean by weight when dealing with graphs?*
Real number is a standard answer in graph theory: see, e.g.,
http://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf (pag. 15).
What we have now in the code is a {{getWeight()}} method that returns a
double. That serves well for all the algorithms currently implemented, and
probably for many more to come. However it is also true that:
* some domains of interest and/or algorithms might be more restrictive
on the type and sign of real number for the weights: integers,
non-negative rationals, etc.
* strictly speaking, the basic operations associated with weights are
usually just a few. Comparison and sum are enough at least for the
algorithms implemented so far in the project (please correct me if I
am wrong). Maybe scaling? Additive inverse?
* each algorithm is aware of the subset of required operations. E.g.
Prim's algorithm for minimum spanning trees only requires edge
weights to be comparable, so they could even be Strings or whatever...
* some very abstract user might want to use a new class (not
necessarily a number) as a weight, provided that it meets the
requirements of the domain.
So here is a high-level view of what I propose:
* the basic weight is nothing more than a {{Comparable}}, which is
hopefully generic enough;
* where needed, algorithms define more specific constraints on the
input graph in their signature (e.g. Dijkstra can use {{Double}}).
Looking forward for comments,
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
