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:
- How can I refactor this code in general to adhere to more SOLID principles?
- 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)?
- How can I avoid the duplicated if statements when doing the console outputs?
- 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;
}
}
