[Bug] EdgeDepthFirstSearchAlgorithm does not find multiple paths when the root vertex has multiple edges

[TheDudeCode]

Considering the following graph

For this graph we would like to know all possible paths between two nodes. So for the example below the resulting paths between nodes 0 and 2 would be:

• 0 -> 2
• 0 -edge A-> 1 -> 2
• 0 -edge B-> 1 -> 2

The code to accomplish this is:

var startNode = "0";
var endNode = "2";

var graph = new AdjacencyGraph<string, TaggedEdge<string, string>>(allowParallelEdges: true);

var edges = new List<TaggedEdge<string, string>>{
    new TaggedEdge<string, string>("0", "1", "edge A"),
    new TaggedEdge<string, string>("0", "1", "edge B"),
    new TaggedEdge<string, string>("1", "2", string.Empty),
    new TaggedEdge<string, string>("0", "2", string.Empty),
    new TaggedEdge<string, string>("0", "3", string.Empty),
    new TaggedEdge<string, string>("1", "3", string.Empty), };
edges.ForEach(x => graph.AddVerticesAndEdge(x));

var algo = new EdgeDepthFirstSearchAlgorithm<string, TaggedEdge<string, string>>(graph);
var observer = new EdgePredecessorRecorderObserver<string, TaggedEdge<string, string>>();

using (observer.Attach(algo))
{
    algo.Compute(startNode);
}

var allPaths = observer.AllPaths().Where(x => x.Last().Target == endNode)

However only 2 paths are found, not finding the one that has edge B:

• 0 -> 2
• 0 -edge A-> 1 -> 2

Would we add a parallel edge between nodes 1 and 2, then indeed 3 paths are found.

[TheDudeCode]

I have also found that when the root vertex has more than one (non-parallel) edge, that only one of these edges result in a path.

My test case:

// Create the following graph:
// 2 ⮀ 0
//   ⭨ ↓ ⭨ 3
//     1 ⭧
var graph = new AdjacencyGraph<int, Edge<int>>();
graph.AddVerticesAndEdge(new Edge<int>(0, 1));
graph.AddVerticesAndEdge(new Edge<int>(0, 2));
graph.AddVerticesAndEdge(new Edge<int>(0, 3));
graph.AddVerticesAndEdge(new Edge<int>(2, 0));
graph.AddVerticesAndEdge(new Edge<int>(2, 1));
graph.AddVerticesAndEdge(new Edge<int>(1, 3));

// Set source and destination 
var source = 2;
var destination = 3;
var algo = new EdgeDepthFirstSearchAlgorithm<int, Edge<int>>(graph);
var observer = new EdgePredecessorRecorderObserver<int, Edge<int>>();

using (observer.Attach(algo))
{
    algo.Compute(source);
}

var listOfPaths = observer.AllPaths()
    .Where(x => x.Last().Target == destination)
    .ToList();

// Check
listOfPaths.Should().HaveCount(3, because: "There are 3 paths from node 2 to node 3");
listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge21, edge13 }, because: "One path is from 2 to 1 to 3");
listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge20, edge03 }, because: "One path is from 2 to 0 to 3");
listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge20, edge01, edge13 }, because: "One path is from 2 to 0 to 1 to 3");

Expected outcome is 3 paths:

• 2 -> 0 -> 3
• 2 -> 0 -> 1 -> 3
• 2 -> 1 -> 3

Instead the result is 2 paths:

• 2 -> 0 -> 3
• 2 -> 0 -> 1 -> 3

So the path option that includes the 2 -> 1 edge is not found.

[KeRNeLith]

Hello,

First of all, thank you for your report. I may be wrong but maybe both issues are more or less related. We should investigate what's going wrong. BTW to assert the behavior is correct adding those tests will be a good point.

If you have time feel free to suggest a fix via a PR. ;-)

[TheDudeCode]

You're welcome :). The two cases/issues feel very related, but perhaps the two cases could end up as separate tests.

I have had a quick look in the implementation of the algorithm but found it quite difficult to follow and currently my time is quite limited, so for now I'll leave it at that.

[KeRNeLith]

@TheDudeCode I was working on a fix, but infortunatly it seems to not well cover the issue and not breaking the algorithm :s Meanwhile if you had time to try something feel free to propose it.

[TheDudeCode]

I think that I have found where the error lies and have implemented a very dirty fix/workaround that is in no way good enough to incorporate into QuikGraph. But I'll try to propose a new branch with my changes early next week to show what I've done

[TheDudeCode]

Ok it seems a bit more work to get everything compiling so in the meantime here are my findings in text. I think that there are two bugs, one in EdgeDepthFirstSearchAlgorithm and one in EdgePredecessorRecorderObserver.

The EdgeDepthFirstSearchAlgorithm does visit one edge but not the parallel edge from the start vertex. My (very dirty and performance heavy) fix for this is to move the call to OnDiscoverTreeEdge above the check for edgeColor == white:

private void Visit([NotNull] TEdge rootEdge, int depth)
{
    Debug.Assert(rootEdge != null);

    // Mark edge as gray
    EdgesColors[rootEdge] = GraphColor.Gray;
    // Add edge to the search tree
    OnTreeEdge(rootEdge);

    // Iterate over out-edges
    var outEdges = VisitedGraph.OutEdges(rootEdge.Target);
    foreach (TEdge edge in outEdges)
    {
        ThrowIfCancellationRequested();
        OnDiscoverTreeEdge(rootEdge, edge);           // <-- moved outside check

        // Check edge is not explored yet,
        // If not, explore it
        if (EdgesColors[edge] == GraphColor.White)
        {
            int newDepth = depth + 1;
            if (newDepth <= MaxDepth)
...

While it is not a good fix it does now make the search algorithm find the parallel edge. I have tried another approach that copied the EdgeColors dictionary for each parallel edge in the Visit function scope, I'm not quite sure anymore why I didn't go for this approach.

But now the EdgePredecessorRecorderObserver does not seem to store the parallel edge. Since it is some time ago since I looked at this I'm not quite sure what the problem was, but I think that was to do with the EdgesPredecessors dictionary overwriting the first edge from the start vertex with the discovery of the second edge due to the nature of a dictionary. My fix for this was to implement my own EdgePredecessorRecorderObserver which stores the edges into an adjacency list much like the adjacency graph. But I'm really not very happy with this approach since it does not allow me to query the resulting result from the observer.

So that's my current brain dump on this issue. I'm interested in your findings and please tell me if my analysis is rubbish :).

[KeRNeLith]

@TheDudeCode Your analysis seems to go in a similar direction than what I was able to explore on my last debugging session.

I ended thinking that the EdgesPredecessors dictionary was limiting the possibility to have multiple edges, so I did go by updating it to support what you called an adjacency list. Unfortunately I think I didn't made all the necessary changes to get it working well.

I pushed my debug try in a branch, here is the relevant commit. Do not pay attention to all code, I have some dirty stuff from others "tests" pushed in the same time. This branch was just for experimentations.

[TheDudeCode]

Very nice! I've ran my unit tests against the changed algorithm and observer and most tests seem to succeed. There were (only) 2 test cases that didn't pass.

First unit test:

            // Create the following graph:
            // 0 → 1 → 3 → 4 → 5
            //       ⭨ 2 ⭧
            var edge01 = new Edge<int>(0, 1);
            var edge12 = new Edge<int>(1, 2);
            var edge13 = new Edge<int>(1, 3);
            var edge34 = new Edge<int>(3, 4);
            var edge24 = new Edge<int>(2, 4);
            var edge45 = new Edge<int>(4, 5);
            var graph = new AdjacencyGraph<int, Edge<int>>(allowParallelEdges: true);
            graph.AddVerticesAndEdge(edge01);
            graph.AddVerticesAndEdge(edge13);
            graph.AddVerticesAndEdge(edge12);
            graph.AddVerticesAndEdge(edge34);
            graph.AddVerticesAndEdge(edge24);
            graph.AddVerticesAndEdge(edge45);

            // Set source 
            var source = 0;
            var algo = new EdgeDepthFirstSearchAlgorithm<int, Edge<int>>(graph);
            var observer = new EdgePredecessorRecorderObserver<int, Edge<int>>();

            using (observer.Attach(algo))
            {
                algo.Compute(source);
            }

            var listOfPaths = observer.AllPaths();

            // Check
            listOfPaths.Should().HaveCount(2, because: "There is 2 path from node 0 to end nodes");
            listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge01, edge13, edge34, edge45 }, because: "One path is from 0 -> 1 -> 3 -> 4 -> 5");
            listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge01, edge12, edge24, edge45 }, because: "One path is from 0 -> 1 -> 2 -> 4 -> 5");

Second unit test:

            // Create the following graph with start node 2 and end node 3:
            // 2 → 0
            //   ⭨ ↓ ⭨ 3 → 4
            //     1 ⭧
            var edge01 = new Edge<int>(0, 1);
            var edge03 = new Edge<int>(0, 3);
            var edge20 = new Edge<int>(2, 0);
            var edge21 = new Edge<int>(2, 1);
            var edge13 = new Edge<int>(1, 3);
            var edge34 = new Edge<int>(3, 4);
            var graph = new AdjacencyGraph<int, Edge<int>>(allowParallelEdges: true);
            graph.AddVerticesAndEdge(edge01);
            graph.AddVerticesAndEdge(edge03);
            graph.AddVerticesAndEdge(edge20);
            graph.AddVerticesAndEdge(edge21);
            graph.AddVerticesAndEdge(edge13);
            graph.AddVerticesAndEdge(edge34);

            // Set source and destination 
            var source = 2;
            var algo = new EdgeDepthFirstSearchAlgorithm<int, Edge<int>>(graph);
            var observer = new EdgePredecessorRecorderObserver<int, Edge<int>>();

            using (observer.Attach(algo))
            {
                algo.Compute(source);
            }

            //var adjacentEdges = observer.AdjacentEdges;
            var listOfPaths = observer.AllPaths();

            // Check
            listOfPaths.Should().HaveCount(3, because: "There are 3 paths from node 2 to end node 3");
            listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge21, edge13, edge34 }, because: "One path is from 2 -> 1 -> 3 -> 4");
            listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge20, edge03, edge34 }, because: "One path is from 2 -> 0 -> 3 -> 4");
            listOfPaths.Should().ContainEquivalentOf(new List<Edge<int>> { edge20, edge01, edge13, edge34 }, because: "One path is from 2 -> 0 -> 1 -> 3 -> 4");

Looking at the first test it seems that the first resulting path is duplicated where the second resulting path is missing.

Probably a side question, but would you know how to get the observer's EdgesPredecessors filtered for those paths that end on a specific edge target vertex?

[TruePluto]

//var adjacentEdges = observer.AdjacentEdges;
var listOfPaths = observer.AllPaths();

foreach (var path in listOfPaths)
{
    Console.Write( source);
    foreach (var edge in path)
    {
        Console.Write("->"+edge.Target);
    }
    Console.WriteLine();
}

why the result is following : 2->0->1->3->4 2->0->3 2->1