Re: [Graph] the future of commons-graph and modularization
Hi Simone and all,
good to see activity on commons-graph :-)
I am currently using it for a research project in my lab, so hopefully
I'll be able to come back with more feedback. In the meantime I agree
with what you guys wrote so far.
Cheers,
Claudio
On 26/05/2013 20:46, Simone Tripodi wrote:
Hi Rodion,
Might the API look like this?
[...]
more or less :) Introducing kind of PathFinder interface, as main
entry point for shortest path algorithms, but keeping the current chin
builders - as you notice, `withEuristhic` makes sense for A* only,
when current fluent interfaces drive users on choosing the right
algorithm, with right inputs, via a state-machine which is clever
than a simple builder pattern.
Anyway
This would seem like eliminating the need for CommonsGraph -monolith at the
cost of introducing new interfaces/abstract base classes for every type of
algos out there, plus the actual implementation classes implementing the
API.
you got the idea, nice to see we are on the same path!!! :)
I'll prepare a more concrete proposal in a branch, hope to read
reviews from your side! :)
All the best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sun, May 26, 2013 at 6:10 PM, Rodion Efremov
rodion.efre...@cs.helsinki.fi wrote:
Simone Tripodi kirjoitti 26.05.2013 18:35:
Hi all, mates,
after a long while I haven't touched commons-graph, I had the
opportunity to get influenced by some activities at my paid work that
made me think twice on what as been already done in that component,
and would like to bring new experiences in.
So, what I still like about it:
* graph APIs: the use of generics make the usage of graphes
extensible and adaptable;
* fluent APIs: this is the most powerful feature IMHO that simplifies
the APIs usage;
What I *don't* like anymore:
* poor modularization: commons-graph is ATM a big fat monolith;
* one single entry-point; for each new family of algorithm(s), new
methods have to be added in the main Commons-Graph class.
What I would like to propose to work _in a separated branch_, is
trying to split the big monolith in smaller modules and separate APIs
from related implementation as much as possible.
Questions are:
* WDYT? :)
Might the API look like this?
public interface PathFinderV, E, W {
public PathV, E search();
public PathFinderV, E, W from( V source );
public PathFinderV, E, W to( V target );
public PathFinderV, E, W withHeuristic( HeuristicFunctionV, W f );
// for A* search.
}
... and then we would have, say, A* as follows:
public class AStarFinderV, E, W implements PathFinderV, E, W {
public PathV, E search() {
// A* magic here.
}
... implement the rest.
}
... with usage as follows:
PathV, E path = new AStarFinderV, E, W().withHeuristic( myFunkyHeuristic
).from( source ).to( target ).search();
This would seem like eliminating the need for CommonsGraph -monolith at the
cost of introducing new interfaces/abstract base classes for every type of
algos out there, plus the actual implementation classes implementing the
API.
* About release process: would it be acceptable, here in commons,
release a single module - the only one that has been changed, I mean -
without releasing the whole project?
* In case the answer to previous question is no, would it make
sense moving commons-graph to the Incubator (and possibly to TLP)?
TIA, 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
-
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
http://www.dia.uniroma3.it/~squarcel
http://twitter.com/hyperboreans
http://claudiosquarcella.com/
-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph] renaming packages
Hi, On 03/08/2012 15:00, Simone Tripodi wrote: ¡Hola! Also remember that if we ever want to deal with, say, multiplications, monoids are only going to be in the way (we already touched this topic before, see [1]). I'm still happy to update and simplify names, only following a different pattern: e.g. from DoubleWeightBaseOperations to DoubleOperations. And I'd also replace Monoid with Addition. yeah thanks of the reminder - I was searching for it in the mail archives and didn't find it :P wouldn't Multiplication have exactly the same methods signature of Addition aka Monoid? I wouldn't replicate stuff just to implement markers... Addition would have signatures like sum and negate, while Multiplication would have multiply and invert. Anyway I agree that algorithms need specific monoids, such as Dijkstra that needs Addition - guess it wouldn't work with Subtractions :P What about having Monoid with package visibility and then Addition/Multiplication... extends Monoid ? Then it would become a bit painless if a class had to implement both interfaces (the current Integer[...]Operations is an example). I'd just have them fully independent from each other, without a common ancestor (Monoid). After thinking a bit I'm also a bit perplexed about renaming builder to connect, and in general about the name of the method connect(). You know the meaning of connected in graph theory, while with our method we could actually create a graph which is not connected (e.g. one with no edges at all). agreed! So I suggest to look for a less ambiguous alternative: populate (this gets my vote)? declare? construct? assemble? +1 to populate (and related class renaming?) cool. Class name = GraphPopulator? Though it sounds sooo bad to my ears... Maybe a mother tongue can help us with the matter :-) Ciao, Claudio thanks a lot for your feedbacks and enjoy vacations! -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 http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudiosquarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
[net] parser for MRT (routing information export) file format
Hi [net]ers, subject says it all: do you know if there is any open-source Java implementation of a parser for MRT file format [1] -- more specifically BGP data files (updates and table dumps)? There are implementations in other languages [2][3], but after googling a bit I could not find anything relevant in Java. Second question: if the answer to the above is no, do you think it would make sense to implement it somewhere in Commons? Would [net] be the best place for it? TIA, Claudio [1] http://tools.ietf.org/html/draft-ietf-grow-mrt-17 [2] https://bitbucket.org/ripencc/bgpdump/wiki/Home [3] http://jon.oberheide.org/pybgpdump/ -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] reintegrating branch in trunk
Hi Simone, While rearranging stuff to prepare the merge, I noticed that the NamedExportSelector disappeared in favor of specifying the graph name inside the usingXXXFormat() method. I honestly think that in that way it lost part of the expressiveness - even if it is less verbose. I am in favor of having it reintegrated before merging back, with his pros and cons - WDYT? so if I get it right, now we have: export( actual ).usingDotNotation( my graph ) .withVertexLabels( new VertexLabelMapper() ) .withEdgeWeights( new EdgeWeightMapper() ) .withEdgeLabels( new EdgeLabelMapper() ) .to( System.out ); which becomes something like: export( actual ).usingDotNotation().withName( my graph ) .withVertexLabels( new VertexLabelMapper() ) .withEdgeWeights( new EdgeWeightMapper() ) .withEdgeLabels( new EdgeLabelMapper() ) .to( System.out ); and in both cases the name is not required. If the above is correct I am quite neutral about the matter... how do you call it, a +0? :) PS. spoiler: I am thinking about importers now -- it is not trivial to get them right with this new model implementation. I'll start a discussion about that when we are done with the merge! Ciao, Claudio best and TIA, -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Fri, Mar 23, 2012 at 4:16 PM, Simone Tripodi simonetrip...@apache.org wrote: Yup I am aware that they are not completed, anyway I would like to encourage their development on /trunk because: * new algorithms can be implemented using new APIs (and I have an idea about a new one) * code is still in sandbox, no risk to break anything So I'll merge last Thomas' commit in trunk, then merging back to /trunk. All the best, -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Fri, Mar 23, 2012 at 3:28 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi, we could merge the branch and open some issues on Jira to track the exporter problems, so people can contribute to fix them. +1. Note that the exporters are not complete yet, and there are still interesting architectural decisions left unanswered. Let's go for it! Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.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 -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
[graph] graph importers
Hi all, the implementation of importers for [graph] requires a bit of attention, in particular with the new model where * there are no explicit markers for Vertex and Edge, * all properties of Vertices and Edges are now specified with generic Mappers. Writing and extending exporters is fine: we first specify the graph, then its properties one after the other in a fluent chain. The exporter simply forgets about the types of Vertex/Edge and serializes the whole input. Importing back a graph from an input source, however, is not as simple because: * standard file formats give us no indication about Vertex/Edge types; * serialized graphs come with a number of properties, some of which we know and sometimes need for graph processing (e.g. labels and weights), while some others are not (yet?) recognized in the code; * the return type of any importer should account for both the graph itself and all the properties. As a first step, these are my suggestions for the design: * we need at least default, empty implementations for Vertex and Edge; together with that, we could do some black magic to allow the user to specify what types should be used to map imported Vertices/Edges to actual classes. * we need a structure to host both the imported graph and properties. And it should be easy for the user to query such a structure for specific graph properties, i.e. we need to isolate properties that we recognize and use in our algorithms (e.g. weights). Other properties could be either ignored or imported with a reference to their name in the input format. One way could be to explicitly ask the user to list all the properties that he expects from the input graph, raising exceptions if they are not found. Something like: * importGraph().asGraphML( graph1.gml ).withEdgeWeights().withVertexLabels(); // only two properties loaded and explicitly identified * importGraph().asGraphML( graph2.gml ).withAllProperties(); // all properties are loaded, none is explicitly recognized ...wow that was long. What do you [graph]ers think? :) Ciao, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph] graph importers
Hi, On 25/03/2012 17:33, Simone Tripodi wrote: Hi Claud.io I honestly felt I little lost - code would speak better than thousands of words, what about branching once again and make a concrete proposal? ;) Sure I'll open a branch for that. But first I would like to validate my thoughts (at least partially), that is why I'm writing poems for now :) An example: I'm very far from understanding how to exactly model the return type for importers. It should give access to both the graph and its properties, with particular emphasis on the ones that are relevant in [graph] like edge weights, vertex labels, etc. Any take on that? Cheers, Claudio Looking forward to read about it! -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sun, Mar 25, 2012 at 3:20 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi all, the implementation of importers for [graph] requires a bit of attention, in particular with the new model where * there are no explicit markers for Vertex and Edge, * all properties of Vertices and Edges are now specified with generic Mappers. Writing and extending exporters is fine: we first specify the graph, then its properties one after the other in a fluent chain. The exporter simply forgets about the types of Vertex/Edge and serializes the whole input. Importing back a graph from an input source, however, is not as simple because: * standard file formats give us no indication about Vertex/Edge types; * serialized graphs come with a number of properties, some of which we know and sometimes need for graph processing (e.g. labels and weights), while some others are not (yet?) recognized in the code; * the return type of any importer should account for both the graph itself and all the properties. As a first step, these are my suggestions for the design: * we need at least default, empty implementations for Vertex and Edge; together with that, we could do some black magic to allow the user to specify what types should be used to map imported Vertices/Edges to actual classes. * we need a structure to host both the imported graph and properties. And it should be easy for the user to query such a structure for specific graph properties, i.e. we need to isolate properties that we recognize and use in our algorithms (e.g. weights). Other properties could be either ignored or imported with a reference to their name in the input format. One way could be to explicitly ask the user to list all the properties that he expects from the input graph, raising exceptions if they are not found. Something like: * importGraph().asGraphML( graph1.gml ).withEdgeWeights().withVertexLabels(); // only two properties loaded and explicitly identified * importGraph().asGraphML( graph2.gml ).withAllProperties(); // all properties are loaded, none is explicitly recognized ...wow that was long. What do you [graph]ers think? :) Ciao, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.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 -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] possible room for improvement for Visit handler APIs
Hi Simone, On 25/03/2012 22:46, Simone Tripodi wrote: Hi Graphers, I was trying to code the ELO algorithm using a BSF algo and got in trouble with the boolean return value of the visit handler methods - I think that we could improve it a little, adopting a similar approach of the AsyncHttpClient's AsyncHandler[1]: *maybe* having those methods that return a kind of STATE[2] enumeration would make APIs a little more intuitive. WDYT? if I get it right you are saying that two values (true/false) are too limiting for some of the current methods. Do you have a specific example, to get a clearer idea of the improvement? Thanks, Claudio TIA, -Simo [1] http://sonatype.github.com/async-http-client/request.html [2] http://sonatype.github.com/async-http-client/apidocs/reference/com/ning/http/client/AsyncHandler.STATE.html 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 http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] possible room for improvement for Visit handler APIs
Hi, My proposal is switching to a more expressive values, kind of VisitState.(ABORT|CONTINUE) enumeration that is free of any misunderstanding. Thoughts? ok so something like: * if ( handler.finishEdge( prevHead, e, v ).equals( VisitState.ABORT ) ) .. Looks good to me, +1 :) Ciao, Claudio best and thanks, -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 http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] possible room for improvement for Visit handler APIs
Hi, On 25/03/2012 23:27, Simone Tripodi wrote: just had an idea of a possible new state: SKIP,that would mean skipping the children/subtrees... thoughts? :P +1. Of course we still need to document the whole thing in the javadoc (as we did already with boolean values), but the readability of the code is a clear advantage. Thanks, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] possible room for improvement for Visit handler APIs
Hi, On 25/03/2012 23:45, Simone Tripodi wrote: just filled SANDBOX-416 and committed the org.apache.commons.graph.visit.VisitState enum, now I am too sleepy to continue - feel free to finalize it if you want/can/have spare time/... I did that, see the comment on SANDBOX-416 :) Ciao, Claudio all the best and thanks for discussing, -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sun, Mar 25, 2012 at 11:36 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi, On 25/03/2012 23:27, Simone Tripodi wrote: just had an idea of a possible new state: SKIP,that would mean skipping the children/subtrees... thoughts? :P +1. Of course we still need to document the whole thing in the javadoc (as we did already with boolean values), but the readability of the code is a clear advantage. Thanks, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.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 -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph][discuss] reintegrating branch in trunk
Hi, we could merge the branch and open some issues on Jira to track the exporter problems, so people can contribute to fix them. +1. Note that the exporters are not complete yet, and there are still interesting architectural decisions left unanswered. Let's go for it! Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: svn commit: r1302930 - in /commons/sandbox/graph/branches/exporters-with-mappers/src/main/java/org/apache/commons/graph/export: AbstractExporter.java DotExporter.java GraphMLExporter.java
Hi, yes I think that having the common denominator would help on avoiding to repeat ourselves in various implementations. Methods in the AbstractExporter could be even final, no needs to provide same implementation in the different exporters. the thing is: even if (for example) edge weights are supported in ALL the file formats of the world (which is quite plausible), the actual attribute will likely be called in different ways for each format: weight, w, value or whatever. So even a unified implementation in AbstractExporter should still rely on concrete implementations to discover the name of the attribute (see e.g. the static fields DotExporter.WEIGHT and DotExporter.LABEL). But it's still fine for me to keep at least the abstract common denominator. Another issue I'm facing: some of the output formats depend on the actual type of the printed value. For example in the DOT format, Strings (especially those with whitespaces) should be double-quoted while numbers (doubles) should not, e.g.: * 192 [label=hello world weight=3.4] So we should also seek a unified way to keep track of attribute types when serializing them, so that each exporter can choose the appropriate output format for each of them. I saw the enlistVerticesProperty/enlistEdgesProperty methods in the code, are they supposed to help on this matter? Ciao, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: svn commit: r1302930 - in /commons/sandbox/graph/branches/exporters-with-mappers/src/main/java/org/apache/commons/graph/export: AbstractExporter.java DotExporter.java GraphMLExporter.java
Hi Simone, On 20/03/2012 17:35, Simone Tripodi wrote: OH :( I liked the fact that commons properties were defined just once in the Abstract impl :( I did it after realizing that the DOT language does not support weights on vertices. Of course I could have kept the others (withEdgeWeights, withVertexLabels, etc), but we could face the same problem if later we introduce a new format that does not support e.g. labels... WDIT? do you want me to reintegrate the common denominator for now? Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://twitter.com/hyperboreans http://claudio.squarcella.com/ - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [graph] Why the Vertex and Edge interfaces?
Hi, On 03/03/2012 02:21, Simone Tripodi wrote: first of all: yes, I will play with this stuff as soon as I find the time :) this is scaring... go Orb.io, go! :) constant), but still there is one more step of indirection. So we would need to test and compare performances, hopefully with acceptable results. sounds it would be better if you implement that stuff in a branch to keep both implementations, IMHO sure :) * with the current approach: one interface for edge-weighted graphs (EdgeWeightedGraph, renaming the current WeightedGraph?), one for vertex-weighted graphs (VertexWeightedGraph) and maybe even one for weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -- not to talk about their counterparts with labels, etc; * with the proposed approach: a Graph would implement HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also HasLabelsOnEdges if needed. do you remember that we reintroduced the WeightedGraph just for the type inference issue on fluent APIs in Eclipse, do you? ;) It would have been worked otherwise as well dropping the WeightedGraph and expressing types only on Vertex/Edges that is right. On the other hand with HasWeightedEdges we could drop WeightedEdge and so on: one interface in, one out. Or we could even save both approaches as alternative implementations. That is: * a set of interfaces: e.g. HasWeightedEdges#getWeight(edge), HasWeightedVertices#getWeight(vertex), etc. * #1 implementation with external properties: the graph keeps the mapping between edge/vertex and weight, so that any type can be used for edges/vertices * #2 classical implementation: we keep markers like WeightedEdge and WeightedVertex but only the graph knows about them. algorithms keep asking the graph for weights of edges/vertices, and the graph in turn asks the edge/vertex itself (passed as parameter). WDYT? I know that this kind of mismatch is not your favourite ;) but would you really call Operations something which is just an Addition -- or viceversa DoubleWeightAddition something that might later be expanded with other operations? I am confused now: this is what you did in the concrete implementation! no, trying to be clearer: you propose to rename Monoid into WeightOperation, which is like renaming Addition into Operation. Or alternatively to call the current *WeightBaseOperations something like *WeightMonoid. In both cases I disagree because I would prefer to keep a clear distinction between single well-defined properties/operations (like Addition or Comparator) and the comprehensive implementation (e.g. DoubleWeightBaseOperations) that implements all the operations it can implement with Doubles. Hoping we'll converge somewhere, maybe asymptotically ;) Claudio time to sleep, cannot reply anymore, read tomorrow -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sat, Mar 3, 2012 at 1:37 AM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi, what if that mapping function becomes a responsibility of WeightedGraph itself? And more generally, what if any property of vertices and/or edges is moved to the containing graph? that would imply that Graph implementations have to implement vertices and/or edges metadata indexing, that would be anyway less performant than accessing directly on metadata contained in current node/arc - just count the number of time you should have to touch the adapted data structures, of course will be at least one more than the actual. that is absolutely right. Not asymptotically if the implementation is good (hashmaps are already good enough with their read time which is basically constant), but still there is one more step of indirection. So we would need to test and compare performances, hopefully with acceptable results. We could externalize all different graph properties to appropriate interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each algorithm specifies the needed input graph including the subset of interfaces it needs to implement. We do something like that with weight operations already. I am worried that with that approach the number of interfaces would proliferate like pollen during Spring, users - and devs - would get easily lost but that would happen anyway as soon as we implement an algorithm with weights on vertices, right? Here are the options I see: * with the current approach: one interface for edge-weighted graphs (EdgeWeightedGraph, renaming the current WeightedGraph?), one for vertex-weighted graphs (VertexWeightedGraph) and maybe even one for weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -- not to talk about their counterparts with labels, etc; * with the proposed approach: a Graph would implement HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also HasLabelsOnEdges if needed
Re: [graph] Why the Vertex and Edge interfaces?
Hi,
Apologize but I still don't understand what the benefit is on storing
nodes/arcs data in the Graph data structure
back to James' first email: any type could be immediately used as
edge/vertex without wrappers, while specific data related to the domain
of graphs (weights, labels) would be handled separately. I actually
think this is useful: back to my days of DIY Java graphs I implemented
something similar to what we have now, just to think every time: why
should I wrap my objects with these markers? I already know my Router is
a Vertex in the graph...
- sounds to me like a
CollectionInteger where, to know the int value of its elements, have
to query the data structure, i.e.
CollectionInteger integerCollection = ...;
for ( Integer ptr : integerCollection )
{
int value = integerCollection.getInt( ptr );
}
It is weird to me even reading it.
When I started modeling Graph, I had collections in mind - above all
to simplify its adoption - I would be more than pleased to drop
Weighted* version of graphs and come back to the previous situation,
but with the annoying type inference issue fixed.
Here's the way I see it. A GraphV,E implementing HasWeightedEdges
would have something like this inside:
MapE, W edgeWeights = new HashMapE, W();
[... populate map, other methods, etc ...]
// implementing HasWeightedEdges#getEdgeWeight
public W getEdgeWeight(E edge)
{
[... check null etc...]
return edgeWeights.get(edge);
}
no, trying to be clearer: you propose to rename Monoid into WeightOperation,
which is like renaming Addition into Operation. Or alternatively to call the
current *WeightBaseOperations something like *WeightMonoid. In both cases I
disagree because I would prefer to keep a clear distinction between single
well-defined properties/operations (like Addition or Comparator) and the
comprehensive implementation (e.g. DoubleWeightBaseOperations) that
implements all the operations it can implement with Doubles.
OK, concept is clear, I still don't agree on the nomenclature, anyway.
Actually *WeightBaseOperations describe
*WeightAdditionalOrderedMonoid, so *BaseOperations doesn't sound self
explaining.
then let's find a better name, but why *OrderedMonoid? Assume we replace
the whole set of current interfaces (see my comment to the next
paragraph below) with just Addition and Comparable (the latter already
exists of course). There is no need to create another interface to merge
the two (ComparableAddition? OrderedAddition?). Then we have:
public class DoubleWeightOperations
implements Addition, Comparator
{
[...]
}
I would not rename the class to DoubleWeightAddition or even
DoubleWeightComparableAddition. What if later we need to e.g. add a
function that normalizes weights by some factor, or returns the
reciprocal of a weight, etc? With the above code it would suffice to add
new interfaces:
public class DoubleWeightOperations
implements Addition, Comparator, Normalization, Reciprocal
{
[...]
}
Moreover, The Zero interface is the *additional* monoid identity
element, if someone has to implement the Multiplication Monoid I
wouldn't expect he implements the One interface wich declares O one()
method.
This is why IMHO in the current algebra model, Zero has to be dropped
and has to be modified in:
That is fine for me. I simply followed pure theory while implementing
that and used all possible granularity. Now looking at our
implementations I think it is save enough to even merge Zero, Semigroup
and Monoid (so that's one step further than your example below) and call
the result Addition so that its role is clear to everybody. Does that
sound good? :)
Claudio
/**
* semigroup is an algebraic structure consisting of a set together
with an associative binary operation.
*/
interface SemigroupE
{
E append( E s1, E s2 );
}
/**
* A {@link Monoid} is a {@link Semigroup} with an identity value.
*/
public interface MonoidE
extends SemigroupM
{
E identity();
E inverse( E element );
}
that would continue working for every Monoid specialization. Or not? thoughts?
Thanks and best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sat, Mar 3, 2012 at 1:43 PM, Claudio Squarcella
squar...@dia.uniroma3.it wrote:
Hi,
On 03/03/2012 02:21, Simone Tripodi wrote:
first of all: yes, I will play with this stuff as soon as I find the time
:)
this is scaring... go Orb.io, go! :)
constant), but still there is one more step of indirection. So we would
need
to test and compare performances, hopefully with acceptable results.
sounds it would be better if you implement that stuff in a branch to
keep both implementations, IMHO
sure :)
* with the current approach: one interface for edge-weighted graphs
(EdgeWeightedGraph, renaming the current WeightedGraph?), one for
vertex-weighted graphs (VertexWeightedGraph
Re: [graph] Why the Vertex and Edge interfaces?
Hi Simone, answering briefly below: Vertex is something we can safety drop because we know its nature at priori, markers are unnecessary.This is fine. +1. what is the sense, at that point, on keeping the Edge?!! It would be more than enough to know which is the Head and which is the Tail in the Edge to get the W! good observation. My 2 cents: it might still make sense for users to map their existing domain (including edges) to the graph (e.g. Routers to Vertices and Cables to Edges) and get it back as soon as they are done with graph operations (e.g. once they find the shortest path, they automatically have the sequence of Cables they need). maybe because they implement OrderedMonoid? :) [...] how much would Addition and Multiplication interface differ each other? [...] that would be fine, what is not clear is that Monoids expose the same interface, so *Operations class implementation canot declare same method multiple times answering all the above: that is another reason why I would like our current Monoid to be called Addition (and Addition#sum instead of Monoid#append, etc), so that it is semantically clearer and later we can introduce Multiplication as a completely independent interface. enough talk IMHO, time to code and make concrete proposals Sure! I'll play with weights first, because I already know what I want to do. As for Vertex/Edge markers I still see valuable feedback coming in, so I'll wait a bit. Branching is ok -- especially for the second part which sounds like a real earthquake ;) 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] Why the Vertex and Edge interfaces?
Hi all, Claudio is aware also about algorithms where weights are associated to Vertex - he's preparing his PhD research on graphes - maybe he can show us a more long-vision roadmap and evaluate benefits on simplifying the design. yes there are algorithms with weights on vertices. Of course those with weighted edges (like the ones already implemented) are much more widespread and frequently used, but still we cannot forget about that. Also, although on a secondary level, labels on vertices/edges are kind of important in many situations (including testing, debugging) where I think it is good to keep them distinct from the standard toString method (you might want to represent only a subset of info in the label, etc). Matthew Pocock suggested an alternative approach back in the days of weight abstraction: * the graph itself is extremely simple and naked: no weights/labels on vertices/edges; * all properties are stored in some external structure, which I imagine composed of associative maps (MapEdge, Weight, etc etc). He motivated the idea with a personal use case: often graphs are used and reused with the same structure but different weights (and/or labels, etc). Now if James' question becomes a second use case, maybe it's the right time to exhume that idea ;) 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] Why the Vertex and Edge interfaces?
Hi, The weights can be external, too. It's only a function from edge to weight. Your algorithm can take a function for its weights. The files library does it similar to this. what if that mapping function becomes a responsibility of WeightedGraph itself? And more generally, what if any property of vertices and/or edges is moved to the containing graph? We could externalize all different graph properties to appropriate interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each algorithm specifies the needed input graph including the subset of interfaces it needs to implement. We do something like that with weight operations already. Claudio On Mar 2, 2012 3:08 PM, Ted Dunningted.dunn...@gmail.com wrote: Having weights on vertices is quite common. Consider any probability transition network. The weight on each node is the probability of being in that state and the weights on the edges are conditional probabilties. Page rank is a related example of having weights on nodes. On Fri, Mar 2, 2012 at 12:40 AM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi all, Claudio is aware also about algorithms where weights are associated to Vertex - he's preparing his PhD research on graphes - maybe he can show us a more long-vision roadmap and evaluate benefits on simplifying the design. yes there are algorithms with weights on vertices. Of course those with weighted edges (like the ones already implemented) are much more widespread and frequently used, but still we cannot forget about that. Also, although on a secondary level, labels on vertices/edges are kind of important in many situations (including testing, debugging) where I think it is good to keep them distinct from the standard toString method (you might want to represent only a subset of info in the label, etc). Matthew Pocock suggested an alternative approach back in the days of weight abstraction: * the graph itself is extremely simple and naked: no weights/labels on vertices/edges; * all properties are stored in some external structure, which I imagine composed of associative maps (MapEdge, Weight, etc etc). He motivated the idea with a personal use case: often graphs are used and reused with the same structure but different weights (and/or labels, etc). Now if James' question becomes a second use case, maybe it's the right time to exhume that idea ;) Ciao, Claudio -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~**squarcel http://www.dia.uniroma3.it/~squarcel http://squarcella.com/ --**--**- To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org -- Claudio Squarcella PhD student at Roma Tre University 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] Doubts on DFS algorithm implementation
Hi, Added an extra check to prevent discovering multiple edges that lead to the same (already visited) vertex. cool stuff, thanks for turning human words into computer words :) I spent a couple minutes running the tests on max-flow algos with breakpoints and stuff, and apparently they keep avoiding zero-capacity links during graph visit. Excellent! 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] Doubts on DFS algorithm implementation
Hi, [...] Also, I don't know if we have an abstraction for this, but the order in which you add your connected vertices can be important, too (might want to do a greedy bfs/dfs). +1. So far the algorithm has no control over that, as it simply scans an IteratorV of adjacent vertices. -- 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] Doubts on DFS algorithm implementation
Hello, the method discoveryEdge currently tells whether or not the algorithm should explore a subtree/branch and add related vertices to the stack/queue. So I see no conflict in the implementation. Maybe you are saying that the edge should be explored *right before* the vertex it leads to -- but why? AFAIK a standard graph search is only concerned with *vertices*. In that sense finishEdge becomes useless, as the responsibility for returning prematurely is entirely covered by finishVertex. Am I raving mad? :-) yes you are right, the visit should be only concerned the vertices, but in our implementation we added also the discoveryEdge that in a dfs has invoked like a BFS. This in my opinion can be frustrating for the user because the edge is not visit in depth but in breadth. So IMHO we should visit also the edge in depth, (only in a dfs of course) or remove the invocation of discover/finish edge that can get confused the user. if you want to postpone the edge visit to the right time (i.e. when the corresponding tail vertex is removed from the waiting list) then I guess the waiting list itself should also keep track of the edge and/or the predecessor (vertex). The class PredecessorsList probably does that job fairly well. Rephrasing a bit: we are seeking a unified implementation for both standard graph searches (only concerned with vertices) and more general graph visits (e.g. the one needed for max flow algorithms). So yeah, let's use our brains for something cool :) P.S. I would not remove discoverEdge anyway because, as I said before, it can help pruning the graph and avoiding to explore dead ends (e.g. for max flow, there is no point in traversing edges with no residual flow capacity). 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] Doubts on DFS algorithm implementation
Hi, Simo you are right, the vertices have visited in the right way, but the edge handler has called in the wrong way. IMHO we have to modify the code in order to fire the edge handler in the right way to avoid any error for the user. the method discoveryEdge currently tells whether or not the algorithm should explore a subtree/branch and add related vertices to the stack/queue. So I see no conflict in the implementation. Maybe you are saying that the edge should be explored *right before* the vertex it leads to -- but why? AFAIK a standard graph search is only concerned with *vertices*. In that sense finishEdge becomes useless, as the responsibility for returning prematurely is entirely covered by finishVertex. Am I raving mad? :-) It's a good idea, Now we have implemented two separate methods that visit the graph for dfs and bfs. We should do a little refactoring and implement a unique method that switches between dfs and bfs simply changing the the type of visitedVertex. WDYT? Yes! James' idea sounds good to me. Ciao, Claudio I think visitedVertices should rather be called seenVertices, as it is only needed to avoid adding vertices more than once to the stack/queue. Marco (and all), please see if the implementations look nicer with that change in mind (looks good to me). +1 -- 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
[math] computational geometry = math + graph ?
Hi all, after reading the issue MATH-751[1] about computational geometry algorithms I realized it could make sense to look at what we already did in [graph], especially in terms of data structures. Things like triangulations, Voronoi diagrams, etc. would need graph representations anyway -- IMHO [math]ers should avoid to reinvent the wheel and/or create a different representation for graphs. Of course the downside is that [graph] in currently in Sandbox without a Release. Still, if we agree that it would make sense to link the two, maybe it is worth to wait a bit more for MATH-751 until [graph] is ready (we're working on that!). Looking forward to comments! Claudio [1] https://issues.apache.org/jira/browse/MATH-751 -- 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: svn commit: r1292272 [1/2] - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/flow/ main/java/org/apache/commons/graph/model/ main/java/org/apache/commons/graph/sho
On 22/02/2012 15:08, Simone Tripodi wrote: hi Claudio, it is a good practice putting, in the commit message log, the related issue key, if any. I suppose this commit is related to [SANDBOX-395]. oops... newbie spotted! :) I changed that with svn propset, thanks for pointing it out. 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] renaming weight operations
Hi Simone and all, On 19/02/2012 22:12, Simone Tripodi wrote: Hi (and sorry for the late) I personally don't see the reason to be open to *Operations until *Monoid (actually, wrongly, *Weight) until there is the real need of. Anyway, please share a patch in the issue you filled - code talks much better, I could finally see what I am currently missing ;) I uploaded a patch on JIRA[1] as requested. I hope that helps convincing you ;) Ciao, Claudio [1] https://issues.apache.org/jira/browse/SANDBOX-395?focusedCommentId=13212017page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13212017 looking forward to it! -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sun, Feb 19, 2012 at 5:05 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hi, * Doubles can also be multiplied, but so far we did not need to include that in our stack of operations and properties. If we ever need to do so, it will be enough to create another interface extending OrderedMonoid and change the implemented interface in DoubleWeightOperations. isn't it a different monoid? I mean, multiplier operator, the 1 identifier and real numbers are a monoid, or my math became terribly bad? :P you're right! Your math is cool don't worry :) But see, maybe we could let it implement both an addiction monoid and a multiplication monoid. We could even create Addition (and later maybe Multiplication?) as interface extending Monoid, so that we also solve the other aspect pointed out by Axel days ago: the Monoid would offer a generic applyOperation, while Addition would wrap it as sum (and Multiplication as multiply). Cool? * Also, there might be properties and/or operations that are unrelated to each other, hence DoubleWeightOperations might implement more than one interface in the future. that sounds good, anyway before to apply any potential improvement because users may need of XXX I'd want to make sure that custom behaviors can be applied to our APIs just estending existing component, rather than blindly provide potential features we don't need. I mean... if we do have the real need of having more operations than the OrderedMonoid already provides, so go for it; otherwise, users shall be able to define their on *Operator by extending ours and implementing their custom interface. then we could use the pattern *WeightBaseOperations (e.g. DoubleWeightBaseOperations): so that we developers are free to extend it with more properties over time, as well as the users in their implementations -- and the name is IMHO self-explanatory and unambiguous. In other words: Doubles (as well as the other types) are not *only* monoids. So I feel we would be much more blind sticking to the term monoid in the implementation: we need more flexibility, and I hope the above *WeightBaseOperations sound good as a candidate. Thank you for the discussion, waiting for further input! Claudio I would be to support the minimum extensible set of features rather than supporting all the potential cases, unless we really have the practical need of them to implement new algos. Thoughts? -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sun, Feb 19, 2012 at 2:59 PM, Claudio Squarcella squar...@dia.uniroma3.itwrote: Hello Simone, It would be much more naturally to my hears hearing it as BigDecimalOrderedMonoid, doesn't it? you have a valid point. However my intention is to decouple implementations from underlying interfaces, because they might evolve and grow over time. Let me give you two examples: * Doubles can also be multiplied, but so far we did not need to include that in our stack of operations and properties. If we ever need to do so, it will be enough to create another interface extending OrderedMonoid and change the implemented interface in DoubleWeightOperations. * Also, there might be properties and/or operations that are unrelated to each other, hence DoubleWeightOperations might implement more than one interface in the future. How does that sound? 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 -- Claudio Squarcella PhD student at Roma Tre University http://www.dia.uniroma3.it/~squarcel http://squarcella.com/ - To unsubscribe, e-mail
[graph] renaming weight operations
Hi all, following previous discussion on ML I opened a JIRA issue to rename classes/variables related to operations on weights: https://issues.apache.org/jira/browse/SANDBOX-395 I will soon work on it. If there is any last minute suggestion I will be happy to hear that. Ciao, -- 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] renaming weight operations
Hello Simone, It would be much more naturally to my hears hearing it as BigDecimalOrderedMonoid, doesn't it? you have a valid point. However my intention is to decouple implementations from underlying interfaces, because they might evolve and grow over time. Let me give you two examples: * Doubles can also be multiplied, but so far we did not need to include that in our stack of operations and properties. If we ever need to do so, it will be enough to create another interface extending OrderedMonoid and change the implemented interface in DoubleWeightOperations. * Also, there might be properties and/or operations that are unrelated to each other, hence DoubleWeightOperations might implement more than one interface in the future. How does that sound? 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] renaming weight operations
Hi, * Doubles can also be multiplied, but so far we did not need to include that in our stack of operations and properties. If we ever need to do so, it will be enough to create another interface extending OrderedMonoid and change the implemented interface in DoubleWeightOperations. isn't it a different monoid? I mean, multiplier operator, the 1 identifier and real numbers are a monoid, or my math became terribly bad? :P you're right! Your math is cool don't worry :) But see, maybe we could let it implement both an addiction monoid and a multiplication monoid. We could even create Addition (and later maybe Multiplication?) as interface extending Monoid, so that we also solve the other aspect pointed out by Axel days ago: the Monoid would offer a generic applyOperation, while Addition would wrap it as sum (and Multiplication as multiply). Cool? * Also, there might be properties and/or operations that are unrelated to each other, hence DoubleWeightOperations might implement more than one interface in the future. that sounds good, anyway before to apply any potential improvement because users may need of XXX I'd want to make sure that custom behaviors can be applied to our APIs just estending existing component, rather than blindly provide potential features we don't need. I mean... if we do have the real need of having more operations than the OrderedMonoid already provides, so go for it; otherwise, users shall be able to define their on *Operator by extending ours and implementing their custom interface. then we could use the pattern *WeightBaseOperations (e.g. DoubleWeightBaseOperations): so that we developers are free to extend it with more properties over time, as well as the users in their implementations -- and the name is IMHO self-explanatory and unambiguous. In other words: Doubles (as well as the other types) are not *only* monoids. So I feel we would be much more blind sticking to the term monoid in the implementation: we need more flexibility, and I hope the above *WeightBaseOperations sound good as a candidate. Thank you for the discussion, waiting for further input! Claudio I would be to support the minimum extensible set of features rather than supporting all the potential cases, unless we really have the practical need of them to implement new algos. Thoughts? -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sun, Feb 19, 2012 at 2:59 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: Hello Simone, It would be much more naturally to my hears hearing it as BigDecimalOrderedMonoid, doesn't it? you have a valid point. However my intention is to decouple implementations from underlying interfaces, because they might evolve and grow over time. Let me give you two examples: * Doubles can also be multiplied, but so far we did not need to include that in our stack of operations and properties. If we ever need to do so, it will be enough to create another interface extending OrderedMonoid and change the implemented interface in DoubleWeightOperations. * Also, there might be properties and/or operations that are unrelated to each other, hence DoubleWeightOperations might implement more than one interface in the future. How does that sound? 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 -- 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)
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)
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, * 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)
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)
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] BST?
Hello, On 01/02/2012 17:39, Simone Tripodi wrote: Hi Gary!!! :) I don't see any issue on adding the BST algorithms you need in [graph], even if you have to reuse the minimum amount of codebase, packages don't usually interact each other very much, unless some DFS/BFS or shortest path is needed in other algo. I have the plan of adding KDTree searches as well. My personal vision of [graph] is realizing a graph-pedia of graph-related algorithms implementation, so every addition is more than welcome!!! I completely agree with Simone. I see [graph] as the right place not only for well-known algorithms but also for state-of-the-art results, where graphs are either support structures for computation or actual main data structures fitting the user domain. I would be thrilled to see more and more of these expansions in the future: e.g. the huge field of algorithms that rely on preprocessed or partially known graphs (see shortest paths for road networks co). Looking forward, -- 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] BST?
I completely agree with Simone. I see [graph] as the right place not only for well-known algorithms but also for state-of-the-art results, where graphs are either support structures for computation or actual main data structures fitting the user domain. P.S.: with this I am not saying that BSTs are state-of-the-art, they are way older than me! ;) -- 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] Graph connectivity algo
Hello, On 27/01/2012 12:35, Marco Speranza wrote: Hi all, I'm trying to implement the Boruvka's algorithm and I need to know is a grah is connected or not. So I'd like to propose a simple algorithm to do that. A simple way to implement that is run a depth-first or breadth-first search starting from an arbitrary vertex. If the number of the vertices touched are the same of the origina graph, the graph is connected. cool, go for it :-) Moreover the algorithm could count the number of che connected componet ( http://en.wikipedia.org/wiki/Connected_component_(graph_theory). well you get that number if you actually map each vertex to a connected component, which means you could need to run the search algorithm more than once. As a unified solution maybe we could go for an algorithm that returns the connected components as a collection of graphs, and then in your case you just check that there is only one connected component. Ciao Claudio what do you think about that? Ciao -- Marco Speranzamarco.speranz...@gmail.com Flick photostream: http://www.flickr.com/photos/marcosperanza79/ Google Code: http://code.google.com/u/marco.speranza79/ -- 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] Graph connectivity algo
On 27/01/2012 12:47, Claudio Squarcella wrote: Hello, On 27/01/2012 12:35, Marco Speranza wrote: Hi all, I'm trying to implement the Boruvka's algorithm and I need to know is a grah is connected or not. So I'd like to propose a simple algorithm to do that. A simple way to implement that is run a depth-first or breadth-first search starting from an arbitrary vertex. If the number of the vertices touched are the same of the origina graph, the graph is connected. cool, go for it :-) Moreover the algorithm could count the number of che connected componet ( http://en.wikipedia.org/wiki/Connected_component_(graph_theory). well you get that number if you actually map each vertex to a connected component, which means you could need to run the search algorithm more than once. As a unified solution maybe we could go for an algorithm that returns the connected components as a collection of graphs, and then in your case you just check that there is only one connected component. ...and of course also the simplified version give me the connected component containing the input vertex, which suits your case better and does not waste resources. Claudio Ciao Claudio what do you think about that? Ciao -- Marco Speranzamarco.speranz...@gmail.com Flick photostream: http://www.flickr.com/photos/marcosperanza79/ Google Code: http://code.google.com/u/marco.speranza79/ -- 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
[SANDBOX][GRAPH] Eclipse vs. latest version
Hi all, I am experiencing a rather annoying issue with the latest version of commons-graph on Eclipse. Compiling with javac (maven, command line) it works fine, but the editor still complains: e.g. line 72 of the new FordFulkersonTestCase[1] gives a list of errors[2]. Now, I know from googling that Eclipse is not new to strange behavior, but I wanted to know if anyone on the ML has a nice answer, solution or workaround (other than standard answers like use another IDE), or at least experiences the same issue with the code. Thank you, Claudio --- [1] https://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?revision=1235827view=markup [2] Multiple markers at this line - Bound mismatch: The generic method applyingFordFulkerson(OM) of type MaxFlowAlgorithmSelectorV,W,WE,G is not applicable for the arguments (IntegerWeight). The inferred type IntegerWeight is not a valid substitute for the bounded parameter OM extends OrderedMonoidObject - Type mismatch: cannot convert from Object to Integer - Bound mismatch: The generic method findMaxFlow(G) of type CommonsGraphV,E,G is not applicable for the arguments (DirectedMutableWeightedGraphBaseLabeledVertex,BaseLabeledWeightedEdgeInteger,Integer). The inferred type BaseLabeledWeightedEdgeInteger is not a valid substitute for the bounded parameter WE extends WeightedEdgeW -- 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: [SANDBOX][GRAPH] Eclipse vs. latest version
P.S. for completeness: Eclipse version: Indigo Service Release 1 Build id: 20110916-0149 OS: Mac OS X Lion Cheers, Claudio On 26/01/2012 15:30, Claudio Squarcella wrote: Hi all, I am experiencing a rather annoying issue with the latest version of commons-graph on Eclipse. Compiling with javac (maven, command line) it works fine, but the editor still complains: e.g. line 72 of the new FordFulkersonTestCase[1] gives a list of errors[2]. Now, I know from googling that Eclipse is not new to strange behavior, but I wanted to know if anyone on the ML has a nice answer, solution or workaround (other than standard answers like use another IDE), or at least experiences the same issue with the code. Thank you, Claudio --- [1] https://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?revision=1235827view=markup [2] Multiple markers at this line - Bound mismatch: The generic method applyingFordFulkerson(OM) of type MaxFlowAlgorithmSelectorV,W,WE,G is not applicable for the arguments (IntegerWeight). The inferred type IntegerWeight is not a valid substitute for the bounded parameter OM extends OrderedMonoidObject - Type mismatch: cannot convert from Object to Integer - Bound mismatch: The generic method findMaxFlow(G) of type CommonsGraphV,E,G is not applicable for the arguments (DirectedMutableWeightedGraphBaseLabeledVertex,BaseLabeledWeightedEdgeInteger,Integer). The inferred type BaseLabeledWeightedEdgeInteger is not a valid substitute for the bounded parameter WE extends WeightedEdgeW -- 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: [SANDBOX][GRAPH] Eclipse vs. latest version
/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Thu, Jan 26, 2012 at 3:33 PM, Claudio Squarcella squar...@dia.uniroma3.it wrote: P.S. for completeness: Eclipse version: Indigo Service Release 1 Build id: 20110916-0149 OS: Mac OS X Lion Cheers, Claudio On 26/01/2012 15:30, Claudio Squarcella wrote: Hi all, I am experiencing a rather annoying issue with the latest version of commons-graph on Eclipse. Compiling with javac (maven, command line) it works fine, but the editor still complains: e.g. line 72 of the new FordFulkersonTestCase[1] gives a list of errors[2]. Now, I know from googling that Eclipse is not new to strange behavior, but I wanted to know if anyone on the ML has a nice answer, solution or workaround (other than standard answers like use another IDE), or at least experiences the same issue with the code. Thank you, Claudio --- [1] https://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?revision=1235827view=markup [2] Multiple markers at this line - Bound mismatch: The generic method applyingFordFulkerson(OM) of type MaxFlowAlgorithmSelectorV,W,WE,G is not applicable for the arguments (IntegerWeight). The inferred type IntegerWeight is not a valid substitute for the bounded parameterOM extends OrderedMonoidObject - Type mismatch: cannot convert from Object to Integer - Bound mismatch: The generic method findMaxFlow(G) of type CommonsGraphV,E,G is not applicable for the arguments (DirectedMutableWeightedGraphBaseLabeledVertex,BaseLabeledWeightedEdgeInteger,Integer). The inferred type BaseLabeledWeightedEdgeInteger is not a valid substitute for the bounded parameterWE extends WeightedEdgeW -- 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 - 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 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,
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)
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)
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)
, 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: 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-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,
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)
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
[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] Weighted as an interface
Hi,
Moreover, I start having the feeling the {{WeightedGraph}} is a
useless interface: it is enough marking the vertices/edges as weighted
depending on the problem... or not? At the end of the day,
{{WeightedGraph}} does nothing than having the the edges marked as
weighted, so Dijkstra signature changed as:
V extends Vertex, WE extends WeightedEdge, G extends DirectedGraphV,
WEWeightedPathV, WEfindShortestPath( G graph, V source, V
target )
still define well the input type, a graph wich relations are directed
edges and edges are weighted... WDYT?
I agree, as long as there are no specific features of the graph that are
independent on its vertices and edges.
quoting myself here: actually I think {{WeightedGraph}} should *not* go
away if it makes sense to add methods to it later (e.g. to get the total
weight). But changing the signature of the methods is still a valid
idea, as it allows for a more fine-grained expressiveness on the input.
Right?
Claudio
Another advantage: I won't bother
later to add more speficic interfaces like {{EdgeWeightedGraph}} or
{{VertexWeightedGraph}} ;-)
+1, please include that in a separate issue!
All the best, have a nice day!
Simo
Ciao,
Claudio
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] Weighted as an interface
Hi,
thanks to both for your words! Please find comments below.
On 05/12/2011 10:01, Simone Tripodi wrote:
Hi Claudio,
what a pleasant surprise! :) I was hoping commons-graph would have
caught the interest of researchers on that field, I'm really happy you
would like to contribute!
I agree with your observations, please fill new issues on JIRA[1] and
feel free to provide patches, I'll process them ASAP :)
Alright, I'll find time later this week.
As for my suggestion on types, should I go for {{WeightedN extends
Number}}?
Note that I am also concerned about domain-specific requirements (e.g.
all weights must be positive) that I would like to see implemented as
statically as possible in the code. {{Number}} should give us quite
enough freedom in that direction (e.g. one could later extend it with
something like {{PositiveInteger}}).
A more platonic alternative would be to have an abstract type of weight
which 1. is comparable and 2. can be aggregated in some way (e.g. the
weight of a path is the sum of weights of its edges). But I am probably
going too far...
Moreover, I start having the feeling the {{WeightedGraph}} is a
useless interface: it is enough marking the vertices/edges as weighted
depending on the problem... or not? At the end of the day,
{{WeightedGraph}} does nothing than having the the edges marked as
weighted, so Dijkstra signature changed as:
V extends Vertex, WE extends WeightedEdge, G extends DirectedGraphV,
WE WeightedPathV, WE findShortestPath( G graph, V source, V
target )
still define well the input type, a graph wich relations are directed
edges and edges are weighted... WDYT?
I agree, as long as there are no specific features of the graph that are
independent on its vertices and edges. Another advantage: I won't bother
later to add more speficic interfaces like {{EdgeWeightedGraph}} or
{{VertexWeightedGraph}} ;-)
Ciao,
Claudio
Looking forward for your contributions, can't wait for them! :)
Simo
[1] https://issues.apache.org/jira/browse/SANDBOX
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Mon, Dec 5, 2011 at 2:00 AM, James Carmanja...@carmanconsulting.com wrote:
Welcome! Contributions (and the contributor) are always welcome. In my
past life, I did quite a bit of graph programming to solve business
problems. We used yfiles, though. I hope to get around to playing with
[graph] someday too. Please do submit a patch!
On Dec 4, 2011 6:43 PM, Claudio Squarcellasquar...@dia.uniroma3.it
wrote:
Hello,
I have been reading the source in the past days and I found that the
concept of weight (e.g. weighted edge, graph, etc) could benefit from a
bit of abstraction.
The basic idea would be to have an interface called Weighted with an
obvious method getWeight(). Changes in the code would easily derive from
that. As a side effect it would be easy to implement new stuff like
weighted vertices: not as glorious as weighted edges, but still needed in
some problems (e.g. all-pairs bottleneck paths) and therefore desirable for
a general purpose graph API.
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 :-)
If my thoughts meet some interest I will work on a patch.
Ciao,
Claudio
P.S.
I am a first-timer here, so what follows is a short introduction.
I am doing a PhD in Graph Drawing and Information Visualization. I always
looked for a standard, unified way to represent and handle graphs when
developing prototypes. So my interest in this project is quite natural, and
I am willing to help and see it become a robust project.
--
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-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
[Graph] Weighted as an interface
Hello, I have been reading the source in the past days and I found that the concept of weight (e.g. weighted edge, graph, etc) could benefit from a bit of abstraction. The basic idea would be to have an interface called Weighted with an obvious method getWeight(). Changes in the code would easily derive from that. As a side effect it would be easy to implement new stuff like weighted vertices: not as glorious as weighted edges, but still needed in some problems (e.g. all-pairs bottleneck paths) and therefore desirable for a general purpose graph API. 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 :-) If my thoughts meet some interest I will work on a patch. Ciao, Claudio P.S. I am a first-timer here, so what follows is a short introduction. I am doing a PhD in Graph Drawing and Information Visualization. I always looked for a standard, unified way to represent and handle graphs when developing prototypes. So my interest in this project is quite natural, and I am willing to help and see it become a robust project. -- 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
