7
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Please do not add, remove, or edit code in a question after you've received an answer. Please see the meta question: What you can and cannot do after receiving answers. \$\endgroup\$ – RubberDuck Oct 7 '14 at 19:58
  • \$\begingroup\$ @RubberDuck Ok, do I just make another question with my updated code? \$\endgroup\$ – xaisoft Oct 7 '14 at 20:00
  • 2
    \$\begingroup\$ As I was saying, yes you can do it. (If it is working), Recomended title "Breadth First Search not SOLID enough v2.0" Also you need to add a link to this question. \$\endgroup\$ – bhathiya-perera Oct 7 '14 at 20:05
  • \$\begingroup\$ @JaDogg - I saw your comment below, but your comment here As I was saying, yes you can do it... wasn't indicated below, so that is why I asked if I can post the revised version. \$\endgroup\$ – xaisoft Oct 7 '14 at 21:48
10
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Hi, sorry for the late response, I took some of your advice and I tried to make it better. You were right about the STRUCT over the Tuple. I did some other things as well. I posted the updated version. I am still unclear about the Builder or Factory pattern for Nodes (I created a Graph class to build the graph). Take a look and let me know if you see any other improvements? Thanks again. \$\endgroup\$ – xaisoft Oct 7 '14 at 19:44
  • 1
    \$\begingroup\$ @xaisoft you are not allowed to update questions after receving answers, because it will invalid the answer that was helpful to you originally. \$\endgroup\$ – bhathiya-perera Oct 7 '14 at 19:58
  • \$\begingroup\$ I took most of your ideas and put it to work in this second version here: codereview.stackexchange.com/q/65024/54489 \$\endgroup\$ – xaisoft Oct 7 '14 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.