[
https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-356:
---------------------------------------
Attachment: SANDBOX-356_GenericWeightTypesForSpanningTreeAlgorithms.patch
Hi,
third patch attached, this time for spanning tree algorithms ({{Prim}} and
{{Kruskal}}, the two implemented so far). The interface {{SpanningTree}} itself
is now weight-generic, together with the implementation
{{MutableSpanningTree}}. Tests updated accordingly.
As a side effect the {{Monoid}} now has an additional method {{inverse}}, which
returns the inverse of an input weight (needed for spanning trees for
subtraction of weights). It perfectly fits math theory on monoids ;)
If this works we are a step closer to closing this issue, or actually already
there -- if I am not wrong, all implemented algorithms requiring weights have
been updated.
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
