[jira] [Created] (SANDBOX-356) Generic weight types and updated shortest path implementations

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (SANDBOX-356) Generic weight types and updated shortest path implementations

ASF GitHub Bot (Jira)
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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (SANDBOX-356) Generic weight types and updated shortest path implementations

ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Claudio Squarcella updated SANDBOX-356:
---------------------------------------

    Attachment: GenericWeightTypesAndUpdatedShortestPathImplementations.patch

proposed patch for generic weight types
               

> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-356) Generic weight types and updated shortest path implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (SANDBOX-356) Generic weight types and updated shortest path implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Claudio Squarcella updated SANDBOX-356:
---------------------------------------

    Attachment: GenericWeightTypeAlsoForAStar.patch

Hi,

here is a second patch to enable generic weight types also for {{AStar}}. I modified {{Heuristic<V,W>}} adding {{W}} as generic weight type. The remaining changes look pretty much like the ones for the other shortest path algorithms.

Next step: same story for spanning tree algorithms :)

Ciao,
Claudio
               

> 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: GenericWeightTypeAlsoForAStar.patch, 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-356) Generic weight types and updated shortest path implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

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

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

cool, patch has been applied, see [r1229746|https://svn.apache.org/viewvc?view=revision&revision=1229746], thanks for contributing!

As a side note: take the good practice of prefixing the patches with the issue number, i.e. {{SANDBOX-356_GenericWeightTypeAlsoForAStar.patch}} that would simplify the patch management in commons (people usually maintain more than one component at once) ;)

I'll keep the issue open waiting for Spanning Trees algorithms :) TIA!
               

> 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: GenericWeightTypeAlsoForAStar.patch, 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Simone Tripodi updated SANDBOX-356:
-----------------------------------

    Assignee: Simone Tripodi
     Summary: Generic weight types and algorithms implementations based on wighted graphes  (was: Generic weight types and updated shortest path implementations)
   

> 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
>
>
> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

     [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

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

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

Ciao Claudio,

latest patch has been successfully applied, see [r1230260|https://svn.apache.org/viewvc?view=revision&revision=1230260].

I'll let the issue open waiting for your confirmation that all weight-related algorithms have been updated with monoid as weight.

Thanks for your efforts!
               

> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Resolved] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/SANDBOX-356?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Simone Tripodi resolved SANDBOX-356.
------------------------------------

    Resolution: Fixed

Thanks Claudio for moving this topic forward!
There are "just a couple" of open issues on [graph], I don't know if you are pleased to work on them... :P
               

> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

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

Claudio Squarcella commented on SANDBOX-356:
--------------------------------------------

_of course_ i am :D
               

> 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