Posted by Leniel Macaferi on 5/20/2008 07:03:00 PM

This post is related to one of the best coursework I've done during the computer engineering course. I'm really proud of it. It was the cornerstone in my programming career and helped me choose an area to put my efforts from that moment on. I was in the 5th term out of 10 (3rd year of the course out of 5 more exactly). The discipline was Programming Languages.

This subject is fantastic and is used extensively throughout the the computer science field.

First I'll give a short description about the Quicksort and Binary Search algorithms and then I'll present the work that I and my dear brother in faith Wellington Magalhães Leite did.

Quicksort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare. Typically, quicksort is significantly faster in practice than other sorting algorithms, because its inner loop can be efficiently implemented on most architectures.

Binary Search

A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value by selecting the median element in a list, comparing its value to the target value, and determining if the selected value is greater than, less than, or equal to the target value. A guess that turns out to be too high becomes the new top of the list, and a guess that is too low becomes the new bottom of the list. Pursuing this strategy iteratively, it narrows the search by a factor of two each time, and finds the target value.

Our paper

Our paper is entitled Quicksort and Binary Search Algorithms. You can get a copy at the end of this post.

Without more ado, see its abstract bellow:

Sorting and searching algorithms are a core part of the computer science area. They are used throughout the programming work when you need to sort a set of data and when you need to search for a specific record (key) present in such set of data.

Quicksort is one of the fastest (quick) sorting algorithms and is most used in huge sets of data. It performs really well in such situations.

Binary search tree is one of the fastest searching algorithms and is applied in a sorted set of data. It reduces the search space by 2 in each iteration, hence its name (binary).

In this paper we present the intrinsic nature of each algorithm as well as a functional implementation of such algorithms in the C++ programming language.

Keywords: quicksort, binary search, sorting algorithms, searching algorithms, c++ programming language

CONTENTS
1 INTRODUCTION 6
  1.1 Objective 6
  1.2 Definition 6
      1.2.1 Sorting algorithms 6
      1.2.2 Searching algorithms 7
2 DEVELOPMENT 8
  2.1 Quicksort algorithm (swapping and partitioning) 8
      2.1.1 Detailed steps 8
  2.2 Binary search algorithm 9
  2.3 Studying the efficiency of the methods 9
      2.3.1 The big O notation 9
      2.3.2 Quicksort efficiency 10
            2.3.2.1 The best and the worst case 10
            2.3.2.2 Comparison with other sorting algorithms 11
      2.3.3 Binary search efficiency 11
3 APPLICATION 12
  3.1 Quicksort implementation 12
  3.2 Binary search implementation 13
4 CONCLUSION 14
5 REFERENCES 15

Words of wisdom

As I mentioned, during the 5th term of the computer engineering course our teacher Marcus Vinicius Carvalho Guelpeli selected some sorting and searching algorithms to pass to the class as a coursework.

The coursework should be done in pairs and each pair should select a sorting and searching algorithm to compose a paper about it. We selected the quicksort and the binary search algorithms. The teacher advised us that these weren't the easy ones. I just thought: that's what I want. I don't want the easy ones. Why? Because if you get just the easy problems I'll never understand something that demands a more deep approach and every time a difficult task is given you'll tend to refuse it. What's the best thing to do? Just accept the challenge and go for it. Chances are you'll succeed. That's just what happened with us.

We haven't just written about the quicksort and the binary search, we implemented it and presented it to the class in a power point presentation. The teacher liked it so much that our grade was the highest possible! :-) In the end what did we feel? An amazing feeling. Something such that the work had been done and we learned a lot from it. That's what a college is supposed to do. Give you the subjects and motivate you; teaching the basic so that you can dig up the more difficult aspects of the subject being taught.

So what's next? Well, I'll explain how we implemented the quicksort and the binary search algorithms.

Quicksort and Binary search algorithms implementation in C++

One of the things that I've always listened to was about code reuse. You search for something already implemented so that you just haven't to reinvent the wheel. Of course you'll complement or even adapt the available code to your situation. That was what we did. I found some code for the quick sort at MSDN and implemented the binary search one. Unfortunately the page at MSDN isn't available anymore. It's been three years since I hit that page.

I wanted a way of measuring the time elapsed so that we could compare the efficiency of both methods when they were fed with different input data sets. The input is nothing more than a text file .txt full of numbers in this case. Can be any data you want. Each test case we passed a text file with different random numbers and different quantity of numbers. For example, in a test case we passed a file named 2500.txt, that means 2500 random numbers. In another test case we passed other file named 7500.txt as so on. I think you got it. Doing so we could compare how well the algorithms were performing.

To generate the random numbers we used an Excel spreadsheet with the formula =RAND()*1000000. For each set of data we generated new numbers and copied and pasted those numbers into the text files that are the input for our program. During a coursework as this one we get to learn everywhere, even a new formula in Excel. It's really good. ;-)

Again, I searched for a timing class that I could reuse with the code and for sure I found it. I didn't use it at all but I used it to learn about how to measure time in C++. It's amazing how fast you can implement something. Much of the things you need related to programming are already implemented. You just have to search for it as is what you're doing here, I think! You searched for the subject of this post and here you are seeing something implemented. Try to learn from it and just don't copy the entire work and think that you know about it. It's wrong. Try to understand what the code is doing. Dive into the theory because it explains the inner essence.

The code that follows is well commented which is something every developer should do. You see, it was three years ago when we worked with this code. Today it's difficult to remember every step I took. The comments helped me to remember almost everything.

Bellow I present the quick sort method we borrowed from MSDN (we adapted it to fit our case). Note the use of the Partition method (explained in the accompanying paper):

// QuickSort implementation
void QuickSort(char** szArray, int nLower, int nUpper)
{
 // Check for non-base case
 if(nLower < nUpper)
 {
   // Split and sort partitions
   int nSplit = Partition(szArray, nLower, nUpper);
   QuickSort(szArray, nLower, nSplit - 1);
   QuickSort(szArray, nSplit + 1, nUpper);
 }
}

// QuickSort partition implementation
int Partition (char** szArray, int nLower, int nUpper)
{
 // Pivot with first element
 int nLeft = nLower + 1;
 char* szPivot = szArray[nLower];
 int nRight = nUpper;

 // Partition array elements
 char* szSwap;
 while(nLeft <= nRight)
 {
   // Find item out of place
   while(nLeft <= nRight && strcmp (szArray[nLeft], szPivot) <= 0)
     nLeft = nLeft + 1;
   while (nLeft <= nRight && strcmp (szArray[nRight], szPivot) > 0)
     nRight = nRight - 1;

   // Swap values if necessary
   if(nLeft < nRight)
   {
     szSwap = szArray[nLeft];
     szArray[nLeft] = szArray[nRight];
     szArray[nRight] = szSwap;
     nLeft = nLeft + 1;
     nRight = nRight - 1;
   }
 }

 // Move pivot element
 szSwap = szArray[nLower];
 szArray[nLower] = szArray[nRight];
 szArray[nRight] = szSwap;
 return nRight;
}

Now see the binary search method implementation that we did:

int BinarySearch(char** szArray, char key[], int nLower, int nUpper)
{
 // Termination case
 if(nLower > nUpper)
   return 0;

 int middle = (nLower + nUpper) / 2;

 if(strcmp(szArray[middle], key) == 0)
   return middle;
 else
 {
   if(strcmp(szArray[middle], key) > 0)
     // Search left
     return BinarySearch(szArray, key, nLower, middle - 1);
   // Search right
   return BinarySearch(szArray, key, middle + 1, nUpper);
 }
}

The next ones are the method prototypes and the main entry point that calls a menu. According to the user passed parameters we call the quicksort and the binary search methods:

// Function prototypes
void Menu(void);
void QuickSort(char** szArray, int nLower, int nUpper);
int Partition(char** szArray, int nLower, int nUpper);
int BinarySearch(char** szArray, char key[], int nLower, int nUpper);

// Application initialization
void main(void)
{
 char op;

 do
 {
   Menu();
   printf("\n\nDo you wanna a new QuickSort? Y/N");
   op = getche();
   if(islower(op))
     op = toupper(op);
 }
 while(op == 'Y');
}

void Menu(void)
{
 // Clear screen
 system("CLS");

 // Control execution time
 clock_t initial, final;

 // Print startup banner
 printf("\nQuickSort C++ Sample Application\n");
 printf("Copyright (c)2001-2002 Microsoft Corporation. All rights reserved.\n\n");
 printf("MSDN ACADEMIC ALLIANCE [http://www.msdnaa.net/]\n\n");
 printf("BinarySearch C++ Sample Application\n");
 printf("Copyright (c)2005 Leniel Braz de Oliveira Macaferi & Wellington Magalhaes Leite.\n");
 printf("UBM COMPUTER ENGINEERING - 5TH SEMESTER [http://www.ubm.br/]\n\n");

 // Describe program function
 printf("This program example demonstrates the QuickSort and BinarySearch algorithms by\n");
 printf("reading an input file, sorting its contents, writing them to a new file and\n");
 printf("searching on them.\n\n");

 // Prompt user for filenames
 char szSrcFile[1024], szDestFile[1024];
 printf("Source: ");
 gets(szSrcFile);
 printf("Output: ");
 gets(szDestFile);

 // Read contents of source file
 const long nGrow = 8;
 long nAlloc = nGrow;
 long nSize = 0;
 char** szContents = new char* [nAlloc];
 char szSrcLine[1024];
 FILE* pStream = fopen(szSrcFile, "rt");

 while(fgets(szSrcLine, 1024, pStream))
 {
   // Trim newline character
   char* pszCheck = szSrcLine;
   while(*pszCheck != '\0')
   {
     if(*pszCheck == '\n' && *(pszCheck + 1) == '\0')
       *pszCheck = '\0';
     pszCheck++;
   }

   // Append to array
   szContents[nSize] = new char [strlen(szSrcLine) + 1];
   strcpy(szContents[nSize], szSrcLine);
   nSize = nSize + 1;

   if(nSize % nGrow == 0)
   {
     // Resize the array
     char** szPrev = szContents;
     nAlloc += nGrow;
     szContents = new char* [nAlloc];
     memcpy(szContents, szPrev, nSize * sizeof(char*));
     delete szPrev;
   }
 }
 fclose (pStream);

 initial = clock();

 // Pass to QuickSort function
 QuickSort(szContents, 0, nSize - 1);

 final = clock();

 // Write sorted lines
 pStream = fopen (szDestFile, "wt");
 for(int nIndex = 0; nIndex < nSize; nIndex++)
 {
   // Write line to output file
   fprintf (pStream, "%s\n", szContents[nIndex]);
 }
 fclose (pStream);

 // Report program success
 printf("\nThe sorted lines have been written to the output file.\n\n");

 // QuickSort execution time
 double duration = (double)(final - initial) / CLOCKS_PER_SEC;

 printf("The QuickSort execution time was: %2.9lf s = %.0lf ms = %.0lf \xE6s\n\n", duration, duration * 1000, duration * 1000000);

 char op = '\0';

 do
 {
   printf("Do you wanna a BinarySearch to locate a specific key? Y/N");

   op = getche();
   if(islower(op))
     op = toupper(op);
   if(op == 'Y')
   {
     printf("\n\nType the key you want to search for: ");
     char key[1024];
     gets(key);

     initial = clock();

     if(BinarySearch(szContents, key, 0, nSize - 1))
     {
       final = clock();

       duration = (double)(final - initial) / CLOCKS_PER_SEC;

       printf("\nKey found!\n\n");

       printf("The BinarySearch execution time was: %2.9lf s = %.0lf ms = %.0lf \xE6s\n\n", duration, duration * 1000, duration * 1000000);

     }
     else
     {
       final = clock();

       duration = (double)(final - initial) / CLOCKS_PER_SEC;

       printf("\nKey not found!\n\n");

       printf("The BinarySearch execution time was: %2.9lf s = %.0lf ms = %.0lf \xE6s\n\n", duration, duration * 1000, duration * 1000000);

     }
   }
   else
   {
     // Deallocate entire array
     for(int nIndex = 0; nIndex < nSize; nIndex++)
       // Delete current array element
       delete szContents[nIndex];

     delete szContents;
     szContents = NULL;
   }
 }
 while(op == 'Y'); 
}

Visual Studio C++ Console Application

You can get the project files at:
http://leniel.googlepages.com/QuicksortBinarySearchCPlusPlus.zip

Random number generator

You can get the spreadsheet responsible for this task at:
http://leniel.googlepages.com/QuicksortBinarySearchRandomNumGen.xls

How to use it?

To use the program:

1. Enter the name of a file that contains unsorted data;
2. Use the sample files included in the .ZIP package as: 1000.txt and 2500.txt;
3. In the command line "Source", type: 1000.txt;
4. In the command line "Output", type a name to the file that will be sorted. e.g.: sorted.txt;
5. After the sorting process, choose if you want or not to execute a Binary Search. If yes, provide a value to be searched. If not, choose if it is or not desired to execute a new Quicksort.

Postscript:
- To generate random numbers, use the file Random numbers generator.xls file;
- The file QuicksortBinarySearch.cpp contains the source code. The same can be used freely. Mention the authors.

Efficiency comparison

For the sake of comparison I've run some test cases with different input files. See the result in the table that follows:

Quicksort and Binary search performance

n	File name	File size (bytes)	Timing (milliseconds)
			Quicksort	Binary search
10000	10000.txt	122.880	16	0
25000	25000.txt	200.704	78	0
50000	50000.txt	401.408	219	0
75000	75000.txt	602.112	360	0
100000	100000.txt	802.816	516	0

It's important to note that the time the quicksort takes appears to be longer but it is not. Why? Because the the program needs to read the file content and write the sorted data back to the output file so that it appears to take longer than the milliseconds shown on the above table. The timing functions just operate while the quicksort is running.

For the the binary search key I've input a value localized in the beginning of the sorted file, in the middle and in the end. There was no time changes. The binary search found the key I entered with a time less than (0 µs - microsecond). I have an AMD Athlon XP 2400 with 512 MB RAM.

See a screenshot of the last test case:

The paper

You can get a copy of the paper in the .PDF format at:
http://leniel.googlepages.com/QuicksortAndBinarySearchAlgorithms.pdf

Posted by Leniel Macaferi on 3/22/2008 03:30:00 PM

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

Posted by Leniel Macaferi on 2/08/2008 03:58:00 AM

Ordinary Differential Equation
In mathematics, an ordinary differential equation (or ODE) is a relation that contains functions of only one independent variable, and one or more of its derivatives with respect to that variable. To get in depth knowledge about ODEs refer to this article at Wikipedia.

A scientific magazine article
As the result of the Numerical Calculus discipline's classwork during the 4th term of the computer engineering course I and the teacher Dener Martins dos Santos decided to write an article about ordinary differential equations. In that discipline we studied about the classic methods for the resolution of ordinary differential equations.

We ended up with a concise informative article with the following title: Development and Numerical Simulation of Algorithms to Computational Resolution of Ordinary Differential Equations. Then we submitted the article to the scientific magazine of my alma mater university. We made it in the magazine called Revista Científica do Centro Universitário de Barra Mansa.

See the article's abstract below:

The computational simulation nowadays consists of a great tool assisting the learning process of complex mathematical calculations. This informative article shows how the computational resolution of differential equations assists in this learning. Two different types of computational resolution for differential equations are demonstrated: explicit Euler's method and Runge-Kutta's fourth order method. The programs were developed in C programming language. The results obtained via both methods are compared with the respective analytical solution (traditional, manual); in these a low level of generated computational error was perceived during their simulation, not compromising the methods.

Keywords: ordinary differential equations, numerical methods, C programming.

SUMMARY
1 INTRODUCTION
2 OBJECTIVE
3 REVISION
4 METHODOLOGY
  4.1 Programs
5 RESULTS
  5.1 Differential equation 1
      5.1.1 Initial conditions
      5.1.2 Analytical solution (traditional)
      5.1.3 Graphical solution
            5.1.3.1 Explicit Euler’s method
            5.1.3.2 Runge-Kutta’s fourth order method
  5.2 Differential equation 2
      5.2.1 Initial conditions
      5.2.2 Analytical solution (traditional)
      5.2.3 Graphical solution
            5.2.3.1 Explicit Euler’s method
            5.2.3.2 Runge-Kutta’s fourth order method
6 CONCLUSION
7 BIBLIOGRAPHY

See a screenshot of the output of Runge-Kutta's fourth order method when simulated with the 1st equation described in the paper:

You can get a PDF copy of the article at:

http://leniel.googlepages.com/DevNumSimOfAlgorithmsCompResOfODEs.pdf

Posted by Leniel Macaferi on 1/12/2008 09:45:00 PM

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 and executable of this post at:

http://leniel.googlepages.com/BreadthDepthFirstSearchCSharp.rar

Posted by Leniel Macaferi on 1/04/2008 08:20:00 PM

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.