8
\$\begingroup\$

Original question: Breadth First Search not SOLID enough

Here is my first attempt at refactoring. Instead of using a Tuple, I used a STRUCT and this made it more readable. I also extracted printing paths and finding paths into interfaces so someone could print their own messages or implement there own path finding algorithm. The graph class has a corresponding interface as well.

I am still not sure if I need all the path finding methods. Some of them are just one-liners, so I wonder if they are necessary. I also want to pass a file name as an args parameter into main, but I am not sure how to get that to my CreateGraph method. Also, IGraph graph = new Graph().CreateGraph(); seems a bit weird. Is this normal? I am also curious if there is a way to better pass in messages to my PrintXXXPath... methods, so I don't have to have so many of them.

Node class

public 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>();
    }

    public void AddEdge(Node targetNode, double weight)
    {
        Edges.Add(new Edge(targetNode,weight));
    }
}

Edge class

public 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

public class QueueItem
{
    public Node Node { get; private set; }
    public List<Edge> VisitedEdges { get; private set; }

    public QueueItem(Node node, List<Edge> visitedEdges)
    {
        Node = node;
        VisitedEdges = visitedEdges;
    }
}

Path struct

public struct Path
{
    public readonly Node StartNode;
    public readonly Node EndNode;
    public readonly string PathRepresentation;
    public readonly int VisitedCount;
    public readonly double TotalWeight;

    public Path(Node startNode, Node endNode, string pathRepresentation, int visitedCount, double totalWeight)
    {
        StartNode = startNode;
        EndNode = endNode;
        PathRepresentation = pathRepresentation;
        VisitedCount = visitedCount;
        TotalWeight = totalWeight;

    }
}

IGraph interface

public interface IGraph
{
    void AddNode(string name);
    Node GetNode(string name);
    IGraph CreateGraph();
}

Graph class

public class Graph : IGraph
{
    public Dictionary<string, Node> Nodes { get; private set; }

    public Graph()
    {
        Nodes = new Dictionary<string, Node>();
    }

    public void AddNode(string name)
    {
        Nodes.Add(name, new Node(name));
    }

    public Node GetNode(string name)
    {
        if (Nodes.ContainsKey(name))
            return Nodes[name];

        return null;
    }

    public IGraph CreateGraph()
    {
        const int START_NODE_INDEX = 0;
        const int END_NODE_INDEX = 1;
        const int EDGE_WEIGHT_INDEX = 2;

        var nodes = File.ReadAllText("graph.csv").Split(',');

        IGraph graph = new Graph();

        foreach (var n in nodes)
        {
            var node = n.Trim();

            if (graph.GetNode(node[START_NODE_INDEX].ToString()) == null)
            {
                graph.AddNode(node[START_NODE_INDEX].ToString());
            }

            if (graph.GetNode(node[END_NODE_INDEX].ToString()) == null)
            {
                graph.AddNode(node[END_NODE_INDEX].ToString());
            }

            graph.GetNode(node[START_NODE_INDEX].ToString())
                 .AddEdge(graph.GetNode(node[END_NODE_INDEX].ToString()), Convert.ToInt32(node[EDGE_WEIGHT_INDEX].ToString()));

        }

        return graph;
    }
}

IPathFinder interface

public interface IPathFinder
{
    Path GetShortestPath(Node startNode, Node endNode);

    List<Path> GetPathsWithMinWeight(Node startNode, Node endNode, double minWeight, bool inclusive);

    List<Path> GetPathsWithMaxWeight(Node startNode, Node endNode, double maxWeight, bool inclusive);

    List<Path> GetPathsWithExactWeight(Node startNode, Node endNode, double weight);

    List<Path> GetAllPaths(Node startNode, Node endNode);

    List<Path> GetPathsWithMinStops(Node startNode, Node endNode, int minStops, bool inclusive);

    List<Path> GetPathsWithMaxStops(Node startNode, Node endNode, int maxStops, bool inclusive);

    List<Path> GetPathsWithExactStops(Node startNode, Node endNode, int stops);

    Path GetPath(Node startNode, Node endNode, IEnumerable<Edge> visitedEdges);

    string GetPathRepresentation(Node startNode, Node endNode, IEnumerable<Edge> visiteEdges);
}

PathFinder class

public class PathFinder : IPathFinder
{
    public string GetPathRepresentation(Node startNode, Node endNode, IEnumerable<Edge> visiteEdges)
    {
        var pathRepresentation = new StringBuilder();

        pathRepresentation.AppendFormat("{0}->", startNode.Name);

        foreach (var visitedEdge in visiteEdges)
        {
            if (visitedEdge.TargetNode == endNode)
            {
                pathRepresentation.Append(endNode.Name);
            }
            else
            {
                pathRepresentation.AppendFormat("{0}->", visitedEdge.TargetNode.Name);
            }
        }

        return pathRepresentation.ToString();
    }

    public Path GetPath(Node startNode, Node endNode, IEnumerable<Edge> visitedEdges)
    {
        var visitedPaths = visitedEdges as IList<Edge> ?? visitedEdges.ToList();

        string pathRepresentation = GetPathRepresentation(startNode, endNode, visitedPaths);

        double totalWeight = visitedPaths.Aggregate<Edge, double>(0,
                            (current, visitedEdge) => current + visitedEdge.Weight);

        return new Path(startNode, endNode, pathRepresentation, visitedPaths.Count(), totalWeight);
    }

    public List<Path> GetAllPaths(Node startNode, Node endNode)
    {
        var paths = new List<Path>();
        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.VisitedEdges.Contains(edge))
                {
                    var visitedEdges = new List<Edge>(currentItem.VisitedEdges) { edge };
                    if (edge.TargetNode == endNode)
                    {
                        var path = GetPath(startNode, endNode, visitedEdges);

                        paths.Add(path);
                    }
                    else
                    {
                        queue.Enqueue(new QueueItem(edge.TargetNode, visitedEdges));
                    }
                }
            }
        }
        return paths;
    }

    public Path GetShortestPath(Node startNode, Node endNode)
    {
        List<Path> paths = GetAllPaths(startNode, endNode);
        var shortestPath = new Path();
        double shortestPathWeight = double.PositiveInfinity;

        if (paths.Count > 0)
        {
            foreach (var path in paths)
            {
                if (path.TotalWeight < shortestPathWeight)
                {
                    if (path.TotalWeight < shortestPathWeight)
                    {
                        shortestPathWeight = path.TotalWeight;

                        shortestPath = new Path(startNode, endNode, path.PathRepresentation, path.VisitedCount,
                            path.TotalWeight);
                    }
                }
            }
        }

        return shortestPath;
    }

    public List<Path> GetPathsWithMinWeight(Node startNode, Node endNode, double minWeight, bool inclusive)
    {
        if (inclusive)
            return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight >= minWeight).ToList();

        return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight > minWeight).ToList();
    }

    public List<Path> GetPathsWithMaxWeight(Node startNode, Node endNode, double maxWeight, bool inclusive)
    {
        if(inclusive)
            return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight <= maxWeight).ToList();

        return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight < maxWeight).ToList();
    }

    public List<Path> GetPathsWithExactWeight(Node startNode, Node endNode, double weight)
    {
        return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight.Equals(weight)).ToList();
    }

    public List<Path> GetPathsWithMinStops(Node startNode, Node endNode, int minStops, bool inclusive)
    {
        if(inclusive)
            return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount >= minStops).ToList();

        return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount > minStops).ToList();
    }

    public List<Path> GetPathsWithMaxStops(Node startNode, Node endNode, int maxStops, bool inclusive)
    {
        if(inclusive)
            return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount <= maxStops).ToList();

        return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount < maxStops).ToList();
    }

    public List<Path> GetPathsWithExactStops(Node startNode, Node endNode, int stops)
    {
        return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount == stops).ToList();
    }

    public List<Path> GetAllPaths2(Node startNode, Node endNode)
    {
        var paths = new List<Path>();
        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.VisitedEdges.Contains(edge))
                {
                    var visitedEdges = new List<Edge>(currentItem.VisitedEdges) { edge };
                    if (edge.TargetNode == endNode)
                    {
                        var path = GetPath(startNode, endNode, visitedEdges);

                        paths.Add(path);
                    }
                    else
                    {
                        queue.Enqueue(new QueueItem(edge.TargetNode, visitedEdges));
                    }
                }
            }
        }
        return paths;
    }
}

IPathPrinter interface

public interface IPathPrinter
{
    void PrintShortestPath(Path path);
    void PrintPathsWithMaxWeight(List<Path> paths, Node startNode, Node endNode, double maxWeight, bool inclusive);
    void PrintPathDistance(List<Path> paths);
    void PrintPathsWithMaxStops(List<Path> paths, Node startNode, Node endNode, int maxStops, bool inclusive);
    void PrintPathsWithExactStops(List<Path> paths, Node startNode, Node endNode, int maxStops);
}

PathPrinter class

public class PathPrinter : IPathPrinter
{
    public void PrintShortestPath(Path path)
    {
        Console.WriteLine("The shortest path from '{0}' to '{1} is '{2}' with a distance of {3}",
            path.StartNode.Name, path.EndNode.Name, path.PathRepresentation, path.TotalWeight);
    }

    public void PrintPathsWithMaxWeight(List<Path> paths, Node startNode, Node endNode, double maxWeight, bool inclusive)
    {
        if (inclusive)
        {
            Console.WriteLine(
                "The number of trips from '{0}' to '{1}' with a distance of less than or equal to {2} is {3}:",
                startNode.Name, endNode.Name, maxWeight, paths.Count);
        }
        else
        {
            Console.WriteLine(
                "The number of trips from '{0}' to '{1}' with a distance of less than {2} is {3}:",
                startNode.Name, endNode.Name, maxWeight, paths.Count);
        }

        foreach (var path in paths)
        {
            Console.WriteLine("{0} with a distance of {1}", path.PathRepresentation, path.TotalWeight);
        }
    }

    public void PrintPathsWithMaxStops(List<Path> paths, Node startNode, Node endNode, int maxStops, bool inclusive)
    {
        if (inclusive)
        {
            Console.WriteLine("The number of trips from '{0}' to '{1}' with a maximum of {2} stops is {3}:", startNode.Name, endNode.Name, maxStops, paths.Count);
        }
        else
        {
            Console.WriteLine("The number of trips from '{0}' to '{1}' with a maximum of less than {2} stops is {3}:", startNode.Name, endNode.Name, maxStops, paths.Count);
        }


        PrintPaths(paths);
    }

    public void PrintPathsWithExactStops(List<Path> paths, Node startNode, Node endNode, int maxStops)
    {

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

        PrintPaths(paths);
    }

    public void PrintPathDistance(List<Path> paths)
    {
        foreach (var path in paths)
        {
            Console.WriteLine("The distance of the route '{0}' is {1}", path.PathRepresentation, path.TotalWeight);
        }
    }

    private static void PrintPaths(IEnumerable<Path> paths)
    {
        foreach (var path in paths)
        {
            Console.WriteLine(path.PathRepresentation);
        }
    }
}

Program class

public class Program
{
    public static void Main(string[] args)
    {
        IPathFinder pathFinder = new PathFinder();
        IPathPrinter pathPrinter = new PathPrinter();

        IGraph graph = new Graph().CreateGraph();

        var pathsAtoC = pathFinder.GetAllPaths(graph.GetNode("A"), graph.GetNode("C"));
        pathPrinter.PrintPathDistance(pathsAtoC.Where(x => x.PathRepresentation.Equals("A->B->C")).ToList());

        var pathsAtoD = pathFinder.GetAllPaths(graph.GetNode("A"), graph.GetNode("D"));

        pathPrinter.PrintPathDistance(pathsAtoD.Where(x => x.PathRepresentation.Equals("A->D")).ToList());

        pathPrinter.PrintPathDistance(pathsAtoC.Where(x => x.PathRepresentation.Equals("A->D->C")).ToList());

        pathPrinter.PrintPathDistance(pathsAtoD.Where(x => x.PathRepresentation.Equals("A->E->B->C->D")).ToList());

        var validPath = pathsAtoD.Any(x => x.PathRepresentation.Equals("A->E->D"));

        if(validPath)
            pathPrinter.PrintPathDistance(pathsAtoD.Where(x => x.PathRepresentation.Equals("A->E->D")).ToList());

        Console.WriteLine(Environment.NewLine);

        var path = pathFinder.GetShortestPath(graph.GetNode("A"), graph.GetNode("C"));
        pathPrinter.PrintShortestPath(path);

        path = pathFinder.GetShortestPath(graph.GetNode("C"), graph.GetNode("C"));
        pathPrinter.PrintShortestPath(path);

        Console.WriteLine(Environment.NewLine);

        var paths = pathFinder.GetPathsWithMaxStops(graph.GetNode("C"), graph.GetNode("C"),3,true);
        pathPrinter.PrintPathsWithMaxStops(paths,graph.GetNode("C"),graph.GetNode("C"),3,true);

        Console.WriteLine(Environment.NewLine);

        paths = pathFinder.GetPathsWithExactStops(graph.GetNode("A"), graph.GetNode("C"), 4);
        pathPrinter.PrintPathsWithExactStops(paths, graph.GetNode("A"), graph.GetNode("C"), 4);

        Console.WriteLine(Environment.NewLine);

        paths = pathFinder.GetPathsWithMaxWeight(graph.GetNode("C"), graph.GetNode("C"), 30, false);
        pathPrinter.PrintPathsWithMaxWeight(paths, graph.GetNode("C"), graph.GetNode("C"), 30,false);

        Console.ReadKey();
    } 
}
\$\endgroup\$
7
\$\begingroup\$

I'm a fan of developing to interfaces and language-provided immutability, so I've refactored your Node and Edge classes to that end:

INode interface:

public interface INode
{
    string Name { get; }

    IEnumerable<IEdge> Edges { get; }

    void AddEdge(INode targetNode, double weight);
}

IEdge interface:

public interface IEdge
{
    INode TargetNode { get; }

    double Weight { get; }
}

IQueueItem interface:

public interface IQueueItem
{
    INode Node { get; }

    IEnumerable<IEdge> VisitedEdges { get; }
}

IGraph interface:

public interface IGraph
{
    void AddNode(string name);

    INode GetNode(string name);
}

Node class:

public sealed class Node : INode
{
    private readonly string name;

    private readonly ICollection<IEdge> edges = new List<IEdge>();

    private Node(string name)
    {
        this.name = name;
    }

    public string Name
    {
        get
        {
            return this.name;
        }
    }

    public IEnumerable<IEdge> Edges
    {
        get
        {
            return this.edges;
        }
    }

    public static INode Create(string name)
    {
        return new Node(name);
    }

    public void AddEdge(INode targetNode, double weight)
    {
        this.edges.Add(Edge.Create(targetNode, weight));
    }
}

Edge class:

public sealed class Edge : IEdge
{
    private readonly INode targetNode;

    private readonly double weight;

    private Edge(INode targetNode, double weight)
    {
        this.targetNode = targetNode;
        this.weight = weight;
    }

    public INode TargetNode
    {
        get
        {
            return this.targetNode;
        }
    }

    public double Weight
    {
        get
        {
            return this.weight;
        }
    }

    public static IEdge Create(INode targetNode, double weight)
    {
        return new Edge(targetNode, weight);
    }
}

QueueItem class:

public sealed class QueueItem : IQueueItem
{
    private readonly INode node;

    private readonly IEnumerable<IEdge> visitedEdges;

    private QueueItem(INode node, IEnumerable<IEdge> visitedEdges)
    {
        this.node = node;
        this.visitedEdges = visitedEdges;
    }

    public INode Node
    {
        get
        {
            return this.node;
        }
    }

    public IEnumerable<IEdge> VisitedEdges
    {
        get
        {
            return this.visitedEdges;
        }
    }

    public static IQueueItem Create(INode node, IEnumerable<IEdge> visitedEdges)
    {
        return new QueueItem(node, visitedEdges);
    }
}

Path struct:

public struct Path
{
    private readonly INode startNode;

    private readonly INode endNode;

    private readonly string pathRepresentation;

    private readonly int visitedCount;

    private readonly double totalWeight;

    public Path(INode startNode, INode endNode, string pathRepresentation, int visitedCount, double totalWeight)
    {
        this.startNode = startNode;
        this.endNode = endNode;
        this.pathRepresentation = pathRepresentation;
        this.visitedCount = visitedCount;
        this.totalWeight = totalWeight;
    }

    public INode StartNode
    {
        get
        {
            return this.startNode;
        }
    }

    public INode EndNode
    {
        get
        {
            return this.endNode;
        }
    }

    public string PathRepresentation
    {
        get
        {
            return this.pathRepresentation;
        }
    }

    public int VisitedCount
    {
        get
        {
            return this.visitedCount;
        }
    }

    public double TotalWeight
    {
        get
        {
            return this.totalWeight;
        }
    }
}

Graph class:

public sealed class Graph : IGraph
{
    private readonly IDictionary<string, INode> nodes = new Dictionary<string, INode>();

    private Graph()
    {
    }

    private enum NodeIndex
    {
        Start = 0,

        End = 1,

        Edge = 2
    }

    public IDictionary<string, INode> Nodes
    {
        get
        {
            return this.nodes;
        }
    }

    public static IGraph Create(IEnumerable<string> graphNodes)
    {
        IGraph graph = new Graph();

        foreach (var node in graphNodes.Select(n => n.Trim()))
        {
            if (graph.GetNode(node[(int)NodeIndex.Start].ToString()) == null)
            {
                graph.AddNode(node[(int)NodeIndex.Start].ToString());
            }

            if (graph.GetNode(node[(int)NodeIndex.End].ToString()) == null)
            {
                graph.AddNode(node[(int)NodeIndex.End].ToString());
            }

            graph.GetNode(node[(int)NodeIndex.Start].ToString()).AddEdge(
                graph.GetNode(node[(int)NodeIndex.End].ToString()),
                Convert.ToInt32(node[(int)NodeIndex.Edge].ToString()));
        }

        return graph;
    }

    public void AddNode(string name)
    {
        this.nodes.Add(name, Node.Create(name));
    }

    public INode GetNode(string name)
    {
        return this.nodes.ContainsKey(name) ? this.Nodes[name] : null;
    }
}

PathFinder class (I removed IPathFinder interface as the class has no state):

public static class PathFinder
{
    public static string GetPathRepresentation(INode startNode, INode endNode, IEnumerable<IEdge> visiteEdges)
    {
        var pathRepresentation = new StringBuilder();

        pathRepresentation.AppendFormat("{0}->", startNode.Name);
        foreach (var visitedEdge in visiteEdges)
        {
            if (visitedEdge.TargetNode == endNode)
            {
                pathRepresentation.Append(endNode.Name);
            }
            else
            {
                pathRepresentation.AppendFormat("{0}->", visitedEdge.TargetNode.Name);
            }
        }

        return pathRepresentation.ToString();
    }

    public static Path GetPath(INode startNode, INode endNode, IEnumerable<IEdge> visitedEdges)
    {
        var visitedPaths = visitedEdges as IList<IEdge> ?? visitedEdges.ToList();
        var pathRepresentation = GetPathRepresentation(startNode, endNode, visitedPaths);
        var totalWeight = visitedPaths.Aggregate(
            0.0D,
            (current, visitedEdge) => current + visitedEdge.Weight);

        return new Path(startNode, endNode, pathRepresentation, visitedPaths.Count(), totalWeight);
    }

    public static IEnumerable<Path> GetAllPaths(INode startNode, INode endNode)
    {
        var paths = new List<Path>();
        var queue = new Queue<IQueueItem>();

        queue.Enqueue(QueueItem.Create(startNode, new List<IEdge>()));
        while (queue.Count > 0)
        {
            var currentItem = queue.Dequeue();

            foreach (var edge in currentItem.Node.Edges)
            {
                if (currentItem.VisitedEdges.Contains(edge))
                {
                    continue;
                }

                var visitedEdges = new List<IEdge>(currentItem.VisitedEdges) { edge };

                if (edge.TargetNode == endNode)
                {
                    var path = GetPath(startNode, endNode, visitedEdges);

                    paths.Add(path);
                }
                else
                {
                    queue.Enqueue(QueueItem.Create(edge.TargetNode, visitedEdges));
                }
            }
        }

        return paths;
    }

    public static Path GetShortestPath(INode startNode, INode endNode)
    {
        var paths = GetAllPaths(startNode, endNode);
        var shortestPath = new Path();
        double[] shortestPathWeight = { double.PositiveInfinity };

        foreach (var path in paths.Where(path => path.TotalWeight < shortestPathWeight[0]).Where(path => path.TotalWeight < shortestPathWeight[0]))
        {
            shortestPathWeight[0] = path.TotalWeight;
            shortestPath = new Path(
                startNode,
                endNode,
                path.PathRepresentation,
                path.VisitedCount,
                path.TotalWeight);
        }

        return shortestPath;
    }

    public static IEnumerable<Path> GetPathsWithMinWeight(INode startNode, INode endNode, double minWeight, bool inclusive)
    {
        return inclusive
            ? GetAllPaths(startNode, endNode).Where(path => path.TotalWeight >= minWeight)
            : GetAllPaths(startNode, endNode).Where(path => path.TotalWeight > minWeight);
    }

    public static IEnumerable<Path> GetPathsWithMaxWeight(INode startNode, INode endNode, double maxWeight, bool inclusive)
    {
        return inclusive
            ? GetAllPaths(startNode, endNode).Where(path => path.TotalWeight <= maxWeight)
            : GetAllPaths(startNode, endNode).Where(path => path.TotalWeight < maxWeight);
    }

    public static IEnumerable<Path> GetPathsWithExactWeight(INode startNode, INode endNode, double weight)
    {
        return GetAllPaths(startNode, endNode).Where(path => path.TotalWeight.Equals(weight));
    }

    public static IEnumerable<Path> GetPathsWithMinStops(INode startNode, INode endNode, int minStops, bool inclusive)
    {
        return inclusive
            ? GetAllPaths(startNode, endNode).Where(path => path.VisitedCount >= minStops)
            : GetAllPaths(startNode, endNode).Where(path => path.VisitedCount > minStops);
    }

    public static IEnumerable<Path> GetPathsWithMaxStops(INode startNode, INode endNode, int maxStops, bool inclusive)
    {
        return inclusive
            ? GetAllPaths(startNode, endNode).Where(path => path.VisitedCount <= maxStops)
            : GetAllPaths(startNode, endNode).Where(path => path.VisitedCount < maxStops);
    }

    public static IEnumerable<Path> GetPathsWithExactStops(INode startNode, INode endNode, int stops)
    {
        return GetAllPaths(startNode, endNode).Where(path => path.VisitedCount == stops);
    }

    public static IEnumerable<Path> GetAllPaths2(INode startNode, INode endNode)
    {
        var paths = new List<Path>();
        var queue = new Queue<IQueueItem>();

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

        while (queue.Count > 0)
        {
            var currentItem = queue.Dequeue();

            foreach (var edge in currentItem.Node.Edges)
            {
                if (currentItem.VisitedEdges.Contains(edge))
                {
                    continue;
                }

                var visitedEdges = new List<IEdge>(currentItem.VisitedEdges) { edge };

                if (edge.TargetNode == endNode)
                {
                    var path = GetPath(startNode, endNode, visitedEdges);

                    paths.Add(path);
                }
                else
                {
                    queue.Enqueue(QueueItem.Create(edge.TargetNode, visitedEdges));
                }
            }
        }

        return paths;
    }
}

PathPrinter class (I removed IPathPrinter interface as the class has no state):

public static class PathPrinter
{
    public static void PrintShortestPath(Path path)
    {
        Console.WriteLine(
            "The shortest path from '{0}' to '{1} is '{2}' with a distance of {3}",
            path.StartNode.Name,
            path.EndNode.Name,
            path.PathRepresentation,
            path.TotalWeight);
    }

    public static void PrintPathsWithMaxWeight(IEnumerable<Path> paths, INode startNode, INode endNode, double maxWeight, bool inclusive)
    {
        Console.WriteLine(
            inclusive
                ? "The number of trips from '{0}' to '{1}' with a distance of less than or equal to {2} is {3}:"
                : "The number of trips from '{0}' to '{1}' with a distance of less than {2} is {3}:",
            startNode.Name,
            endNode.Name,
            maxWeight,
            paths.Count());
        foreach (var path in paths)
        {
            Console.WriteLine("{0} with a distance of {1}", path.PathRepresentation, path.TotalWeight);
        }
    }

    public static void PrintPathsWithMaxStops(IEnumerable<Path> paths, INode startNode, INode endNode, int maxStops, bool inclusive)
    {
        Console.WriteLine(
            inclusive
                ? "The number of trips from '{0}' to '{1}' with a maximum of {2} stops is {3}:"
                : "The number of trips from '{0}' to '{1}' with a maximum of less than {2} stops is {3}:",
            startNode.Name,
            endNode.Name,
            maxStops,
            paths.Count());
        PrintPaths(paths);
    }

    public static void PrintPathsWithExactStops(IEnumerable<Path> paths, INode startNode, INode endNode, int maxStops)
    {
        Console.WriteLine("The number of trips from '{0}' to '{1}' with exactly {2} stops is {3}:", startNode.Name, endNode.Name, maxStops, paths.Count());
        PrintPaths(paths);
    }

    public static void PrintPathDistance(IEnumerable<Path> paths)
    {
        foreach (var path in paths)
        {
            Console.WriteLine("The distance of the route '{0}' is {1}", path.PathRepresentation, path.TotalWeight);
        }
    }

    private static void PrintPaths(IEnumerable<Path> paths)
    {
        foreach (var path in paths)
        {
            Console.WriteLine(path.PathRepresentation);
        }
    }
}

Program class:

internal static class Program
{
    private static void Main()
    {
        var graph = Graph.Create(File.ReadAllText("graph.csv").Split(','));
        var pathsAtoC = PathFinder.GetAllPaths(graph.GetNode("A"), graph.GetNode("C"));

        PathPrinter.PrintPathDistance(pathsAtoC.Where(thePath => thePath.PathRepresentation.Equals("A->B->C")).ToList());

        var pathsAtoD = PathFinder.GetAllPaths(graph.GetNode("A"), graph.GetNode("D"));

        PathPrinter.PrintPathDistance(pathsAtoD.Where(thePath => thePath.PathRepresentation.Equals("A->D")).ToList());
        PathPrinter.PrintPathDistance(pathsAtoC.Where(thePath => thePath.PathRepresentation.Equals("A->D->C")).ToList());
        PathPrinter.PrintPathDistance(pathsAtoD.Where(thePath => thePath.PathRepresentation.Equals("A->E->B->C->D")).ToList());

        var validPath = pathsAtoD.Any(thePath => thePath.PathRepresentation.Equals("A->E->D"));

        if (validPath)
        {
            PathPrinter.PrintPathDistance(pathsAtoD.Where(thePath => thePath.PathRepresentation.Equals("A->E->D")).ToList());
        }

        Console.WriteLine(Environment.NewLine);

        var path = PathFinder.GetShortestPath(graph.GetNode("A"), graph.GetNode("C"));

        PathPrinter.PrintShortestPath(path);
        path = PathFinder.GetShortestPath(graph.GetNode("C"), graph.GetNode("C"));
        PathPrinter.PrintShortestPath(path);
        Console.WriteLine(Environment.NewLine);

        var paths = PathFinder.GetPathsWithMaxStops(graph.GetNode("C"), graph.GetNode("C"), 3, true);

        PathPrinter.PrintPathsWithMaxStops(paths, graph.GetNode("C"), graph.GetNode("C"), 3, true);
        Console.WriteLine(Environment.NewLine);
        paths = PathFinder.GetPathsWithExactStops(graph.GetNode("A"), graph.GetNode("C"), 4);
        PathPrinter.PrintPathsWithExactStops(paths, graph.GetNode("A"), graph.GetNode("C"), 4);
        Console.WriteLine(Environment.NewLine);
        paths = PathFinder.GetPathsWithMaxWeight(graph.GetNode("C"), graph.GetNode("C"), 30, false);
        PathPrinter.PrintPathsWithMaxWeight(paths, graph.GetNode("C"), graph.GetNode("C"), 30, false);
        Console.ReadKey();
    }
}

Now, I'd say there's more to do. I would not have the Graph class load the file directly. It should be passed in a dependency, like a Stream or even just the string of read data from the method that calls Create(). It breaks Single Responsibility Principle to have it both read the nodes from a file and then parse them. EDIT: I just did this and put it in there.

The PathPrinter class would likely do better to have a parameter on each of the methods that's a TextWriter and you can call writer.WriteLine(...) as necessary. The caller (Program.Main()) can pass in Console.Out to see console output, but it can be exchanged for a file, network stream, etc.

EDIT here's how to have a TextWriter be used:

private static void Main()
{
    DoSomething(Console.Out); // Outputs to the console.
    DoSomething(TextWriter.Null); // Won't output anything.
}

private static void DoSomething(TextWriter writer)
{
    writer.WriteLine("Hello, World!");
    writer.WriteLine();
}
\$\endgroup\$
  • \$\begingroup\$ Great! I can't wait to see it. Would you also enlighten me as why you chose some data structures, such as ICollection instead of IList for example as well? \$\endgroup\$ – xaisoft Oct 7 '14 at 21:49
  • \$\begingroup\$ @xaisoft I'm just about ready. I chose ICollection as the implementation didn't need any functionality that's from any more specific interface. Rule of thumb is to code to the least-general interface you want to support. I'm working backward here, so I made the judgment call. \$\endgroup\$ – Jesse C. Slicer Oct 7 '14 at 21:54
  • \$\begingroup\$ Thanks for this so far. It is really great. I have a few questions: 1) Can you elaborate on developing to interfaces and language-provided immutability?, 2) What benefit does making the concrete classes sealed?, 3) If there is no state, does it make sense to have an interface?, 4) Also, by removing the interfaces, if I want to implement another way of path finding or path printing, don't I have to create new classes anyways?, 5) I am a bit confused on passing in a TextWriter to PathPrinter, can you possibly provide an example of how that works? \$\endgroup\$ – xaisoft Oct 8 '14 at 1:24
  • \$\begingroup\$ @xaisoft 1) yes. by developing to interfaces (INode vs. Node in the Edge class, for instance) - you decouple your interface from your implementation. Loose coupling is a hallmark of good OO design. Plug, it allows you to unit test your components by mocking out the dependent interfaces. \$\endgroup\$ – Jesse C. Slicer Oct 8 '14 at 2:04
  • 1
    \$\begingroup\$ Great. It makes sense now. Thanks for the link and detailed answer. \$\endgroup\$ – xaisoft Oct 9 '14 at 0:49

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.