[ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13184426#comment-13184426 ]
Claudio Squarcella commented on SANDBOX-356: -------------------------------------------- Hi Simone, yes, I double-checked and essentially weights are only used (so far) in the two packages {{shortestpath}} and {{spanning}}. So let's just close the issue and keep in mind the new approach for new algorithm implementations :) Ciao, Claudio > Generic weight types and algorithms implementations based on wighted graphes > ---------------------------------------------------------------------------- > > Key: SANDBOX-356 > URL: https://issues.apache.org/jira/browse/SANDBOX-356 > Project: Commons Sandbox > Issue Type: Improvement > Components: Graph > Reporter: Claudio Squarcella > Assignee: Simone Tripodi > Labels: generic, graph, shortestpath, type, weight > Attachments: GenericWeightTypeAlsoForAStar.patch, > GenericWeightTypesAndUpdatedShortestPathImplementations.patch, > SANDBOX-356_GenericWeightTypesForSpanningTreeAlgorithms.patch > > > Hello, > with this issue I propose quite a major improvement to the current version of > Apache Commons Graph, aimed at introducing generic types for weights (edge > weights, vertex weights, etc) and decoupling related properties and > operations using external classes. The proposed changes reflect observations > and proposals that have been evaluated on the dev mailing list, particularly > in the thread with title "On graph weight type(s)". > A new top level package {{weight}} contains a hierarchy of interfaces > representing different "families" of weights with their properties and > operations: {{Zero}}, {{Semigroup}}, {{Monoid}}, {{OrderedMonoid}}. These > interfaces are meant to be specified as input by different algorithms > depending on the properties needed: e.g. some only require an ordering on the > weights, some apply operations, etc. A subpackage called {{primitive}} > contains two implementations, {{DoubleWeight}} and {{IntegerWeight}}, > respectively wrapping properties and operations on weights of type {{Double}} > and {{Integer}}. > In addition, some of the implementations in the package {{shortestpath}} have > been updated to take advantage of the new generic weight types. In particular > each of the three classes {{Dijkstra}}, {{BellmannFord}} and > {{FloydWarshall}} now has two public methods: a generic one (working with any > kind of weight, provided an {{OrderedMonoid}}) and a "shortcut" for weights > of type {{Double}}, which is basically identical to the current signature. > Other classes in the package were subject to minor changes to support the > improvements. As an exception, {{AStar}} is still tied to {{Double}} weights > for now: as a future step that could also use generic weights (but it needs > more thinking for the heuristics). > Further, in order to handle generic weight types, I got rid of > {{Double.POSITIVE_INFINITY}} as a way to represent unreachability between two > endpoints in a graph and replaced it with related boolean methods. > Finally, all the tests were updated for compatibility with the new > signatures, and they all run smoothly. > I hope this patch meets the approval of other developers/users. I am > available for discussion and clarification. > Ciao, > Claudio -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira