Algorithm to find path between nodes

Question

First time working with any type of graph traversal. The algorithm determines whether a path exists between two nodes using breadth first searching (BFS). The BFS method returns a tuple; indicating whether a match has been found and the length between the two nodes. I implemented it this way since it's part of a private member and wont be seen externally. When the result is seen as part of the HasPath method I modeled it after the Try-Pattern similar to TryParse(...).

The local function EnqueueNonVisitedChildrenNodes is declared as such since it would make no sense to call it anywhere else. It too uses a tuple to simplify its invocation.

Am I properly using the tuple type? Is there anything that could be improved with code structure?

using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Name = {Name}, ChildCount = {Children.Count}")]
public class Node
{
    public string Name { get; }
    public List<Node> Children { get; } = new List<Node>();
    public bool Visited { get; set; }

    public Node(string Name)
    {
        this.Name = Name;
    }

    public Node(string name, IEnumerable<Node> children)
    {
        Name = name;

        foreach (var node in children)
        {
            AddChild(node);
        }
    }

    public void AddChild(Node node)
    {
        Children.Add(node);
    }
}

The implemented algorithm.

public class PathAlgorithm
{
    Node Start { get; }
    Node End { get; }

    public PathAlgorithm(Node start, Node end)
    {
        Start = start ?? throw new ArgumentNullException(nameof(start));
        End = end ?? throw new ArgumentNullException(nameof(end));
    }

    public bool HasPath(out int length)
    {
        bool hasPath;
        (hasPath, length) = BreadthFirstSearch(Start);

        return hasPath;
    }
        
    public (bool, int) BreadthFirstSearch(Node root)
    {
        if (root == null)
        {
            return (false, 0);
        }

        Queue<(Node, int)> searchQueue = new Queue<(Node, int)>();
        root.Visited = true;
        searchQueue.Enqueue((root, 0));
            
        while (searchQueue.Any())
        {
            (Node node, int length) = searchQueue.Dequeue();
            if (node == End)
            {
                return (true, length);
            }

            EnqueueNonVisitedChildrenNodes(searchQueue, (node, length));
        }

        return (false, 0);

        void EnqueueNonVisitedChildrenNodes(Queue<(Node, int)> queue, (Node node, int length) foo)
        {
            foreach (var n in foo.node.Children)
            {
                if (!n.Visited)
                {
                    n.Visited = true;
                    searchQueue.Enqueue((n, foo.length + 1));
                }
            }
        }
    }
}

Answer 1

The code you have there may accomplish the task you have in mind for it, but it's not useful for a "real world" usecase.
That's because usually you'd want to be able to run an algorithm like this multiple times on the same graph, maybe even concurrently.

The problem that's posing itself here is that Node mixes two concerns: Representing the graph and traversing it.

Storing the Visited state inside the Node is really useful, but it's also quite limiting. As such you could greatly benefit from storing visited Nodes as a Set instead to separate traversal from representation.

---

There's also some minor optimization possibilities:

• Replace the foreach in the Node constructor with AddRange

• Once .NET 5 releases (or you switch to .NET Core) You can slightly simplify the while loop in the BFS itself using searchQueue.TryDequeue(var (node, length)).

• Storing visited nodes in a HashSet (or similar) enables reformulating EnqueueNotVisitedChildrenNodes as:

  foreach (var child in node.Children.ExceptWith(visited))
  {
      searchQueue.Enqueue((child, length + 1));
  }
  

  This reformulation of course then messes with the visited state of nodes you didn't actually visit yet, since you set Visited when you enqueue the node, not when you actually visit it.

  This flagging visited when enqueueing utterly breaks as soon as you start working with "weighted graphs", where the smallest number of edges may not be the optimal path (like the following)

  (A) -(1)- (B) -(1)- (C)
    \                 /
     -------(5)-------
  

  Going from (A) to (C) via (B) is cheaper than the direct route here :), if your real target was a node (D) that's only connected to (C), your current code would route you through (C) because the shorter route through (B) would be ignored since (C) already counts as visited when you dequeue (B).

---

Overall this code is really nice and clean, but it lacks general applicability (which is not a bad thing in itself).