How to replace inner Foreach loops with a Recursive method

Question

I'm a bit stuck on creating a method that is generic that can loop through a directed graph to get all possible routes based on max number of depth, for example:

All routes from A with a maximum of 4 hops returns the following concatenated routes:

ABCDC  
ABCDE  
ABCEB  
ADCDC  
ADCDE  
ADCEB  
ADEBC  
AEBCD  
AEBCE

The routes data is the following Json values:

"Routes": [
    {
      "From": "A",
      "To": "B",
      "Distance": 5
    },
    {
      "From": "A",
      "To": "D",
      "Distance": 5
    },
    {
      "From": "A",
      "To": "E",
      "Distance": 7
    },
    {
      "From": "B",
      "To": "C",
      "Distance": 4
    },
    {
      "From": "C",
      "To": "D",
      "Distance": 8
    },
    {
      "From": "C",
      "To": "E",
      "Distance": 2
    },
    {
      "From": "D",
      "To": "C",
      "Distance": 8
    },
    {
      "From": "D",
      "To": "E",
      "Distance": 6
    },
    {
      "From": "E",
      "To": "B",
      "Distance": 3
    }
]

And my inner loops, fixed four times is the following, where start would be "A", end would be "C" and the int stops value should determine the amount of recursion, instead of the hard coded loops. Any assistance or guidance in the right direction would be greatly apreciated.

public void GetRoutes(string start, string end, int stops)
{
    var tempRoutes = graph.Routes;

    foreach(var route in tempRoutes.Where(x => x.From == start))
    {
        foreach(var innerRoute in tempRoutes.Where(x => x.From == route.To))
        {
            foreach(var innerRoute2 in tempRoutes.Where(x => x.From == innerRoute.To))
            {
                foreach(var innerRoute3 in tempRoutes.Where(x => x.From == innerRoute2.To))
                {
                    totalPath = start + route.To + innerRoute.To + innerRoute2.To + innerRoute3.To;

                    PathCounter.Add(totalPath, totalPath.Length);
                }
            }
        }
    }
}

Answer 1

Try the following solution:

The following class models a link between two nodes in the graph:

public class NodeLink
{
    public string From { get; set; }
    public string To { get; set; }
}

The following class can search the graph recursively for routes:

public class RouteFinder
{
    public IEnumerable<string> FindRoutes(NodeLink[] node_links, string start, string end, int max_length)
    {
        if (max_length == 0)
            yield break;

        if (start == end)
        {
            yield return start;
            yield break;
        }

        if (max_length == 1)
        {
            yield break;
        }

        foreach (var route in node_links.Where(x => x.From == start))
        {
            IEnumerable<string> sub_routes = FindRoutes(node_links, route.To, end, max_length - 1);

            foreach (string sub_route in sub_routes)
            {
                yield return start + sub_route;
            }
        }
    }
}

And you can use it like this:

var node_links = new List<NodeLink>
{
    new NodeLink {From = "A", To = "B"},
    new NodeLink {From = "A", To = "C"},
    new NodeLink {From = "C", To = "D"},
    new NodeLink {From = "C", To = "E"},
    new NodeLink {From = "E", To = "F"},
    new NodeLink {From = "B", To = "F"}
};

RouteFinder finder = new RouteFinder();

foreach (string path in finder.FindRoutes(node_links.ToArray(), "A", "F", 4))
{
    Console.WriteLine(path);
}

This is the output that I get:

ABF
ACEF