While applying to a masters degree course I had to write an essay of no more than 500 words containing:

1. Personal appreciation about the evolution of my academic and professional activities up to now, avoiding the mere repetition of information already contained in my resume/CV.
2. Succinct description about the reasons I have to take a post-graduation course and what I expect from the course.
3. My expectations regarding the post-graduate course's influences in my future professional activities.
4. Specification of topics of interest, trying to correlate them with the research area of the program I'm applying to.

So far so good.

I have sent my enrollment docs to two of the best universities in the Rio de Janeiro state in Brazil, namely: UFRJ and PUC-Rio. Both of them have the highest assessment grades ( 7 ) conferred by CAPES. CAPES is the Brazilian government agency responsible for the evaluation of post-graduate courses.

I applied for two research areas: Software Engineering and Artificial Intelligence.

The essay I'm posting here (English and Portuguese versions) is from the UFRJ enrollment process (Software Engineering one) in which I applied to the Systems and Computer Engineering Program (site in Portuguese).

Now I hope to be called for at least one of these institutions. UFRJ process requires the applicant to take some tests: language test (English) and specifics test (the research area you're applying to) and both counts towards the acceptance.

---

Essay
I have been trying for almost three years now (since the graduation in Computer Engineering in Dec/2007) to apply at work and in my life the content I learned.

I succeeded in my last job at Chemtech because I had a good background provided by the Computer Engineering course. During the course, the disciplines that really caught my attention were those related to software. In this last job experience I could put into practice the theory seen at the university in my first level degree. I participated in several interesting software projects. I found this way the importance of theory in the activities of a computer professional.

My motivation to continue the studies through a masters course exists since I finished the first level degree. Meanwhile, between the graduation and the master's degree, I got a job. One of the reasons that made me quit that job was simply because I wanted to continue studying. I attended great part of the university only studying, which allowed me to have a good performance. Likewise, I wish to attend the masters in full time.

I want to take the post-graduate course to:

1 - Learn and get a deep understanding of the software area;
2 - Improve what I know;
3 - Grow as a computer professional;
4 - Get better opportunities in the job market.

My expectations for the course are the best. I know the the course and institution reputation and I know I can learn a lot. This is my main goal: to learn more and with quality. I am hungry for knowledge!

After the masters and possessing more advanced knowledge, I intend to pursue a career in software. The software engineering market is "young" compared to others and has shown steady growth in recent years. I believe that this market will provide excellent opportunities for the professional who has a post-graduate degree in the area. Money Magazine and Salary.com site rated the area of Software Engineering as the best area to work in 2006. This demonstrates and attests this area's power and influence in the global market. When I mention a career, I think of software companies or even in educational institutions as a teacher/university researcher. Any of these options I choose will satisfy me as a person and as professional. If I decide to go with a software company, I hope to contribute with a deeper view on the aspects involving software projects. Otherwise, I hope to be able to disseminate advanced knowledge in the area, teaching people. Brazil in particular has a deficit of engineers and particularly in the area of software engineering, which is a technology area that adds greater value and therefore contributes more effectively to the growth of our country.

My interest in the area of software engineering is focused on the development of software products. I love writing code, and consequently the programming languages, solve programming problems, study the software tools used in development and all the metrics involved and any possible subject that is related to software engineering.

See:

http://www.leniel.net
http://stackoverflow.com/users/114029/leniel-macaferi

---

Redação
Tenho buscado nestes quase 3 anos de formado em Engenharia de Computação aplicar no trabalho e nada vida o conteúdo que aprendi.

Tive êxito em minha última experiência profissional devido à base proporcionada pelo curso de Engenharia de Computação. Durante o curso, as matérias que mais chamaram minha atenção foram aquelas ligadas a software. Nesta última experiência profissional pude colocar em prática a teoria vista na faculdade. Participei em vários projetos de software interessantes. Constatei dessa maneira a importância da teoria nas atividades do profissional de computação.

Minha motivação para dar continuidade nos estudos através de um curso de mestrado existe desde que terminei o curso de graduação. Neste meio tempo, entre a graduação e o mestrado, consegui um emprego. Um dos motivos que me fez sair desse emprego foi justamente o de querer continuar os estudos. Cursei a maior parte da graduação somente estudando, o que me permitiu ter um bom aproveitamento. Da mesma forma, desejo cursar o mestrado com dedicação exclusiva.

Quero fazer o curso de pós-graduação para:

1 - Aprender e me aprofundar mais na área de software;
2 - Aprimorar o que sei;
3 - Crescer como profissional da área;
4 - Conseguir melhores oportunidades no mercado de trabalho.

Minhas expectativas quanto ao curso são as melhores. Conheço a reputação do curso e da instituição e sei que poderei aprender bastante. Este é o meu principal objetivo: aprender mais e com qualidade. Sou faminto por conhecimento!

Após o mestrado e de posse do conhecimento mais avançado, pretendo seguir carreira na área de software. O mercado de engenharia de software é "jovem" se comparado a outros e tem apresentado constante expansão nos últimos anos. Creio que este mercado proporcionará excelentes oportunidades para o profissional que possui uma pós-graduação na área. A revista Money Magazine e o site Salary.com, classificaram a área de Engenharia de Software como a melhor área para se trabalhar no ano de 2006. Isso mostra e atesta o poder e influência da área no mercado global.Quando menciono seguir carreira, penso em empresas de software ou até mesmo em instituições de ensino como professor/pesquisador universitário. Qualquer uma dessas opções que eu escolher me satisfará como pessoa e profissional. Caso eu siga em uma empresa de software, espero contribuir com uma visão mais ampla sobre os aspectos que envolvem os projetos de software. Caso contrário, espero ter a possibilidade de disseminar o conhecimento avançado na área, ajudando a formar pessoal capacitado. O Brasil em especial tem um déficit na área de engenharia e particularmente na engenharia de software, que é uma área tecnológica que agrega maior valor e portanto contribui de maneira mais eficaz para o crescimento do nosso país.

Meu interesse pela área de engenharia de software é centrado no desenvolvimento do produto de software. Amo escrever código e consequentemente as linguagens de programação, resolver problemas de programação, estudar ferramentas de software usadas no desenvolvimento e todas as métricas envolvidas e qualquer outro assunto possível que seja relativo à engenharia de software.

Veja:

http://www.leniel.net
http://stackoverflow.com/users/114029/leniel-macaferi

A* pathfinding search in C# - Part 1
A* pathfinding search in C# - Part 3

Code available at GitHub: https://github.com/leniel/AStar

To illustrate the path finding problem and how it can be solved using A* (A star) I decided to use the Romania map (with the same Cities I used in Breadth and depth first search series of posts). Now I modified it adding more connections between the cities so that we have more fun while debugging the code.

This time I decided to get the real values of latitude and longitude for the cities shown in the Romania map. To accomplish this I used this Google Spreadsheet that is a geocoder. It uses geo-google-docs to get geolocalization data for the address column.

This is the Map created using the data stored in the spreadsheet with the help of a Google Map:

You can pass your mouse over each pin to see the name of the city it represents in the map.

The following picture shows the fictitious connections (paths) between the cities and the cost to move from city to city.

To fill the Graph that represents the Romania map above I created a static private method called FillGraphWithEarthMap inside the AStar class that does the job of creating the Nodes and adding them to the graph (bellow I show a shortened version of such a method because it is a really big method given the fact that we have 20 cities and 41 connections (paths) between them:

/// <summary>
/// Fills a Graph with Romania map information.
/// The Graph contains Nodes that represents Cities of Romania.
/// Each Node has as its key the City name and its Latitude and Longitude associated information.
/// Nodes are vertexes in the Graph. Connections between Nodes are edges.
/// </summary>
/// <param name="graph">The Graph to be filled</param>
/// <param name="distanceType">The DistanceType (KM or Miles) between neighbor cities</param>
private static void FillGraphWithEarthMap(Graph graph, DistanceType distanceType)
{
    // 20 Vertexes in total
    Node arad = new Node("Arad", null, 46.1792414, 21.3150154); // Creating a Node...
    graph.AddNode(arad); // Adding the Node to the Graph...

    Node bucharest = new Node("Bucharest", null, 44.4479237, 26.097879);
    graph.AddNode(bucharest);

    Node craiova = new Node("Craiova", null, 44.3182085, 23.8016427);
    graph.AddNode(craiova);

    .
    .
    .

    // 41 Edges in total
    // Arad <-> Sibiu
    graph.AddUndirectedEdge(arad, sibiu, Haversine.Distance(arad, sibiu, distanceType));
    // Arad <-> Timisoara
    graph.AddUndirectedEdge(arad, timisoara, Haversine.Distance(arad, timisoara, distanceType));
    // Arad <-> Zerind
    graph.AddUndirectedEdge(arad, zerind, Haversine.Distance(arad, zerind, distanceType));

    .
    .
    .
}

The Vertexes
You must create a vertex/Node for each City of the map, passing to the Node’s class constructor the name of the City and its Latitude and Longitude coordinates. Add each Node to the Graph passed as a parameter to the method.

The Edges
You must create an undirected edge/path for each connection between two cities, passing to the constructor the first city, the second city and the cost to go from one city to the other. In this case the cost is calculated through the Haversine class discussed in A* pathfinding search in C# - Part 1.

To help debug the code I created two methods: DistanceBetweenNodes and ViewOtherPaths. Both methods are kept in the AStar class.

This is the DistanceBetweenNodes method:

/// <summary>
/// Prints on screen the distance from a city to its neighbors.
/// </summary>
/// <param name="graph">The Graph</param>
/// <param name="distanceType">The distance type: KM or Miles</param>
private static void DistanceBetweenNodes(Graph graph, DistanceType distanceType)
{
    // First we cast the Graph.Nodes which is a NodeList to type Node and then we order the list of Nodes by the Node Key
    // so that we get the list of cities in ascending order.
    foreach(Node n in graph.Nodes.Cast<Node>().OrderBy(n => n.Key))
    {
        // For each city neighbor we gets its information and print it on screen.
        foreach(EdgeToNeighbor etn in n.Neighbors)
        {
            Console.WriteLine("Distance from {0} to {1} is -> {2:#.##} {3}", n.Key, etn.Neighbor.Key, etn.Cost, distanceType);
        }
    }
}

Inside the FindPath method presented on A* pathfinding search in C# - Part 1, I call the ViewOtherPaths method (it’s commented out):

/// <summary>
/// This is the method responsible for finding the shortest path between a Start and Destination cities using the A*
/// search algorithm.
/// </summary>
/// <typeparam name="TNode">The Node type</typeparam>
/// <param name="start">Start city</param>
/// <param name="destination">Destination city</param>
/// <param name="distance">Function which tells us the exact distance between two neighbours.</param>
/// <param name="estimate">Function which tells us the estimated distance between the last node on a proposed path and the
/// destination node.</param>
/// <returns></returns>
static public Path<TNode> FindPath<TNode>(
    TNode start,
    TNode destination,
    Func<TNode, TNode, double> distance,
    Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
    var closed = new HashSet<TNode>();

    var queue = new PriorityQueue<double, Path<TNode>>();

    queue.Enqueue(0, new Path<TNode>(start));

    while(!queue.IsEmpty)
    {
        var path = queue.Dequeue();

        if(closed.Contains(path.LastStep))
            continue;

        if(path.LastStep.Equals(destination))
            return path;

        closed.Add(path.LastStep);

        foreach(TNode n in path.LastStep.Neighbours)
        {
            double d = distance(path.LastStep, n);

            var newPath = path.AddStep(n, d);

            queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
        }

        //ViewOtherPaths(queue, estimate);
    }

    return null;
}

This is the ViewOtherPaths method:

/// <summary>
/// This method can be used to view the other paths inside the PriorityQueue.
/// </summary>
/// <typeparam name="TNode">The Node type</typeparam>
/// <param name="queue">The priority queue</param>
/// <param name="estimate">Function which tells us the estimated distance between the last node on a proposed path and the
/// destination node.</param>
private static void ViewOtherPaths<TNode>(PriorityQueue<double, Path<TNode>> queue, Func<TNode, double> estimate)
{
    // The priority queue is composed of KeyValuePairs which has as key a double value (the TotalCost) and
    // has as Value a Queue which contains Paths.
    foreach(KeyValuePair<double, Queue<Path<TNode>>> kvp in queue)
    {
        // For each path in the Queue...
        foreach(Path<TNode> otherPath in kvp.Value)
        {
            // Reverse the Path so that we get the order of the cities in a more meaningful way...
            var otherPathReversed = otherPath.Cast<Node>().Reverse();

            // Prints on screen the Cities that are part of this path.
            foreach(Node n in otherPathReversed)
            {
                Console.WriteLine(n.Key);
            }

            // Get the total cost of the other path.
            double otherPathTotalCost = otherPath.TotalCost;
            // Get the estimation cost of the other path.
            double otherPathEstimation = estimate(otherPath.LastStep);

            // Prints on the screen the relevant information so that it gets easier to debug the code and see how
            // the A* search algorithm really does the job...
            Console.WriteLine("Total Cost other path = {0}", otherPathTotalCost);
            Console.WriteLine("Estimation other path = {0}", otherPathEstimation);
            Console.WriteLine(@"Priority Queue Cost other path = {0} =
                            Total Cost other path + Estimation other path =
                            {1}", kvp.Key, otherPathTotalCost + otherPathEstimation);
        }

        Console.WriteLine();
    }

    Console.WriteLine();
}

I also use two additional methods to get the Start and Destination cities entered by the user when s/he runs the code. Both methods keep a loop until the user enters the name of a city that is indeed part of the Graph we’ve just created:

/// <summary>
/// Gets the Destination city.
/// </summary>
/// <param name="graph">The Graph</param>
/// <returns>Name of Destination city</returns>
private static string GetDestinationCity(Graph graph)
{
    string destinationCity;

    do
    {
        Console.Write("\nEnter a Destination city: ");

        destinationCity = Console.ReadLine();
    }
    while(!graph.Nodes.ContainsKey(destinationCity));

    return destinationCity;
}

/// <summary>
/// Gets the Destination city.
/// </summary>
/// <param name="graph">The Graph</param>
/// <returns>Name of Destination city</returns>
private static string GetDestinationCity(Graph graph)
{
    string destinationCity;

    do
    {
        Console.Write("\nEnter a Destination city: ");

        destinationCity = Console.ReadLine();
    }
    while(!graph.Nodes.ContainsKey(destinationCity));

    return destinationCity;
}

This is the main entry point of the Console Application I created:

static void Main(string[] args)
{
    do
    {
        // Creating the Graph...
        Graph graph = new Graph();

        //FillGraphWithGridMap(graph);

        FillGraphWithEarthMap(graph, DistanceType.Kilometers);

        // Prints on the screen the distance from a city to its neighbors.
        // Used mainly for debug information.
        // DistanceBetweenNodes(graph, DistanceType.Kilometers);

        Console.WriteLine("A* Search - Sample implementation by Leniel Macaferi, June 7-20, 2009\n");
        Console.WriteLine("These are the Cities you can choose as Start and Destination in Romania: \n");

        // Prints on screen the cities that you can choose as Start and Destination.
        foreach(Node n in graph.Nodes.Cast<Node>().OrderBy(n => n.Key))
        {
            Console.WriteLine(n.Key);
        }

        string startCity = GetStartCity(graph);

        string destinationCity = GetDestinationCity(graph);

        Node start = graph.Nodes[startCity];

        Node destination = graph.Nodes[destinationCity];

        // Function which tells us the exact distance between two neighbours.
        Func<Node, Node, double> distance = (node1, node2) => node1.Neighbors.Cast<EdgeToNeighbor>().Single(etn => etn.Neighbor.Key == node2.Key).Cost;

        // Estimation/Heuristic function (Manhattan distance)
        // It tells us the estimated distance between the last node on a proposed path and the destination node.
        //Func<Node, double> manhattanEstimation = n => Math.Abs(n.X - destination.X) + Math.Abs(n.Y - destination.Y);

        // Estimation/Heuristic function (Haversine distance)
        // It tells us the estimated distance between the last node on a proposed path and the destination node.
        Func<Node, double> haversineEstimation = n => Haversine.Distance(n, destination, DistanceType.Kilometers);

        //Path<Node> shortestPath = FindPath(start, destination, distance, manhattanEstimation);
        Path<Node> shortestPath = FindPath(start, destination, distance, haversineEstimation);

        // Prints the shortest path.
        foreach(Node n in shortestPath.Reverse())
        {
            Console.WriteLine(n.Key);
        }

        Console.Write("\nDo you wanna try A* Search again? Yes or No? ");
    }
    while(Console.ReadLine().ToLower() == "yes");
}

The main entry point above calls all the other methods I showed in this post.

This is all you need to run the A* pathfinding search algorithm! :-)

I think the code is well documented through comments.

I wish this helps you understand how to put together the working pieces necessary to run a test case.

Next time: I’ll run a test case using the Graph we have assembled in this post.

A* pathfinding search in C# - Part 2
A* pathfinding search in C# - Part 3

Code available at GitHub: https://github.com/leniel/AStar

Last Sunday after I got back from church I read Kirill Osenkov’s post Algorithms in C#: shortest path around a polygon (polyline routing). Kirill mentions Eric Lippert’s excellent series of posts titled Path Finding Using A* in C# 3.0. I’ve read that series of posts a long time ago (2007 - I was on the last year of the computer engineering course).

See you how life is interesting: in 2007 after reading Lippert’s posts I wanted to see a running sample of the code but didn’t try to implement that until the time I read Osenkov’s post. Why did it took so long? I don’t know how to answer this.

I studied A* (A star) in the 9th term of the computer engineering course  (Feb-Jun, 2007). The discipline was Artificial Intelligence. At that time I didn’t implement any code for this specific algorithm (I think this is due the so famous excuse during the classes - we just don’t have enough time to do that. We have lots of topics to see yet.) . Therefore, we’ve just run test cases on sheets of paper. Not so good but a start.

Well, Eric wrote the base structure of the A* pathfinding algorithm but didn’t provide a complete running sample. He wrote the following:

I have a nice example of using A* to find the shortest path around a lake (but not the longest shortest path!) but I'm not going to post it here until Orcas ships. I'll just put up the whole project file at that time and you can check it out all at once.

Still on Sunday night I took the time to write some code that put up a running A* search.

I basically merged some code I had already posted on the series of posts titled Breadth and depth first search and created some properties here and there to get the whole thing running. It’s nothing more than code reuse.

The following is the basic project’s structure I created:

In Path Finding Using A* in C# 3.0, Part One the A* algorithm is described.

In Path Finding Using A* in C# 3.0, Part Two the data structures necessary to implement the A* algorithm are defined.

In this part Eric writes:

Let’s make an immutable stack of nodes which tracks the total cost of the whole path. Later on, we’ll see that we need to enumerate the nodes of this thing, so we’ll do a trivial implementation of IEnumerable while we’re at it. And since we don’t know exactly what a node will look like, let’s make the thing generic.

In part two we are presented to an immutable stack that I’ve put inside the Path class.

In Path Finding Using A* in C# 3.0, Part Three we are presented to a priority queue. This structure is responsible for putting the best paths so far in priority order, that is, the path with a lesser cost has a major priority.

In this part Eric writes:

In order to make the A* algorithm work we need to get the lowest-estimated-cost-path-discovered-so-far out of the list of paths under consideration. The standard data structure for doing so is called a “priority queue”. Priority queues are so-called because they are typically used to store a list of jobs where each job has an associated priority.

The PriorityQueue lies within its namesake class.

In Path Finding Using A* in C# 3.0, Part Four we get the FindPath method that is the one responsible for finding the shortest path possible. This method uses all of the remaining classes shown on the project structure above.

I put the FindPath method inside the AStar class.

In this part Eric writes:

What do we need to make the algorithm run? We need a start node, a destination node, a function which tells us the exact distance between two neighbours, and a function which tells us the estimated distance between the last node on a proposed path and the destination node.

This is the beautiful PathFind method:

static public Path<TNode> FindPath<TNode>(
    TNode start,
    TNode destination,
    Func<TNode, TNode, double> distance,
    Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
    var closed = new HashSet<TNode>();

    var queue = new PriorityQueue<double, Path<TNode>>();

    queue.Enqueue(0, new Path<TNode>(start));

    while(!queue.IsEmpty)
    {
        var path = queue.Dequeue();

        if(closed.Contains(path.LastStep))
            continue;

        if(path.LastStep.Equals(destination))
            return path;

        closed.Add(path.LastStep);

        foreach(TNode n in path.LastStep.Neighbours)
        {
            double d = distance(path.LastStep, n);

            var newPath = path.AddStep(n, d);

            queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
        }
    }

    return null;
}

When you get at the fourth part of Eric’s posts you may get thinking: How can I run this thing? That’s what I try to explain in this post.

The immutable stack implemented in part two of Eric’s posts is a generic one, that is, it accepts an object custom made to represent a Node in the path.

I already had a class Node that I used sometime ago while studying Artificial Intelligence. Take a look at Breadth and depth first search series of posts.

I also needed a Graph that represents the map formed with the connections between the nodes.

The Graph has a NodeList that stores all the nodes currently in the graph.

A node can have neighbors, that is, other nodes connected to it and such connections are represented in the code through the class AdjacencyList. Each node has an AdjacencyList that stores its neighbors.

A connection (edge) between two nodes (vertexes) is represented by the EdgeToNeighbor class that stores the neighbor of a node and the cost to get to that neighbor.

The AdjacencyList, EdgeToNeighbor, Graph, Node and NodeList classes are the outcome of an excellent series of articles by Scott Mitchell titled An Introduction to Data Structures. I got those classes and added them to the project.

This way I had all set to pass in the first two parameters of the PathFind method.

Now I needed to figure out how to create the distance and estimate functions to pass as the third and fourth parameters.

For the distance function I did this:

// Function which tells us the exact distance between two neighbours.
Func<Node, Node, double> distance = (node1, node2) => node1.Neighbors.Cast<EdgeToNeighbor>().Single(etn => etn.Neighbor.Key == node2.Key).Cost;

The distance function receives two nodes as parameters as can be seen in the PathFind method and returns a double value. I then use a lambda expression to find the Cost, (distance) in this case, between the two nodes. I get the neighbors of node1 and cast those to EdgeToNeighbor and execute a query using a lambda expression again to return the Cost only if the key of one of the neighbors of node1 is equal to the key of node2.

For the estimation function I did this:

// Estimation/Heuristic function (Haversine distance)
// It tells us the estimated distance between the last node on a proposed path and the destination node.
Func<Node, double> haversineEstimation = n => Haversine.Distance(n, destination, DistanceType.Kilometers);

Now I’m using as the estimation the Haversine formula. This formula gives the great-circle distances between two points on a sphere (Earth) from their longitudes and latitudes.

I got the Haversine formula code from the post Haversine Formula in C# and in SQL by Seth Long. I just adapted it a little bit so that I could use it with the Node data structure.

The haversine generic delegate receives as input a Node and return a double. Using a lambda expression I get the Haversine distance from node n to the destination node and I set that I want the distance in Kilometers.

With the distance and estimate functions on hand we’re OK to call the PathFind method.
Wait! Don’t we need something before that? Of course we need. We need to populate the graph with nodes. After all we’re after the shortest path between two nodes and we need some nodes to test the A* star pathfinding search. :-)

Next time: I’ll show you how to create a complete scenario using the same Romania map I used in the Breadth and depth first search series of posts.

References
[1] Lippert, Eric. Path Finding Using A* in C# 3.0, Part One. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/02/path-finding-using-a-in-c-3-0.aspx>. Accessed on June 13, 2009.

[2] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Two. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/04/path-finding-using-a-in-c-3-0-part-two.aspx>. Accessed on June 13, 2009.

[3] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Three. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx>. Accessed on June 13, 2009.

[4] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Four. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/10/path-finding-using-a-in-c-3-0-part-four.aspx>. Accessed on June 13, 2009.

[5] Mitchell, Scott. An Extensive Examination of Data Structures. 2005. Available at <http://msdn.microsoft.com/en-us/library/ms379570(VS.80).aspx>. Accessed on June 13, 2009.

[6] Long, Seth. Haversine Formula in C# and in SQL. 2008. Available at <http://megocode3.wordpress.com/2008/02/05/haversine-formula-in-c>. Accessed on June 13, 2009.

Breadth and depth first search - part 1
Breadth and depth first search - part 2

As an extra, today I'm posting the C++ code of the breadth and depth first search algorithms. Take a look at part 1 and part 2 of this series.

When I had to hand in the work for the artificial intelligence discipline, the teacher wanted the code in C++ and I had already started developing the code in C#. The result was two versions of the same functions. The good part is that I could master both languages while developing such a code.

The code presented here uses an adjacency matrix to represent the links between the cities that are part of the Romania map shown bellow.

The following is the adjacency matrix:

// Adjacency matrix
int map[21][21] = {
/*   A B C D E F G H I L M N O P R S T U V Z */
  {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1}, // Arad
  {2,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0}, // Bucharest
  {3,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0}, // Craiova
  {4,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, // Dobreta
  {5,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, // Eforie
  {6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0}, // Fagaras
  {7,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, // Girgiu
  {8,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, // Hirsova
  {9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, // Iasi
  {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0}, // Lugoj
  {1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Mehadia
  {2,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, // Neamt
  {3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, // Oradea
  {4,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}, // Pitesti
  {5,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0}, // Rimnicu Vilcea
  {6,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0}, // Sibiu
  {7,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Timisoara
  {8,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0}, // Urziceni
  {9,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0}, // Vaslui
  {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0}  // Zerind
};

Note that the first commented line represents the initial letter of each city's name. The mapping done with the adjacency matrix refers to these letters so that it's easier to understand. For example, getting the first entry of the adjacency matrix that refers to Arad: we have that Arad has paths that lead us to Sibiu, Timisoara and Zerind, thus we put a value of 1 on the columns that represent those cities, in this case, the columns beneath the letters S, T and Z. That's how the mapping is done. We put a value of 0 on the other columns to state that there is no path that leads us to those cities.

The code also has a hand made version of the stack and queue data structures. Each one of these structures is on its proper header file and are inline functions. See their implementations:

// Queue struct Queue { int start, end, tot; int info[max + 1]; }; void StartQueue(Queue *q) { q->tot = 0; q->start = 1; q->end = 0; } int IsQueueEmpty(Queue *q) { return q->tot == 0 ? 1 : 0; } int IsQueueFull(Queue *q) { return q->tot == max ? 1 : 0; } int Adc(int x) { return x == max ? 1 : x + 1; } void Enqueue(Queue *q, int x) { if(!IsQueueFull(q)) { q->end = Adc(q->end); q->info[q->end] = x; q->tot++; } } int Dequeue(Queue *q) { int ret = 0; if(!IsQueueEmpty(q)) { ret = q->info[q->start]; q->start = Adc(q->start); q->tot--; } return ret; } // End Queue

// Stack struct Stack { int topo; int info[max + 1]; }; void StartStack(Stack *s) { s->topo = 0; } int IsStackEmpty(Stack *s) { return s->topo==0 ? 1 : 0; } int IsStackFull(Stack *s) { return s->topo == max ? 1 : 0; } void Push(Stack *s, int x) { if(!IsStackFull(s)) { s->topo++; s->info[s->topo] = x; } } int Pop(Stack *s) { int ret = 0; if(!IsStackEmpty(s)) { ret = s->info[s->topo]; s->topo--; } return ret; } // End Stack

The Breadth First Search and Depth First Search functions are written in the same fashion of the C# code, but with little modifications.

void BreadthFirstSearch(int origin, int destination)
{
  Queue *q = new Queue();

  StartQueue(q);

  Enqueue(q, origin);

  while(IsQueueEmpty(q) == 0)
  {
    int u = Dequeue(q);

    if(u == destination)
    {
      printf("Path found.");

      break;
    }
    else
    {
      visited[u] = 1;

      for(int v = 1; v <= 20; v++)
      {
        if(map[u][v] != 0)
        {
          if(visited[v] == 0)
          {
            visited[v] = 1;

            parents[v] = u;

            if(v != destination)
            {
              if(!IsQueueFull(q))
              {
                Enqueue(q, v);

                ShowPath(v);

                printf("\n");
              }
              else
              {
                printf("Queue full.");

                break;
              }
            }
            else
            {
              ShowPath(v);

              return;
            }
          }       
        }
      }
    }
  }
}

void DepthFirstSearch(int origin, int destination)
{
  Stack *s = new Stack();

  StartStack(s);

  Push(s, origin);

  while(IsStackEmpty(s) == 0)
  {
    int u = Pop(s);

    if(u == destination)
    {
      printf("Path found.");

      break;
    }
    else
    {
      visited[u] = 1;

      for(int v = 1; v <= 20; v++)
      {
        if(map[u][v] != 0)
        {
          if(visited[v] == 0)
          {
            visited[v] = 1;

            parents[v] = u;

            if(v != destination)
            {
              if(!IsStackFull(s))
              {
                Push(s, v);

                ShowPath(v);

                printf("\n");
              }
              else
              {
                printf("Stack full.");

                break;
              }
            }
            else
            {
              ShowPath(v);

              return;
            }
          }      
        }
      }
    }
  }
}

To show the travelled paths there is a recursive function called ShowPath:

void ShowPath(int u)
{
  if(parents[u] != 0)
    ShowPath(parents[u]);

  printf(" %s", cities[u]);
}

You see, I had finalized the C# code and even sent the code to the teacher, but I received his reply stating that he wanted the code in C++. I complained with him! I told him about the easiness that modern programming languages as C# offers us when writing code.

Today, the data structures (queue and stack) "hand made" in this code are present in modern and optimized fashions inside standard libraries. We just need to instantiate an object from that specific class, in this case, stack or queue, and tada, we get lots of functions that do the hard work. But the point here is not the easiness. What the teacher wanted to force us to do was to comprehend how those data structures really function.

Nothing is better than writing the data structures by yourself. Although I didn't agree at the time, I thank him for forcing me to learn. Needless to say, these are basic data structures and are used in a great amount of code. You'll see these data structures during your entire developer life.

Visual Studio C++ Console Application
You can get the Microsoft Visual Studio Project and the app executable at:

http://leniel.googlepages.com/BreadthDepthFirstSearchCPlusPlus.zip

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

Breadth and depth first search - part 2
Breadth and depth first search - part 3

Search algorithms
The idea behind search algorithms is to simulate the exploration of a space of states or search space through the generation of successor states already explored.

Tree based search algorithms
Tree search algorithms are the heart of searching techniques. The basic principle is that a node is taken from a data structure, its successors examined and added to the data structure. By manipulating the data structure, the tree is explored in different orders for instance level by level (breadth-first search) or reaching a leaf node first and backtracking (depth-first search).

Definitions

• State - a representation of a physical configuration.
• Node - a data structure part of a search tree. A node has the following properties: father, sons, depth and path cost.

States don't have father, sons, depth and path cost.

Types of problems

• Deterministic accessible - simple states problem.
• Deterministic inaccessible - multiple states problem.
• Non deterministic inaccessible - contingency problem (maybe) - sensors must be used during the execution process. The solution is a tree or a policy. Many times alternates between search and execution.
• Unknown search space - exploration problem (online).

Selecting a search space
The real world is extremely complex. The search space must be abstracted from the solution process.

Abstracting we have:

• Abstract state - the set of real states.
• Abstract operator - combination of real actions.
• Abstract solution - set of real paths that represents a solution in the real world.

Each abstract action must be easier than the action in the real problem.

A simple algorithm

function GeneralSearch(problem, strategy)

  return a solution or failure

Initialize the search tree using the initial state of the problem

loop do

  if there are no candidates for expansion then

    return failure

Choose a leaf node for expansion according to strategy

if the node contains a goal state then

  return the corresponding solution

else

  expand the node and add the resulting nodes to the tree

end

Algorithm implementation

function GeneralSearch(problem, QueueingFunction)

nodes <- MakeQueue(MakeNode(InitialState[problem]))

loop do

  if nodes is empty then

    return failure

  node <- RemoveFront(nodes) a leaf node for expansion according
to strategy

  if GoalTest[problem] applied to State(node) succeeds then

    return node

  nodes <- QueueingFunction(nodes, Expand(node, Operators[problem]))

end

Search strategies
A search strategy is a choice made between the methods used to expand the nodes. Each method has its proper order of expansion. Strategies are evaluated according to following parameters:

• Time complexity - the number of generated or expanded nodes.
• Space complexity - maximum number of nodes presented in the memory.
• Optimality - the solution found has the minimum cost?

Complexities in time and space are measured in terms of:

• b - maximum ramification factor of the search tree.
• d - depth of the solution that has the minimum cost.
• m - maximum depth of the search space (can be ∞) infinite.

The two strategies presented in this post (breadth and depth first search) are considered uninformed strategies because they only use the information available in the problem definition. 

Breadth first search
The breadth first search expands the less deep node. The data structured used to implement this search algorithm is a queue. 

Breadth first search properties
Is complete? Yes, if (b is finite).

Time: 1 + b² + b³ + … + b^d = O(b^d). e.g.: exponential in d

Space: O(b^d) (maintains all the nodes in memory)

Optimal? Yes, if cost per step is 1; in general is not optimal.

Space is the big problem for can generate nodes at a rate of 1 MB / sec. 24 hours = 86 GB.

Depth first search
The depth first search expands the deepest node.

The data structure used to implement this search algorithm is a stack.

An important note about the depth first search is that it can execute infinite cycles so it’s mandatory to check the states already visited to avoid such infinite cycles.

Depth first search properties
Is complete? No. It is imperfect in spaces of infinite depth or in cyclic paths. Is complete only in a finite search space.

Time: O(bm). Is very bad if m is a lot greater than d. If solutions are dense can be fastest than the breadth first search.

Space: O(bm) e.g.: linear in space

Optimal? No. 

Working problem: vacation in Romania
In this post let's explore a simple states problem as shown in the following picture:

Suppose we are taking a vacation in Romania. More specifically we are in the city called Arad. We want to go to Bucharest the capital city of Romania and our flight takes off tomorrow. Breaking down our problem, we have:

• Objective - go to Bucharest.
• Search space - several cities to get to Bucharest.
• Operator - drive through the cities.

In this case a solution is a sequence of cities so that the last city is Bucharest.

A valid path could be: Arad, Sibiu, Fagaras, Bucharest. e.g.: Arad -> Zerind represents a complex set of possible paths, returns, pauses for resting, etc.

To guarantee the realizability, any real state in “Arad” must take us to some real state in “Zerind”.

The problem's formulation can be:

• Initial state - Arad
• Operator (or successor function S(x)) - eg.: Arad -> Zerind, Arad -> Sibiu, etc.
• Goal test - can be explicit or implicit as x = Bucharest or NoDirty(x).
• Path cost (additive) - can be the sum of distances, used operators, etc.

The solution is a sequence of operators that takes from the initial state to the goal state. 

Implementing the breadth and depth first search in C#
The following methods use two classes implemented by Scott Mitchell [1]. The classes are: Node and EdgeToNeighbor.

I just added a new property called PathParent in the node class.
 

public static void BreadthFirstSearch(Node start, Node end)

{

  Queue<Node> queue = new Queue<Node>();

  queue.Enqueue(start);

  while(queue.Count != 0)

  {

    Node u = queue.Dequeue();

    // Check if node is the end

    if(u == end)

    {

      Console.Write("Path found.");

      break;

    }

    else

    {

      u.Data = "Visited";

      // Expands u's neighbors in the queue

      foreach(EdgeToNeighbor edge in u.Neighbors)

      {

        if(edge.Neighbor.Data == null)

        {

          edge.Neighbor.Data = "Visited";

          if(edge.Neighbor != end)

          {

            edge.Neighbor.PathParent = u;

            PrintPath(edge.Neighbor);

          }

          else

          {

            edge.Neighbor.PathParent = u;

            PrintPath(edge.Neighbor);

            return;

          }

          Console.WriteLine();

        }

        /* shows the repeated nodes

        else

        {

          Console.Write(edge.Neighbor.Key);

        } */

        queue.Enqueue(edge.Neighbor);

      }

    }

  }

}
 

public static void DepthFirstSearch(Node start, Node end)

{

  Stack<Node> stack = new Stack<Node>();

  stack.Push(start);

  while(stack.Count != 0)

  {

    Node u = stack.Pop();

    // Check if node is the end

    if(u == end)

    {

      Console.WriteLine("Path found");

      break;

    }

    else

    {

      u.Data = "Visited";

      // Store n's neighbors in the stack

      foreach(EdgeToNeighbor edge in u.Neighbors)

      {

        if(edge.Neighbor.Data == null)

        {

          edge.Neighbor.Data = "Visited";

          if(edge.Neighbor != end)

          {

            edge.Neighbor.PathParent = u;

            PrintPath(edge.Neighbor);

          }

          else

          {

            edge.Neighbor.PathParent = u;

            PrintPath(edge.Neighbor);

            return;

          }

          Console.WriteLine();

          stack.Push(edge.Neighbor);

        }

        /* shows the repeated nodes

        else

        {

          Console.Write(edge.Neighbor.Key);

        } */

      }

    }

  }

}

Summary
The formulation of a problem requires abstraction to avoid irrelevant details of the real world so that a search space can be defined and explored.

In a next post 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 in the picture above, 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. Before that I recommend the reading of the excellent revision about data structures written by Scott Mitchell [1]. Although I only use the facts exposed in part 5 of Scott's article: From Trees to Graphs, it's worth to read starting in part 1. For now, look and think about the breadth and depth first search implementation in C#. 

References
[1] Mitchell, Scott. An Extensive Examination of Data Structures. 2004. Available at <http://msdn2.microsoft.com/en-us/library/aa289152(VS.71).aspx>. Accessed on January 8, 2008.

[2] Artificial Intelligence Depot. Blind search. Available at <http://ai-depot.com/Tutorial/PathFinding-Blind.html>. Accessed on January 8, 2008.