Breadth and depth first search - part 1
Breadth and depth first search - part 3
As I've written in the previous post Breadth and depth first search - part 1 - I'll dive in more details and explain how to use the breadth and depth search methods. We'll execute a test case using the Romania map shown bellow, print the traveled paths in the screen, calculate the shortest path possible between two cities using Dijkstra's algorithm and print such a path in the screen.
To accomplish all the above let's start presenting the data structures used to represent the map in the C# programming language:
public class Node
{
public Node(string key, object data);
public Node(string key, object data, AdjacencyList neighbors);
public virtual object Data { get; set; }
public virtual string Key { get; }
public virtual AdjacencyList Neighbors { get; }
public virtual Node PathParent { get; set; }
protected internal virtual void AddDirected(EdgeToNeighbor e);
protected internal virtual void AddDirected(Node n);
protected internal virtual void AddDirected(Node n, int cost);
}
The Node class will be used to represent each city of the map.
Each city has its name represented by the key property and some other relevant data represented by the data property. Each city also has an adjacency list implemented by a specific class called AdjacencyList. This adjacency list represents the neighbors cities of a given city. For example, in the above map the neighbors cities of Bucharest are: Urziceni, Giurgiu, Pitesti and Fagaras.
Let's see the code of another class:
public class Graph
{
public Graph();
public Graph(NodeList nodes);
public virtual int Count { get; }
public virtual NodeList Nodes { get; }
public virtual void AddDirectedEdge(Node u, Node v);
public virtual void AddDirectedEdge(string uKey, string vKey);
public virtual void AddDirectedEdge(Node u, Node v, int cost);
public virtual void AddDirectedEdge(string uKey, string vKey, int cost);
public virtual void AddNode(Node n);
public virtual Node AddNode(string key, object data);
public virtual void AddUndirectedEdge(Node u, Node v);
public virtual void AddUndirectedEdge(string uKey, string vKey);
public virtual void AddUndirectedEdge(Node u, Node v, int cost);
public virtual void AddUndirectedEdge(string uKey, string vKey, int cost);
public virtual void Clear();
public virtual bool Contains(Node n);
public virtual bool Contains(string key);
}
The Graph class has a property that references a collection of nodes, that is, a collection of cities. This collection of cities is represented by the class NodeList that implements the so used interface IEnumerable.
As you can see the Graph class has methods that add directed or undirected edges to the graph. Each line that connects two cities (vertexes) in the Romania map is considered an edge.
The map above contains only undirected edges because they aren't defined just as one way paths between the cities. It's possible to go from Bucharest to Urziceni and then come back to Bucharest for example. So it's a two way path.
Above each line in the map is a value that represents the path cost between two cities. Let's consider this cost as the distance in miles between the cities. The path cost could be any other variable, for example, the time spent to traverse the distance (edge). The cost variable can vary according to the problem.
I implemented a class called Pathfinding as follows:
class Pathfinding
{
private static Graph graph = new Graph();
...
public static void BreadthFirstSearch(Node start, Node end)
{
...
}
public static void DepthFirstSearch(Node start, Node end)
{
...
} ... }
This class has additional properties and methods as ShortestPath and PrintPath. I won't spend time explaining its additional methods because they are already well explained in Part 5: From Trees to Graphs (article by Scott Mitchell). So, let's run a test case. For this we need to fill the graph with the Romania map data.
class Program
{
static void Main(string[] args)
{
Pathfinding pathFinding = new Pathfinding();
Node start, end;
// Vertexes
pathFinding.Graph.AddNode("Arad", null);
pathFinding.Graph.AddNode("Bucharest", null);
pathFinding.Graph.AddNode("Craiova", null);
pathFinding.Graph.AddNode("Dobreta", null);
pathFinding.Graph.AddNode("Eforie", null);
pathFinding.Graph.AddNode("Fagaras", null);
pathFinding.Graph.AddNode("Giurgiu", null);
pathFinding.Graph.AddNode("Hirsova", null);
pathFinding.Graph.AddNode("Iasi", null);
pathFinding.Graph.AddNode("Lugoj", null);
pathFinding.Graph.AddNode("Mehadia", null);
pathFinding.Graph.AddNode("Neamt", null);
pathFinding.Graph.AddNode("Oradea", null);
pathFinding.Graph.AddNode("Pitesti", null);
pathFinding.Graph.AddNode("Rimnicu Vilcea", null);
pathFinding.Graph.AddNode("Sibiu", null);
pathFinding.Graph.AddNode("Timisoara", null);
pathFinding.Graph.AddNode("Urziceni", null);
pathFinding.Graph.AddNode("Vaslui", null);
pathFinding.Graph.AddNode("Zerind", null);
// Edges
// Arad <-> Zerind
pathFinding.Graph.AddUndirectedEdge("Arad", "Zerind", 75);
// Arad <-> Timisoara
pathFinding.Graph.AddUndirectedEdge("Arad", "Timisoara", 118);
// Arad <-> Sibiu
pathFinding.Graph.AddUndirectedEdge("Arad", "Sibiu", 140);
// Bucharest <-> Urziceni
pathFinding.Graph.AddUndirectedEdge("Bucharest", "Urziceni", 85);
// Bucharest <-> Giurgiu
pathFinding.Graph.AddUndirectedEdge("Bucharest", "Giurgiu", 90);
// Bucharest <-> Pitesti
pathFinding.Graph.AddUndirectedEdge("Bucharest", "Pitesti", 101);
// Bucharest <-> Fagaras
pathFinding.Graph.AddUndirectedEdge("Bucharest", "Fagaras", 211);
// Craiova <-> Dobreta
pathFinding.Graph.AddUndirectedEdge("Craiova", "Dobreta", 120);
// Craiova <-> Pitesti
pathFinding.Graph.AddUndirectedEdge("Craiova", "Pitesti", 138);
// Craiova <-> Rimnicu Vilcea
pathFinding.Graph.AddUndirectedEdge("Craiova", "Rimnicu Vilcea", 146);
// Dobreta <-> Mehadia
pathFinding.Graph.AddUndirectedEdge("Dobreta", "Mehadia", 75);
// Eforie <-> Hirsova
pathFinding.Graph.AddUndirectedEdge("Eforie", "Hirsova", 86);
// Fagaras <-> Sibiu
pathFinding.Graph.AddUndirectedEdge("Fagaras", "Sibiu", 99);
// Hirsova <-> Urziceni
pathFinding.Graph.AddUndirectedEdge("Hirsova", "Urziceni", 98);
// Iasi <-> Neamt
pathFinding.Graph.AddUndirectedEdge("Iasi", "Neamt", 87);
// Iasi <-> Vaslui
pathFinding.Graph.AddUndirectedEdge("Iasi", "Vaslui", 92);
// Lugoj <-> Mehadia
pathFinding.Graph.AddUndirectedEdge("Lugoj", "Mehadia", 70);
// Lugoj <-> Timisoara
pathFinding.Graph.AddUndirectedEdge("Lugoj", "Timisoara", 111);
// Oradea <-> Zerind
pathFinding.Graph.AddUndirectedEdge("Oradea", "Zerind", 71);
// Oradea <-> Sibiu
pathFinding.Graph.AddUndirectedEdge("Oradea", "Sibiu", 151);
// Pitesti <-> Rimnicu Vilcea
pathFinding.Graph.AddUndirectedEdge("Pitesti", "Rimnicu Vilcea", 97);
// Rimnicu Vilcea <-> Sibiu
pathFinding.Graph.AddUndirectedEdge("Rimnicu Vilcea", "Sibiu", 80);
// Urziceni <-> Vaslui
pathFinding.Graph.AddUndirectedEdge("Urziceni", "Vaslui", 142);
start = pathFinding.Graph.Nodes["Oradea"];
end = pathFinding.Graph.Nodes["Neamt"];
Console.WriteLine("\nBreadth First Search algorithm");
Pathfinding.BreadthFirstSearch(start, end);
foreach(Node n in pathFinding.Graph.Nodes)
n.Data = null;
Console.WriteLine("\n\nDepth First Search algorithm");
Pathfinding.DepthFirstSearch(start, end);
Console.WriteLine("\n\nShortest path");
Pathfinding.ShortestPath(start, end);
pathFinding.Graph.Clear();
Console.ReadKey();
}
}
Firstly we create a new instance of the Pathfinding class and two instances of the Node class that will reference the start and end city respectively.
The pathfinding object has a graph property that we use to store the nodes, that is, the cities of the map. To accomplish this the method AddNode of the Graph class is used.
The key that represents the node is the name of the city in this case.
After adding the cities to the graph it's time to connect the cities by means of the edges between them. For each undirected edge of the map the fourth overload of the AddUndirectedEdge method is used. The method receives as arguments the names of the edge's vertexes and the path cost.
Supposing we want to go from Oradea to Neamt, we must set the start and end node appropriately and that is done when the start and end node are assigned the values already present in the graph.
After everything is set up we can run the the breadth and depth first search methods. To start I call the the method BreadthFirstSearch already presented in the previous post Breadth and depth first search - part 1. The method receives the start and end nodes as arguments and traverses the graph according to the breadth first search algorithm. During the traversal it prints the paths in the screen so that it's easier to visually debug the code.
We use the same graph data to run the depth first search method but to avoid a wrong behavior it's necessary to set the data property of each graph's node to null. It's because such property is used to store a value indicating if that node was already visited during the path traversal of the breadth first search method.
OK. Now that the graph data is prepared we can run the depth first search method invoking the DepthSearchMethod of the Pathfinding class. This method receives the start and end nodes as arguments and traverses the graph according to the depth first search algorithm. During the traversal it prints the paths in the screen so that it's easier to visually debug the code.
The last and so important method is the ShortestPath one. The shortest path problem can be calculated through different algorithms. In this case the algorithm used (Dijkstra's algorithm) is suitable because we don't have negative costs otherwise we should use other algorithms. The ShortestPath method of the Pathfinding class receives as arguments the start and end nodes and prints in the screen the total distance of such a path and the cities travelled.
See the screenshot of the output:
Note: if you want to see a C++ implementation of the breadth and depth first search, check the third part of this series: Breadth and depth first search - part 3.
Get the complete code (Microsoft Visual C# 2008 solution) and executable of this post at:
https://github.com/leniel/leniel.net/blob/master/Uploads/BreadthDepthFirstSearchCPlusPlus.zip
To try out the code you can use the free Microsoft Visual C# 2008 Express Edition that you can get at: http://www.microsoft.com/express/vcsharp
