Details

Type: Improvement

Status: Open

Priority: Major

Resolution: Unresolved

Affects Version/s: None

Fix Version/s: None

Component/s: Graph

Labels:None
Description
As discussed on dev@, Zero, Semigroup and Monoid can be merged directly in one single interface

 SANDBOX404.patch
 14 kB
 Simone Tripodi

 SANDBOX404_gettingRidOfOrderedMonoid.patch
 47 kB
 Claudio Squarcella

 SANDBOX404_FromMonoidToAddition.patch
 58 kB
 Claudio Squarcella
Activity
Hi Simone,
you were convincing
I just reverted that change and only committed the solution for the issue you discovered (see r1299232).
Claudio
Now, secondary issue: while looking for a solution I also noticed that SpanningTree did not have a generic type for the type of weight operations (i.e. the variable in MutableSpanningTree had explicit type Monoid<W>). So as a first attempt to fix the error I added WO as a generic type in SpanningTree and modified all the classes using it.
It is not an issue, it is not broken in my branch (at least).
Why should it matter which type of Monoid the spanning trees are using, at APIs level? They don't add any value to execute algorithms.
If you can take a look at the experimental branch, I simplified a lot also the chain builders signatures, getting rid of useless generic types.
For what I've experienced, the only types that really matter are Vertices V, Edges E and Weights W (and Graph and its specializations)
Hi,
I found it. All the above errors were caused by the tests using null weight operations, while the compiler expects an explicit type. So as a workaround I just added casts to existing types: see the example below.
Before:
findShortestPath( graph ).from( a ).to( b ).applyingDijkstra( null );
After:
findShortestPath( graph ).from( a ).to( b ).applyingDijkstra( (DoubleWeightBaseOperations) null );
Now, secondary issue: while looking for a solution I also noticed that SpanningTree did not have a generic type for the type of weight operations (i.e. the variable in MutableSpanningTree had explicit type Monoid<W>). So as a first attempt to fix the error I added WO as a generic type in SpanningTree and modified all the classes using it.
Is it ok if I commit both changes together? (and since we're here, I can also do the same for InMemoryWeightedPath that still uses Monoid<W>).
Claudio
Hi Simone,
thanks for the notice. Working on it now!
Hi Claudio,
unfortunately the patch you committed doesn't work when launching tests from CLI (OTOH works well inside eclipse), follows below the errors I got:
$ svn info Path: . URL: https://svn.apache.org/repos/asf/commons/sandbox/graph/trunk Repository Root: https://svn.apache.org/repos/asf Repository UUID: 13f7953547bb03109956ffa450edef68 Revision: 1299097 Node Kind: directory Schedule: normal Last Changed Author: cs Last Changed Rev: 1298136 Last Changed Date: 20120307 22:34:21 +0100 (Wed, 07 Mar 2012) ... mvn clean test ... [ERROR] COMPILATION ERROR : [INFO]  [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java:[77,63] type parameters of <WO>org.apache.commons.graph.shortestpath.AllVertexPairsShortestPath<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double,WO> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java:[71,77] type parameters of <WO>org.apache.commons.graph.SpanningTree<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java:[98,65] type parameters of <WO>org.apache.commons.graph.shortestpath.HeuristicBuilder<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double,org.apache.commons.graph.model.UndirectedMutableWeightedGraph<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double>,WO> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java:[53,67] type parameters of <WO>org.apache.commons.graph.SpanningTree<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java:[71,77] type parameters of <WO>org.apache.commons.graph.SpanningTree<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java:[69,68] type parameters of <WO>org.apache.commons.graph.WeightedPath<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [ERROR] /private/tmp/graph/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java:[71,77] type parameters of <WO>org.apache.commons.graph.SpanningTree<org.apache.commons.graph.model.BaseLabeledVertex,org.apache.commons.graph.model.BaseLabeledWeightedEdge<java.lang.Double>,java.lang.Double> cannot be determined; no unique maximal instance exists for type variable WO with upper bounds java.lang.Object,org.apache.commons.graph.weight.Monoid<java.lang.Double>,java.util.Comparator<java.lang.Double> [INFO] 7 errors [INFO]  [INFO]  [INFO] BUILD FAILURE [INFO]  [INFO] Total time: 47.856s [INFO] Finished at: Sat Mar 10 00:23:30 CET 2012 [INFO] Final Memory: 16M/2039M [INFO] 
I am going to partially merge it on my experimental branch
Hi,
just a quick notice to confirm that I just committed the modifications contained in the second patch posted above (see r1298136)
Claudio
please don't shutdown because this is a matter of making the component good software, not just writing code!
So I deduce that having an interface to define the behavior is not enough, users are still able to create an Addition instance and implement the multiplication operator inside  it doesn't matter how we call it... uhmmmm...
Hi,
one question left from my side and then I shutdown ( ): why would you still call Monoid something which in all the algorithms is actually used and seen as an Addition?
Hi Claudio!
I still don't understand how the rename simplifies the actual scenario design: I suppose that users with the need to calculate a Strongly Connected Component on their graph data are enough educated that should understand basic Algebra, if even a B.Sc. like me does I suppose everybody does
The only way to evaluate the if and when condition is IMHO listing at least one graph algorithm that requires a different Monoid to perform its execution, otherwise no needs to model something unused.
Hi Simone!
I completely agree with your last sentence, and that is one of the reasons why I am providing this extended patch where there is no Monoid anymore, only Addition – simplification of the weight operations model!
No use for theoretical algebra in the code: only clear, unambiguous names (sum, negate, zero). I think that is a primary concern as long as we have the power to improve semantics before things go "live" (releases, people using the library consistently and getting used to class names, etc). Also, no risk to extend Monoid twice if and when we add Multiplication or whatsoever, because it will be totally independent.
Hoping to meet your agreement and the one of others working on our beloved [graph]
Claudio
Until there will be real need of adding new Monoid implementations, I would suggest to postpone the problem and keep your version of the patch.
Let's fight with the right weapons when we need, I wouldn't use a katana to kill a fly (unless I am Bruce Willis and I'm in Pulp Fiction )
best and thanks!
Simo
Hi!
First things first:
My idea is to completely get rid of Monoid, in favor of a group of interfaces directly representing operations. In the specific case, Addition would immediately "take its place" not semantically but functionally, to cover algorithm needs – indeed so far we compute "additions" and not generic "monoid operations", so that would also increase consistency and readability. It would look more or less like this:
public interface Addition<E> { E sum(E e1, E e2); E zero(); E negate(E e); }
In case later we want to add Multiplication it will be totally independent, as explained in my first comment above. Something like:
public interface Multiplication<E> { E multiply(E e1, E e2); E one(); // or "identity()", we'll see E reciprocal(E e); }
As for the signature change, I did it because I would prefer not to stack interfaces on top of each other like we did with Zero, Semigroup, Monoid and OrderedMonoid. As long as we can easily write in the signatures all the individual properties we need (in the example Addition and Comparator) we can avoid to add interfaces like ComparableAddition, ComparableMultiplication, ComparableAdditionMultiplication... see my point?
Concluding: I can work on Addition if, and as soon as, we agree.
Ciao,
Claudio
hola,
having a look at the patch I am not really happy on how signatures heavily changed, once dropped the OrderedMonoid, but I can safety live with it.
The rename instead doesn't convince me at all: Monoid perfectly reflects the monoid definition  it is an interface indeed  Addition is one monoid instance. What is we have to add more Monoid operations? Do you intend to create new monoid for each operation?
Hi Simone,
I am attaching a patch that begins with yours and goes one step further, getting rid of OrderedMonoid basically everywhere (although I did not delete OrderedMonoid itself for now) and replacing it with Monoid & Comparator. That has two reasons:
 separating main operations/properties, so that every algorithm specifies what is needed in terms of a set of interfaces;
 leading the way to the next refactoring step where Monoid is converted into Addition, in order to better represent what it actually does.
So one step is missing, i.e. renaming Monoid to Addition (and Monoid#append to Addition#sum, etc) – but first I want to get some feedback on this one.
Ciao
Claudio
Hi Simo,
good that you moved discussion here so that we can focus.
I don't know if I got your question correctly, but I have answers for both interpretations
 what if our class has to implement two different kinds of Monoid (e.g. Addition and Multiplication)? I propose to convert our current Monoid to Addition to represent the sum operation (which indeed is how we use it right know). Then we can add Multiplication as a completely separate interface, without the need to be backed by the same "abstract monoid" (although, of course, theory tells us that they are both monoids):
public class DoubleOperations implements Addition, Comparator, Multiplication { ... }
 what if our class has to be not just a Monoid, but also something else? Then we simply add a new interface. I am already thinking of clearly separating Monoid/Addition from Comparator (see code snippet above). Algorithms can still enumerate all properties/operations they need, for example:
public <WO extends Addition<W> & Comparator<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations ) { ... }
Ciao
Claudio
Ciao Claudio,
Thanks for the feedbacks, anyway I think it worths analyzing more deeply how to disambiguate cases in wich our concrete implementations have the need to implement more than Monoid at the same time, before applying the patch.
I hijacked specific discussion here because in the ML we were speaking about 2 different topics, having a spike to speak about should drive us in the right direction.
going offline in a while until tonight, best and have a nice WE,
Simo
Hi Simone,
I applied the patch and it looks good to me, please go ahead
I would suggest to keep this issue open for further changes to weight operations that were proposed in ML – maybe renaming it to "simplify weight model"?
Ciao
Claudio
attached solution, just need a review before committing it
great, thanks a lot!!!
instead of enjoying vacations, can you please apply the same change on the branch? It would simplify the future merge, if accepted.
TIA, all the best!
Simo
PS I was obviously joking