commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Simone Tripodi (JIRA)" <>
Subject [jira] [Commented] (SANDBOX-332) [graph] add FloydWarshall algorithm implementation
Date Wed, 22 Jun 2011 11:08:47 GMT


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

Thanks anyway for the great effort!!!

> [graph] add FloydWarshall algorithm implementation 
> ---------------------------------------------------
>                 Key: SANDBOX-332
>                 URL:
>             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:


View raw message