Shortest path depends on vertex sequence

[integer]

I have code like this:

$graph = new \Fhaculty\Graph\Graph();
$v1 = $graph->createVertex(1);
$v2 = $graph->createVertex(2);
$v5 = $graph->createVertex(5);
$v6 = $graph->createVertex(6);

$v1->createEdge($v2)->setWeight(4);
$v2->createEdge($v5)->setWeight(4);
$v5->createEdge($v6)->setWeight(4);

$alg = new \Fhaculty\Graph\Algorithm\ShortestPath\Dijkstra($v1);
echo $graph;
var_dump($alg->getDistance($v6));

it has output as excepted:

graph G {
  1 -- 2 [label=4]
  2 -- 5 [label=4]
  5 -- 6 [label=4]
}
int(12)

but if I change sequence of creating vertices

$v1 = $graph->createVertex(1);
$v2 = $graph->createVertex(2);
$v6 = $graph->createVertex(6);  // this vertex was created as last
$v5 = $graph->createVertex(5);

// other code is the same

I get this output:

graph G {
  1 -- 2 [label=4]
  2 -- 5 [label=4]
  5 -- 6 [label=4]
}

And distance isn't count because maximum execution time exceeded.

Graph is the same in both cases, so result has to be same too.

[clue]

Thanks for the report!

The ordering of the vertices does not necessarily affect its output, which is correct. The ordering of the vertices should also not affect the Dijkstra algorithm, I'll look into this issue more closely later today.

[clue]

Reproducible on current master, thanks for providing the test script!

[clue]

TL;DR:
Turns out we're using some assumptions which make our algorithms only work on directed graphs and some undirected ones.

All of our algorithms in the ShortestPath namespace (Dijkstra, Moore-Bellman-Ford, Breadth-First-Search) solve the single-source shortest path problem by producing a shortest path tree. I.e. they all only implement a single getEdges() method that returns a set of Edges that can be used to reach all other vertices from a single given start vertex.

So if you're running either of the shortest path algorithms on a complete Graph (say K_6) it will return something like this:

        A
      / | \
     B  C  D
          / \
         E   F

Initially, our algorithms were designed to work on directed (i.e. not undirected) graphs. This is also what you'll likely find (perhaps implicitly) when looking for resources on Dijkstra's algorithm. Assuming the graph is directed, its shortest path tree will also be directed and the following logic applies:

Now if you need to find the edges between vertex A and F (getEdgesTo($v6) or getWalkTo($v6)), we "walk up" in this tree in backwards order by starting at vertex F. This is done because in this tree there's always a single edge on the path to the start vertex, i.e. the one that "points towards" our current vertex. Whereas if we were to start at the start vertex A, there are several possible edges that "point away".

In the above tree, we start at vertex F, check all available edges, pick the first (and only only) that points towards our current vertex and then move on to "the other side" of if, Vertex D. Now at vertex D, we do exactly the same thing as there's also only a single edge that points "towards" our current vertex and we can repeat this process until we reach our start vertex A. Finally, we reverse the order and receive a path "A - D - F"

We figured it should be fairly easy to also run the very same algorithms on undirected and even mixed graphs. It turns out, it's not :) Running the algorithms on the same undirected graph (undirected K_6) also returns the same tree, except its edges also being undirected, obviously. This may sound like a very subtle difference, but because of this, our above logic no longer works out:

In the above tree, we again start at vertex F, check all available edges, pick the first (and in this case only) that points towards our current vertex and then move on to Vertex D. Now at vertex D, we do exactly the same thing, except, now we can actually take multiple edges because they're not directed and we don't know which one "leads" to the start vertex. In this ticket we happened to pick the one that goes back to vertex F again (which is incorrect, obviously) and thus lead to the infinite loop you've observed.

Now that PR #68 makes sure we no longer take the same edges multiple times (which should absolutely never happen) we can no longer get stuck in this infinite loop. Depending on the order the edges are defined, however, we may end up picking the edge to vertex E instead. And because we're no longer allowed to take the same edge back, we end up stuck and not finding any other edge and will thus throw an OutOfBoundsException.

So simply put, this assumption works only for directed graphs. And we have yet to work out a way to handle undirected and mixed graphs. Running an additional breadth-first-search should work, but I'd like to avoid the inherent complexity if possible..

[Andrewsville]

OK, got it. So basically the problem is that all shortest path algorithms create a kind-of spanning tree and try to walk it, which obviously doesn't work reliably for undirected graphs.

Looking at the Fhaculty\Graph\Algorithm\ShortestPath\Base public methods I see following kinds:

1. getVertices, getVerticesId, hasVertex, createGraph need the whole tree but don't need to walk it. Those methods are OK with the current implementation, IMO.
2. getDistanceMap needs the whole tree and needs to walk it (or know the distances from the algorithm). I would suggest that the method returning the set of edges for the tree also returns an array [vertex: distance] that will be used instead of calculating the distance. I assume that counting the distance inside the individual algorithms will be trivial (memory wise as well as time wise).
3. getWalkTo, getEdgesTo need only the shortest path. Those methods would have to create the path from the tree somehow. I have two ideas:
   1. Create a new method in all algorithms that only returns an array of edges creating the path. Considering that the algorithm logically has to know the edge order, you wouldn't have to call the getEdgesToInternal method at all.
   2. With each edge returned by the algorithm return its starting vertex distance from the main vertex. Then it's trivial to walk the tree the correct way.
4. getDistance needs only the shortest path and needs to walk it (or know the distances from the algorithm). Again, two possible solutions:
   1. If you create a new method for only the shortest path (see 3.1), you only need to sum the weight of all edges on that path.
   2. If you don't, you can use the whole tree (see 2) and use the returned distance to that particular vertex.

[clue]

Thanks again for the investigation! I mostly agree with your observations, except perhaps for the following assumption:

I assume that counting the distance inside the individual algorithms will be trivial

If this turns out to be trivial, I'd like to apply this suggestion. Given the current class hierarchy, we'd have to adjust all three shortest path algorithms to take advantage of it. I can't really tell off-hand, but I suppose it might be trivial for Dijkstra, but tricky to implement for Moore-Bellman-Ford. If you feel like providing a patch that doesn't break any of the existing tests, I'd love to apply it, of course!

Perhaps another solution might be taking advantage of the predecessor-map in Dijkstra and Moore-Bellman-Ford. They both essentially create a map startVertex=>targetVertex which thus also includes a kind of direction, even if they encounter undirected edges. We currently apply getEdgesCheapestPredecesor() to it to receive an array of edges and thus lose this direction information, so perhaps working on that could also be a good start? Applying the appropriate logic to your observed "kinds of methods" would still apply, of course.

Maybe we can work out a test case that completely covers this subject?

[Andrewsville]

Well a basic test would be a graph like you've described in the reply after my PR. The thing is that whether the test actually covers this issue or not relies on the internals - that at some point in the source code an array of edges is returned in particular order. And that's a very fragile assumption. I would rather alter how the internals of algorithms work so that an issue like this one wouldn't appear.

[clue]

[...] that's a very fragile assumption

Yeah, I agree we should not resort to testing those internals.

The current test suite only covers directed graphs, so perhaps adding some tests for undirected (like the above) and mixed graphs will work out.

[clue]

This will be addressed with #79. Thanks to @integer for spotting and @Andrewsville for helping analyze the root issue.