[jira] [Commented] (SANDBOX-332) [graph] add FloydWarshall algorithm implementation

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