I'm trying to find all paths through the following graph:

    start
    /   \
c--A-----b--d
    \   /
     end

It is only acyclic in that vertices with lowercase names may only be visited once, e.g. vertex d should not be visited, because to include it in a path through the graph, vertex b would have to be visited twice.

All permissible paths through the graph are:

start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end

Nearly all my google results are for directed graphs, and the only way I can find of making them work for my undirected graph is to add each edge twice, once in each direction, which I think is even messier than my current, non-working solution.

The best I have come up with it this attempt at a recursive traversal through the graph:

private HashSet<List<Edge>> paths = new();
private List<Edge> _path = new();
HashSet<Vertex> smallsVisited = new HashSet<Vertex>();
private void Traverse(Vertex start)
{
    var traverseEnd = GetVertexByName("end");
    if (start == traverseEnd)
    {
        paths.Add(_path.ToList());
        _path.Clear();
        return;
    }

    if (smallsVisited.Contains(start))
        return;

    if (start.Name != "start" && char.IsLower(start.Name[0]))
        smallsVisited.Add(start);

    var traverseStart = GetVertexByName("start");
    var neighbours = _adjacencyList[start].Where(v => v != traverseStart);
    foreach (var end in neighbours)
    {
        _path.Add(new Edge(start, end));
        Traverse(end);
    }
}

I call Traverse with the vertex called start to set the process rolling. I expected traversal to stop when the parameter start is the vertex named end but the result is only a single path which is vertex start to vertex b.

I am very new, only a few days, to working with graphs, and very rusty at recursion. What am I doing wrong?

CodePudding user response：

Here's how I'd handle traversing this with recursion. I've setup the graph as a dictionary of vertex name to a list of neighbors. Also since "start" begins with a lower case character I'm just relying on that to have it not go back through that vertex. The other trick here is to pass the path to the current vertex so that you can build on it in each recursion but in a way that each one is not effected by other recursions. And since you have the path you can just check to see if it contains the lower case vertex. Also note that we can still get infinite paths and StackOverflow depending on the graph. For instance if your graph changed the "b" to a "B" then you could travel between "A" and "B" an infinite number of times and this code would not detect that in any way.

void Main()
{
    var graph = new Dictionary<string, List<string>>
    {
        ["start"] = new List<string>{"A", "b"},
        ["A"] = new List<string>{"c", "b", "end", "start"},
        ["b"] = new List<string>{"A", "d", "end", "start"},
        ["c"] = new List<string>{"A"},
        ["d"] = new List<string>{"b"},
        ["end"] = new List<string>{"A", "b"},
    };
    
    var result = Traverse(graph, "start", "end");

    foreach(var x in result)
    {
        Console.WriteLine(string.Join("-", x));
    }
}

public static IEnumerable<IEnumerable<string>> Traverse(
    Dictionary<string, List<string>> graph, 
    string current, 
    string end, 
    IEnumerable<string> path = null)
{
    // Initialize the path if we don't have one yet.
    path ??= Enumerable.Empty<string>();
    
    // Do not allow the path to go to a lower cast vertex 
    // more than once.
    if(char.IsLower(current[0]) && path.Contains(current))
    {
        yield break;
    }
    
    path = path.Append(current);
    
    // If we are at the end then return the path and break.
    if(current == end)
    {
        yield return path;
        yield break;
    }
    
    // Find all the paths from the current vertex through
    // each of it's neighbors and return them.
    foreach(var neighbor in graph[current])
    {
        foreach(var subPath in Traverse(graph, neighbor, end, path))
        {
            yield return subPath;
        }   
    }   
}

And the Result is

start-A-c-A-b-A-end
start-A-c-A-b-end
start-A-c-A-end
start-A-b-A-c-A-end
start-A-b-A-end
start-A-b-end
start-A-end
start-b-A-c-A-end
start-b-A-end
start-b-end