You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Marco Speranza (JIRA)" <ji...@apache.org> on 2011/06/22 11:36:47 UTC
[jira] [Created] (SANDBOX-332) [graph] add FloydWarshall algorithm
implementation
[graph] add FloydWarshall algorithm implementation
---------------------------------------------------
Key: SANDBOX-332
URL: https://issues.apache.org/jira/browse/SANDBOX-332
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Marco Speranza
Priority: Minor
Attachments: patchAddFloydWarshallImpl.patch
Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-332) [graph] add FloydWarshall
algorithm implementation
Posted by "Simone Tripodi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13053179#comment-13053179 ]
Simone Tripodi commented on SANDBOX-332:
----------------------------------------
Ciao Marco ;)
that's simply *amazing*, congrats!!!
There are anyway 2 minor details I'd like to discuss before applying the patch, in order you can provide an improved patch:
* very fine to add {{E getEdge( V source, V target )}} method in {{Graph}} interface (I bet it is useful also in other algorithms), anyway you could improve a little the implementation in {{BaseGraph}}: what I suggest is moving the {{VertexPair}} class under {{utils}} package and adding in {{BaseGraph}} a new index {{Map<VertexPair, E>}} in the way that {{E getEdge( V source, V target )}} doesn't need to scan the {{V}} adjacency list - please note that few lines of code has to be added in {{BaseMutableGraph}} when adding and {{Edge}};
* I noticed that, differing from other shortest-path algorithms implementation, the FloydWarshall needs to maintain a data structure where all vertex pairs shortest paths are stored; I would separate the algorithm implementation and the data structure, so I'd suggest adding a new class, let's call it {{AllVertexPairsShortesPath}} for example, and modifying the {{FloydWarshall}} class with a single static method that takes in input only the {{Graph}} and gives as output the {{AllVertexPairsShortesPath}}.
WDYT?
Thanks anyway for the great effort!!!
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-332) [graph] add FloydWarshall
algorithm implementation
Posted by "Simone Tripodi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13053263#comment-13053263 ]
Simone Tripodi commented on SANDBOX-332:
----------------------------------------
Ciao Marco!
looking for your next patch, can't wait anymore! :)
Thanks in advance for your hard work!
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-332) [graph] add FloydWarshall algorithm
implementation
Posted by "Marco Speranza (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marco Speranza updated SANDBOX-332:
-----------------------------------
Attachment: patchAddFloydWarshallImpl.patch
here is my patch
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-332) [graph] add FloydWarshall algorithm
implementation
Posted by "Marco Speranza (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marco Speranza updated SANDBOX-332:
-----------------------------------
Attachment: patchAddFloydWarshallImpl_modified.patch
Hi all guys,
I just modified the patch in this way:
* I modified the FloydWarshall class and I created one single static method.
* I improved a little bit also BaseGraph adding the new index Map<VertexPair, E> and I removed old edge Set.
I'm looking forward to your suggestions and comments.
Ciao
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch, patchAddFloydWarshallImpl_modified.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-332) [graph] add FloydWarshall
algorithm implementation
Posted by "Marco Speranza (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13053228#comment-13053228 ]
Marco Speranza commented on SANDBOX-332:
----------------------------------------
Ciao Simo,
thanks for your comment.
I think that your advices are very interesting.
This evening I'll modify the patch.
have a nice day
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (SANDBOX-332) [graph] add FloydWarshall algorithm
implementation
Posted by "Simone Tripodi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-332?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Simone Tripodi resolved SANDBOX-332.
------------------------------------
Resolution: Fixed
Assignee: Simone Tripodi
the patch has been successfully applied, thanks for your hard work!!!
I just re-enabled tests on Undirected graph that were commented, everything works like a charm! Congrats!
> [graph] add FloydWarshall algorithm implementation
> ---------------------------------------------------
>
> Key: SANDBOX-332
> URL: https://issues.apache.org/jira/browse/SANDBOX-332
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Assignee: Simone Tripodi
> Priority: Minor
> Attachments: patchAddFloydWarshallImpl.patch, patchAddFloydWarshallImpl_modified.patch
>
>
> Hi all, I implemented the Floyd Warshall algorithm. This algorithm finds shortest paths between every pair of vertices.
> I based my implementation on the standard algorithm that creates a matrix NxN with all weights of the shortest paths.
> Futhermore I added a Map that contains all paths.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira