[
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
