commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Simone Tripodi (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (SANDBOX-356) Generic weight types and updated shortest path implementations
Date Sun, 08 Jan 2012 19:48:41 GMT

    [ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13182279#comment-13182279
] 

Simone Tripodi commented on SANDBOX-356:
----------------------------------------

Really *amazing* patch Claudio, great!
I just applied it, see [r1228934|https://svn.apache.org/viewvc?view=revision&revision=1228934].

I won't mark that issue as resolved because, as you said, maybe all the work you've done could
influence improvements on the {{AStar}} heuristic, so instead of opening a new issue we can
continue working here.

Very well done!
                
> 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
>              Labels: generic, graph, shortestpath, type, weight
>         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

        

Mime
View raw message