[jira] [Updated] (SANDBOX-409) Drop Vertex/Edge marker interfaces
[
https://issues.apache.org/jira/browse/SANDBOX-409?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-409:
---
Attachment: SANDBOX-409_ExportersWithVarargsForVertexAndEdgeProperties.patch
Hi Simone,
as anticipated on ML I played a bit with the branch to (re)add export
functionalities. You can find my (very incomplete) attempts to use varargs for
Vertex and Edge properties. However the tests in {{export.ExportTestCase}} give
a warning on the type of the varargs array.
See if you can make sense out of it and maybe even get rid of the warning... :)
Ciao
Claudio
Drop Vertex/Edge marker interfaces
--
Key: SANDBOX-409
URL: https://issues.apache.org/jira/browse/SANDBOX-409
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Simone Tripodi
Assignee: Simone Tripodi
Attachments:
SANDBOX-409_ExportersWithVarargsForVertexAndEdgeProperties.patch
As widely discussed in the ML, there is a general agreement on dropping the
{{Vertex}} and {{Edge}} interface and allow {{Graph}} using whatever object
as node/arc.
Due to the large number of modifications involved, I intend working on it on
a separate branch.
--
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
[jira] [Updated] (SANDBOX-404) Simplify weight model
[
https://issues.apache.org/jira/browse/SANDBOX-404?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-404:
---
Attachment: SANDBOX-404_FromMonoidToAddition.patch
Hi Simone!
I completely agree with your last sentence, and that is one of the reasons why
I am providing this extended patch where there is no {{Monoid}} anymore, only
{{Addition}} -- simplification of the weight operations model!
No use for theoretical algebra in the code: only clear, unambiguous names
({{sum}}, {{negate}}, {{zero}}). I think that is a primary concern as long as
we have the power to improve semantics before things go live (releases,
people using the library consistently and getting used to class names, etc).
Also, no risk to extend {{Monoid}} twice *if and when* we add
{{Multiplication}} or whatsoever, because it will be totally independent.
Hoping to meet your agreement and the one of others working on our beloved
[graph] ;)
Claudio
Simplify weight model
-
Key: SANDBOX-404
URL: https://issues.apache.org/jira/browse/SANDBOX-404
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Simone Tripodi
Attachments: SANDBOX-404.patch,
SANDBOX-404_FromMonoidToAddition.patch,
SANDBOX-404_gettingRidOfOrderedMonoid.patch
As discussed on {{dev@}}, {{Zero}}, {{Semigroup}} and {{Monoid}} can be
merged directly in one single interface
--
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
[jira] [Updated] (SANDBOX-404) Simplify weight model
[
https://issues.apache.org/jira/browse/SANDBOX-404?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-404:
---
Attachment: SANDBOX-404_gettingRidOfOrderedMonoid.patch
Hi Simone,
I am attaching a patch that begins with yours and goes one step further,
getting rid of {{OrderedMonoid}} basically everywhere and replacing it with
{{Monoid Comparator}}. That has two reasons:
* separating main operations/properties, so that every algorithm specifies what
is needed in terms of a set of interfaces;
* leading the way to the next refactoring step where {{Monoid}} is converted
into {{Addition}}, in order to better represent what it actually does.
So one step is missing, i.e. renaming {{Monoid}} into {{Addition}} (and
{{Monoid#append}} into {{Addition#sum}}, etc) -- but I first wanted to get some
feedback on this one.
Ciao
Claudio
Simplify weight model
-
Key: SANDBOX-404
URL: https://issues.apache.org/jira/browse/SANDBOX-404
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Simone Tripodi
Attachments: SANDBOX-404.patch,
SANDBOX-404_gettingRidOfOrderedMonoid.patch
As discussed on {{dev@}}, {{Zero}}, {{Semigroup}} and {{Monoid}} can be
merged directly in one single interface
--
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
[jira] [Updated] (SANDBOX-395) Correct names for classes and variables related to operations on weights
[
https://issues.apache.org/jira/browse/SANDBOX-395?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-395:
---
Attachment:
SANDBOX-395_CorrectClassAndVariableNamesForWeightOperations.patch
Hi,
I attach my proposed change as anticipated on mailing list. Note that:
* all base implementations of weight operations change names with the new
pattern {{*BaseOperations}} (e.g. {{DoubleWeight}} becomes
{{DoubleWeightBaseOperations}});
* all weight-operation variables passed to algorithms and data structures
change name from the implemented interface (e.g. {{orderedMonoid}}) to
{{weightOperations}}. To reflect this also the generic type changes from {{OM}}
to {{WO}};
* all comments, documentation and null-check strings are changed accordingly;
* in {{SuperVertex}} the {{Comparator}} needed for the operations is called
{{weightComparator}}.
Correct names for classes and variables related to operations on weights
Key: SANDBOX-395
URL: https://issues.apache.org/jira/browse/SANDBOX-395
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Assignee: Claudio Squarcella
Priority: Minor
Labels: graph, operations, weight
Attachments:
SANDBOX-395_CorrectClassAndVariableNamesForWeightOperations.patch
Hi all,
as discussed in ML already the current classes/variables that refer to
operations on weights can be renamed for better expressiveness:
* all the classes under {{weight.primitive}} should be renamed from {{XXX}}
to {{XXXOperations}} because they actually contain operations on weights
(they do not represent weights themselves);
* in the actual algorithms, all variable names for weight operations should
actually be something like {{weightOperations}} instead of the name of the
interface (e.g. {{orderedMonoid}}).
--
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
[jira] [Updated] (SANDBOX-385) Provide Edmonds-Karp algorithm
[
https://issues.apache.org/jira/browse/SANDBOX-385?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-385:
---
Attachment: SANDBOX-385_AddedEdmondsKarpImplementationAndTest.patch
Hello,
I implemented Edmonds-Karp plus a test for it.
I also found a bug in the previous implementation of
{{DefaultVisitAlgorithmsSelector}} and fixed it: vertices are added to the
visit stack/queue only if the edge leading to them is actually discovered.
Finally I extracted common code in the {{FlowNetworkHandler}} creating a
utility class called {{FlowNetwork}}, that represents a directed graph with
flow capacity.
Hoping this helps,
Claudio
Provide Edmonds-Karp algorithm
--
Key: SANDBOX-385
URL: https://issues.apache.org/jira/browse/SANDBOX-385
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Marco Speranza
Attachments: SANDBOX-385_AddedEdmondsKarpImplementationAndTest.patch
Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm]
algorithm into org.apache.commons.graph.flow package.
--
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
[jira] [Updated] (SANDBOX-355) Provide Flow algorithms
[
https://issues.apache.org/jira/browse/SANDBOX-355?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-355:
---
Attachment: SANDBOX-355_FixBugInFordFulkerson.patch
Hi,
I am attaching a patch fixing a bug in my previous implementation of
{{FordFulkerson}}. No {{unchecked}} type casting anymore, this one should be ok
:)
Claudio
Provide Flow algorithms
---
Key: SANDBOX-355
URL: https://issues.apache.org/jira/browse/SANDBOX-355
Project: Commons Sandbox
Issue Type: New Feature
Components: Graph
Reporter: Simone Tripodi
Attachments: SANDBOX-355_FixBugInFordFulkerson.patch,
SANDBOX-355_FordFulkersonImplementationAndTest.patch
right now the {{org.apache.commons.graph.flow}} package contains an empty
implementation of
[Ford-Fulkerson|http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm]'s
algorithm, that needs to be filled.
Other algorithms that work on resolving Flow-related problems, are welcome.
--
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
[jira] [Updated] (SANDBOX-367) Move base implementations from test to main
[
https://issues.apache.org/jira/browse/SANDBOX-367?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-367:
---
Attachment: MoveBaseImplementationsFromTestToMain.patch
Move base implementations from test to main
---
Key: SANDBOX-367
URL: https://issues.apache.org/jira/browse/SANDBOX-367
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Priority: Trivial
Labels: graph, implementations, main, model, test
Attachments: MoveBaseImplementationsFromTestToMain.patch
Hi,
very tiny patch to move default implementations from test (in package
{{model}}: {{BaseLabeledEdge}}, {{BaseLabeledWeightedEdge}} and
{{BaseLabeledVertex}}) to main. Needed for other implementations that require
manipulation of input graphs -- e.g. the upcoming Ford-Fulkerson ;)
--
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
[jira] [Updated] (SANDBOX-367) Move base implementations from test to main
[
https://issues.apache.org/jira/browse/SANDBOX-367?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-367:
---
Attachment: SANDBOX-367_MoveBaseImplementationsFromTestToMain.patch
oops, just realized the patch doesn't include new file adds. I am attaching a
new one, which btw has a better name :)
Claudio
Move base implementations from test to main
---
Key: SANDBOX-367
URL: https://issues.apache.org/jira/browse/SANDBOX-367
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Priority: Trivial
Labels: graph, implementations, main, model, test
Attachments: MoveBaseImplementationsFromTestToMain.patch,
SANDBOX-367_MoveBaseImplementationsFromTestToMain.patch
Hi,
very tiny patch to move default implementations from test (in package
{{model}}: {{BaseLabeledEdge}}, {{BaseLabeledWeightedEdge}} and
{{BaseLabeledVertex}}) to main. Needed for other implementations that require
manipulation of input graphs -- e.g. the upcoming Ford-Fulkerson ;)
--
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
[jira] [Updated] (SANDBOX-355) Provide Flow algorithms
[
https://issues.apache.org/jira/browse/SANDBOX-355?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-355:
---
Attachment: SANDBOX-355_FordFulkersonImplementationAndTest.patch
Hi,
find attached an implementation for the algorithm of Ford and Fulkerson to find
the max flow in a network.
The implementation is split between a main class {{FordFulkerson}} which
provides two public methods (one for generic weights, the other for {{Integer}}
weights) and an auxiliary class {{FlowNetworkHandler}} which does the dirty
job.
I also implemented a test using [this
example|http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm#Integral_example]
and it runs just fine.
I am available for clarifications and comments.
Ciao,
Claudio
Provide Flow algorithms
---
Key: SANDBOX-355
URL: https://issues.apache.org/jira/browse/SANDBOX-355
Project: Commons Sandbox
Issue Type: New Feature
Components: Graph
Reporter: Simone Tripodi
Attachments: SANDBOX-355_FordFulkersonImplementationAndTest.patch
right now the {{org.apache.commons.graph.flow}} package contains an empty
implementation of
[Ford-Fulkerson|http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm]'s
algorithm, that needs to be filled.
Other algorithms that work on resolving Flow-related problems, are welcome.
--
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
[jira] [Updated] (SANDBOX-364) Adding generic weight type to model
[
https://issues.apache.org/jira/browse/SANDBOX-364?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-364:
---
Attachment: AddingGenericWeightTypeToModel.patch
Adding generic weight type to model
Key: SANDBOX-364
URL: https://issues.apache.org/jira/browse/SANDBOX-364
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Priority: Minor
Labels: generic, graph, weight, weightededge
Attachments: AddingGenericWeightTypeToModel.patch
Hello,
with this patch I introduce generic weight types in all the implementations
of the domain (mainly classes in the {{model}} packages both in {{main}} and
{{test}}). Consequently I updated tests and references to be fully generic.
One side effect is that {{WeightedEdge}} does not implement {{Comparable}}
anymore, because that would imply passing it a {{Comparator}} for weights as
an argument upon creation. Instead, without polluting {{WeightedEdge}}, I
changed the classes where it was needed to be {{Comparable}} (e.g. in
{{Kruskal}} there is a {{PriorityQueue}} that is now initialized with an
appropriate {{Comparator}} instead of relying on {{Comparable}} edges).
All tests are green. Hoping to help :-)
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
[jira] [Updated] (SANDBOX-358) Early return/termination for graph visit
[
https://issues.apache.org/jira/browse/SANDBOX-358?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-358:
---
Attachment: EarlyTerminationAndSubgraphSkipForSearchAlgorithms.patch
Hi,
so I actually changed signatures for methods in {{GraphVisitHandler}}:
* {{discoverVertex}} and {{discoverEdge}} now tell the algorithm if the
corresponding {{Vertex}} and {{Edge}} should be expanded (i.e. if their
neighbors should be added to the visit queue);
* {{finishVertex}} and {{finishEdge}} tell if the algorithm can be ended
prematurely (because the search is complete, e.g. before the target element was
found).
All tests still work. I hope you guys like this one :)
Claudio
Early return/termination for graph visit
Key: SANDBOX-358
URL: https://issues.apache.org/jira/browse/SANDBOX-358
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Priority: Minor
Labels: graph, visit, visithandler
Attachments: EarlyTerminationAndSubgraphSkipForSearchAlgorithms.patch
Original Estimate: 72h
Remaining Estimate: 72h
Hello,
the current implementations in the class {{Visit}} (package
{{org.apache.commons.graph.visit}}) do not include the possibility to stop
the search prematurely. That would be more natural (and faster) for many
kinds of search, e.g. when looking for the first occurrence of a specific
pattern (vertex, path with certain features, etc).
The easiest solution: changing all method signatures in {{GraphVisitHandler}}
from {{void}} to {{boolean}}, forcing the handler to answer the question:
_should I continue?_
I understand semantics get a bit entangled (well, not with an appropriate
documentation!), so I am open to more verbose options: e.g. a method
{{isSearchComplete}} to call after every step... but that would only be more
verbose, wouldn't it?
Waiting for feedback and ready to patch :-)
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
[jira] [Updated] (SANDBOX-356) Generic weight types and algorithms implementations based on wighted graphes
[
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
[jira] [Updated] (SANDBOX-356) Generic weight types and updated shortest path implementations
[
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 {{HeuristicV,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
[jira] [Updated] (SANDBOX-356) Generic weight types and updated shortest path implementations
[
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
[jira] [Updated] (SANDBOX-346) DotExporter only exports weights that extend Number
[ https://issues.apache.org/jira/browse/SANDBOX-346?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Claudio Squarcella updated SANDBOX-346: --- Attachment: DotExporterOnlyExportsWeightsExtendingNumber.patch patch for DotExporter DotExporter only exports weights that extend Number --- Key: SANDBOX-346 URL: https://issues.apache.org/jira/browse/SANDBOX-346 Project: Commons Sandbox Issue Type: Improvement Components: Graph Reporter: Claudio Squarcella Priority: Minor Labels: dot, dotexporter, double, graph, weight Attachments: DotExporterOnlyExportsWeightsExtendingNumber.patch Hi, I propose a tiny patch for the DotExporter in order to print weight as an edge attribute only when the actual weight extends Number, using the method getDouble(). This is to be fully compliant with the DOT language specification on the attribute weight (see http://www.graphviz.org/content/attrs#aweight). Hope this helps, 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
[jira] [Updated] (SANDBOX-345) Weighted as an interface with generic weight type
[
https://issues.apache.org/jira/browse/SANDBOX-345?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claudio Squarcella updated SANDBOX-345:
---
Attachment: WeightedAsAnInterfaceWithGenericWeightType.patch
patch to enable interface WeightedW with generic weight type
Weighted as an interface with generic weight type
-
Key: SANDBOX-345
URL: https://issues.apache.org/jira/browse/SANDBOX-345
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Claudio Squarcella
Priority: Minor
Labels: graph, weight, weighted
Attachments: WeightedAsAnInterfaceWithGenericWeightType.patch
Hello,
after recent discussions on the mailing list ([Graph] On graph weight
type(s)) I am proposing a first patch to enable support for generic weights
in the current implementation.
Main changes include:
- adding an interface WeightedW with method W getWeight()
- modifying WeightedEdge, WeightedPath, WeightedGraph etc. to implement the
new interface
- changing the implemented algorithms (at the moment they all still require
weights to be Double)
- changing the DOT exporter (prints the weight as an attribute only if it is
of type Double)
- incidentally also fixing a small bug in the DOT exporter ('weight' was part
of the label, now it is a proper attribute as documented in DOT language
specs http://www.graphviz.org/content/attrs#dweight)
This can be the first safe step to dig into different types and/or properties
of weights.
Please let me know if it looks good.
Cheers,
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
