Generic weight types and updated shortest path implementations
--------------------------------------------------------------
Key: SANDBOX-356
URL: https://issues.apache.org/jira/browse/SANDBOX-356
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Attachments:
GenericWeightTypesAndUpdatedShortestPathImplementations.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
