Breadth First Search not SOLID enough

Question

The following code has a modified version of the Breadth First Search algorithm. It not only visits the nodes, but keeps track of the paths, so I can output various messages later. I would like to make it more reusable and cut down on some of the duplicated code. There appears to be a lot of noise in it. Here are some questions:

1. How can I refactor this code in general to adhere to more SOLID principles?
2. How can I make it so that I don't have to have a method for everything I want to do with the path (Find the shortest, find the paths with number of stops, find all paths, etc)?
3. How can I avoid the duplicated if statements when doing the console outputs?
4. Any other ideas are more than welcome?

Node class

internal class Node
{
    public string Name { get; private set; }
    public List<Edge> Edges { get; private set; }

    public Node(string name)
    {
        Name = name;
        Edges = new List<Edge>();
    }
}

Edge class

internal class Edge
{

    public Node TargetNode { get; private set; }
    public double Weight { get; private set; }

    public Edge(Node targetNode, double weight)
    {
        TargetNode = targetNode;
        Weight = weight;
    }
}

QueueItem class

internal class QueueItem
{

    public Node Node { get; private set; }
    public List<Edge> Visited { get; private set; }

    public QueueItem(Node node, List<Edge> visited)
    {
        Node = node;
        Visited = visited;
    }
}

Program class

class Program
{
    static void Main(string[] args)
    {

        var a = new Node("A");
        var b = new Node("B");
        var c = new Node("C");
        var d = new Node("D");
        var e = new Node("E");

        a.Edges.Add(new Edge(b, 5));
        a.Edges.Add(new Edge(e, 7));
        a.Edges.Add(new Edge(d, 5));
        b.Edges.Add(new Edge(c, 4));
        c.Edges.Add(new Edge(e, 2));
        c.Edges.Add(new Edge(d, 8));
        d.Edges.Add(new Edge(c, 8));
        d.Edges.Add(new Edge(e, 6));
        e.Edges.Add(new Edge(b, 3));

        FindAllPaths(a,c);

        FindAllPaths(a,d);

        FindShortestPath(a, c);

        FindShortestPath(b,b);

        FindPathsWithStops(c,c,0,3);

        FindPathsWithStops(a,c,4,4);

        FindPathsWithDistances(c,c,30);


        Console.ReadKey();
    }

    private static void FindPathsWithDistances(Node startNode, Node endNode, int maxWeight)
    {
        var paths = new List<Tuple<string, int, double>>();

        var queue = new Queue<QueueItem>();

        queue.Enqueue(new QueueItem(startNode, new List<Edge>()));

        GetAllPaths(startNode, endNode, queue, paths);


        var foundPaths = paths.Where(path => path.Item3 < maxWeight).ToList();

        Console.WriteLine("The number of trips from '{0}' to '{1}' with a distance of less than {2} is {3}", startNode.Name, endNode.Name, maxWeight, foundPaths.Count);


        foreach (var foundPath in foundPaths)
        {
            Console.WriteLine(foundPath.Item1);
        }

    }

    private static void FindShortestPath(Node startNode, Node endNode)
    {
        var paths = new List<Tuple<string, int,double>>();
        Tuple<string, int, double> shortestPath = null;
        double shortestPathWeight = double.PositiveInfinity;


        var queue = new Queue<QueueItem>();

        queue.Enqueue(new QueueItem(startNode, new List<Edge>()));

        GetAllPaths(startNode, endNode, queue, paths);

        if (paths.Count > 0)
        {
            foreach (var path in paths)
            {

                if (path.Item3 < shortestPathWeight)
                {
                    shortestPathWeight = path.Item3;
                    shortestPath = path;
                }
            }

            Console.WriteLine("The shortest path from {0} to {1} is {2} with a distance of {3}", startNode.Name,
                endNode.Name, shortestPath.Item1, shortestPath.Item3);
        }
    }

    public static void FindAllPaths(Node startNode, Node endNode)
    {
        var queue = new Queue<QueueItem>();

        queue.Enqueue(new QueueItem(startNode, new List<Edge>()));

        while (queue.Count > 0)
        {
            var currentItem = queue.Dequeue();
            foreach (var edge in currentItem.Node.Edges)
            {
                if (!currentItem.Visited.Contains(edge))
                {
                    var visited = new List<Edge>(currentItem.Visited) {edge};
                    if (edge.TargetNode == endNode)
                    {
                        double totalWeight = visited.Aggregate<Edge, double>(0,
                            (current, visitedEdge) => current + visitedEdge.Weight);
                        var path = GetPath(startNode, endNode, visited);

                        Console.WriteLine("The distance of the route {0} is {1}",path, totalWeight);

                    }
                    else
                    {
                        queue.Enqueue(new QueueItem(edge.TargetNode, visited));
                    }
                }
            }
        }
    }

    private static void FindPathsWithStops(Node startNode, Node endNode, int minStops, int maxStops)
    {
        var paths = new List<Tuple<string, int, double>>();
        var foundPaths = new List<Tuple<string, int, double>>();

        var queue = new Queue<QueueItem>();

        queue.Enqueue(new QueueItem(startNode, new List<Edge>()));

        GetAllPaths(startNode, endNode, queue, paths);


        foreach (var path in paths)
        {

            if (path.Item2 >= minStops && path.Item2 <= maxStops)
            {
                if (minStops < maxStops)
                {
                    foundPaths.Add(path);

                }
                else if (minStops == maxStops)
                {
                    foundPaths.Add(path);

                }
            }
        }

        if (minStops < maxStops)
        {
            Console.WriteLine("The number of trips from '{0}' to '{1}' with a maximum of {2} stops is {3}", startNode.Name, endNode.Name, maxStops, foundPaths.Count);

        }
        else if (minStops == maxStops)
        {

            Console.WriteLine("The number of trips from '{0}' to '{1}' with exactly {2} stops is {3}", startNode.Name, endNode.Name, maxStops, foundPaths.Count);
        }

        foreach (var foundPath in foundPaths)
        {
            Console.WriteLine(foundPath.Item1);
        }


    }

    private static void GetAllPaths(Node startNode, Node endNode, Queue<QueueItem> queue, List<Tuple<string, int, double>> paths)
    {
        while (queue.Count > 0)
        {
            var currentItem = queue.Dequeue();
            foreach (var edge in currentItem.Node.Edges)
            {
                if (!currentItem.Visited.Contains(edge))
                {
                    var visited = new List<Edge>(currentItem.Visited) {edge};
                    if (edge.TargetNode == endNode)
                    {
                        double totalWeight = visited.Aggregate<Edge, double>(0,
                            (current, visitedEdge) => current + visitedEdge.Weight);

                        var path = GetPath(startNode, endNode, visited);

                        paths.Add(new Tuple<string, int, double>(path.ToString(), visited.Count, totalWeight));
                    }
                    else
                    {
                        queue.Enqueue(new QueueItem(edge.TargetNode, visited));
                    }
                }
            }
        }
    }

    private static StringBuilder GetPath(Node startNode, Node endNode, IEnumerable<Edge> visited)
    {
        var path = new StringBuilder();
        path.AppendFormat("{0}->", startNode.Name);
        foreach (var visitedEdge in visited)
        {
            if (visitedEdge.TargetNode == endNode)
            {
                path.Append(endNode.Name);
            }
            else
            {
                path.AppendFormat("{0}->", visitedEdge.TargetNode.Name);
            }
        }
        return path;
    }
}

Answer 1

Cosmetics

At first glance, your post looks about right... until the Program class. But before I dig into the matter of the subject, I like to scratch the surface a bit.

Whitespace Consistency

Try to be more consistent with vertical whitespace. I think the Node and Program classes have it right:

internal class Node
{
    public string Name { get; private set; }

Naming

In general, you're using good, clear, readable names, and your naming conventions follow the official C# conventions, well done!

These ones stick out like a sore thumb though:

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");

Single-letter identifiers are never a good sign. At a glance I'd recommend making an array of nodes:

var nodes = new[] 
{ 
    new Node("A"), 
    new Node("B"), 
    new Node("C"),
    new Node("D"),
    new Node("E")
};

...but this isn't ideal, building the nodes shouldn't be done here.

This is wrong though:

private static void GetAllPaths(...)

A method that's called GetXxxxx should be returning Xxxxxx - I would expect GetAllPaths to return all paths. Being void, I can already say that calling this method will have side-effects on the values I give it.

Access Modifiers

I think internal is overkill here, these types aren't hurting anyone being public. What I don't get, is why only FindAllNodes is public while every single other member of the Program class is private.

---

SOLID

There's quite a lot of refactoring work to be done before this code can adhere to SOLID principles.

S. Single Responsibility Principle

The Main method in the Program class is doing way too many things:

• It builds a bunch of Node objects. Look into a builder or factory pattern to extract that functionality. This node-building code looks very frail and bug-prone, easy to get wrong and break.
• It contains the entire functionality, and makes all function calls. Because the methods being called have side-effects, the order in which these methods are called actually matters, and will produce different results if modified: this is called temporal coupling, and should be avoided.

Each private method (oh, and the public one, too) is also doing too many things - they all "do their own thing", but then they're also responsible for outputting to the console.

The first thing to do, is to change all these void methods for functions that return a result - and let the calling code decide how it wants to output that result.

All other SOLID principles are irrelevant at this point. Why? Because you don't write code to be SOLID; you write code, and as you clean it up and refactor, it becomes SOLID. While SRP is still taking a beating, none of the other principles are applicable.

You need to extract classes, and keep the Program class - and especially anything static, to a minimum. I would start with moving the node-building to some NodeBuilder class, and the should-all-be-private methods into some PathFinder class.

---

Tuples

I don't like Tuple. Maybe it's just me, but whenever I used it, it seemed like a missed opportunity at making a meaningful class, or more appropriately, an immutable struct.

This:

new Tuple<string, int, double>(path.ToString(), visited.Count, totalWeight)

Should be written like this:

Tuple.Create(path.ToString(), visited.Count, totalWeight)

But wouldn't it be clearer to have an immutable struct with PathRepresentation, VisitedCount and TotalWeight members, so that the rest of your code can call a path representation PathRepresentation instead of Item1?