Details
Major Description
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