Floyd–Warshall algorithm for all-pair shortest paths

[pablormier]

[jlopezg8]

Is anyone else working on this?

[pablormier]

Hi @jlopezg8 For the moment, no plans to implement it

[jlopezg8]

Just to be clear, no plans to incorporate it or what? Because I would love to give it a try.

[gonzalezsieira]

@jlopezg8 Although at this moment we are not working on it, we are open to include your implementation in the library. Please, take a look to the contribution guidelines and try that:

• Your implementation integrates with the existing components. It would be great if you use the coding style of currently implemented algorithms (like AStar).
• The new algorithm comes with the corresponding tests that demonstrate the validity of the implementation. Feel free to re-use some of the existing JUnit tests and create some of your own, if needed.

Thanks for your interest in contributing to the library!

[jlopezg8]

Hi.

I just finished an implementation with tests and documentation, as generic as I possibly could. You can see it in my forked repo. The thing is, it expects a graph, and returns an object with the outputs and utility methods such as getting the path between any two vertices.

After thinking about it for a while, I don't see how to adapt the class to subclass Algorithm, mainly because classes that do (and the library as a whole) aim to be graph-agnostic, and are framed around progressively exploring the state space from a single initial state until reaching any of several goal states; while the Floyd-Warshall algorithm is inherently graph-centric, since it works with the graph's adjacency matrix (and thus the fully explored state space), and does not expect a single initial state, a node expander, nor any goal states, since all states would be considered initial and goal states.

With this in mind, do you have any suggestions? Or would you agree that the Floyd-Warshall algorithm, being an all-pairs algorithm, doesn't fit as well as the others single-source algorithms?

Thanks for your time.

[pablormier]

Hi @jlopezg8,

I had a look at your implementation and looks great, thanks for the effort you put on that! As you said, one common issue is to fit this kind of algorithms into the iterative framework implemented in Hipster4j. We ran into this problem many times, because no initial state / goal state is required.

I think there is no perfect solution for this. One idea could be to redefine the algorithm interface in a more generic way, for example using a pattern like the ask-and-tell (https://github.com/scikit-optimize/scikit-optimize/issues/68), and make the current "goal-oriented" interface as a subtype of this more generic interface. In this way, graph-centric algorithms could implement this type of iterative approach (the distance matrix is updated in each iteration until completion).

We would need to think about it as this is a recurrent problem we found with the current API of Hipster4j. Anyway, we are very interested in integrating your implementation in the library. What's your opinion @gonzalezsieira, any suggestion about how to proceed?

Happy Christmas!