Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ Depth-First Make Map Function

Now that we have a data structure capable of containing all the necessary data for a Depth-First Search algorithm, as well as functions to build the Depth-First Search data structure. We still need to transfer the data from the map into the data structure. For this process, we will create a function called MakeMap(). MakeMap() will take advantage of the City AddNeighbor function, to add the neighboring city information to each of the corresponding cities:


void	MakeMap()
{
	City TempCity;

//Enter data for Arad

	TempCity.Name="Arad";
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Zerind",75);
	TempCity.AddNeighbor("Sibiu", 140);
	TempCity.AddNeighbor("Timisoara",118);
	Cities.push_back(TempCity);

//Enter data for Bucharest

	TempCity.Name="Bucharest";
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Giurgiu",90);
	TempCity.AddNeighbor("Urziceni",85);
	TempCity.AddNeighbor("Fagaras",211);
	TempCity.AddNeighbor("Pitesti",101);
	Cities.push_back(TempCity);
}

						

Figure DFS-5: Code to Manually Enter data using City Class data structure.


The data in this example will be entered in alphabetical order. Notice that it is not necessary to order the data for the algorithm to function. The explanation of the code is as follows:

  • City TempCity: Declare a temporary copy of the City class data structure to transfer data into the Cities vector.

  • TempCity.Name="Arad": Assign the name to City.

  • TempCity.Neighbors.clear(): Each time we enter data for a new city, we have to clear out the Neighbors vector so the data from the preceding cities does not accumulate.

  • TempCity.AddNeighbor("Zerind",75): Add the data describing the connection between Arad and Zerind.

  • Cities.push_back(TempCity): Save the data in the Cities vector so we can reuse TempCity to reenter data for the remaining data points.

C++ Depth-First PrintCities()

Now that a couple of data points are entered. We should print out the map to make sure the data structure is functioning as planned. The following code will print the data structure to the screen. It can also be used to help conceptualize the methods used for extracting data from the Cities vector:


//Function to Display contents of Cities data structure to screen:

void	PrintCities()
{
	City		TempCity;
	Neighbor	TempNeighbor;

	vector<City>::iterator	CityNumber;

//Loop Through Entire Cities vector

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		TempCity=*CityNumber;
		cout<<"Current City: "<<TempCity.Name<<endl;
		cout<<"Neighbors: ";

//Loop Through Each Neighbor printing name and distance

		for(TempCity.NeighborNumber=TempCity.Neighbors.begin();
			TempCity.NeighborNumber<TempCity.Neighbors.end();
				TempCity.NeighborNumber++)
		{
			TempNeighbor=*TempCity.NeighborNumber;
			cout<<"  "<<TempNeighbor.Name;
			cout<<","<<TempNeighbor.Distance;
		}
		cout<<endl<<endl;
	}
}
						

Figure DFS-6: Code to print contents of Cities Data structure


Let's see how the data is being printed out:

  • void PrintCities ( ): A void function because we don't need to return anything.

  • City TempCity: Temporary Class construct of type City .

  • Neighbor TempNeighbor: Temporary Neighbor Structure.

  • vector <City> ::iterator CityNumber: An index to step through our Cities vector.

  • vector <Neighbor> ::iterator NeighborNumber: An index to step through our Neighbors sub vector.

  • for(CityNumber=Cities.begin( );
      CityNumber<Cities.end( );
        CityNumber++)
    • CityNumber=Cities.begin( ): Initialize the index to the first City in the Cities vector.
    • CityNumber<Cities.end( ): Test for the last City in Cities vector.
    • CityNumber++: Increment the index to the next City.

  • TempCity=*CityNumber: Transfer the indexed vector element into TempCity.

  • for(NeighborNumber=TempCity.Neighbors.begin( );
      NeighborNumber<TempCity.Neighbors.end( );
        NeighborNumber++)
    • NeighborNumber=TempCity.Neighbors.begin( ): Initialize the index to the first Neighbor of the city we are looking at.
    • NeighborNumber<TempCity.Neighbors.end( ): Test for last Neighbor in Neighbors vector.
    • NeighborNumber++: Increment index to next Neighbor.
  • TempNeighbor=*NeighborNumber: Transfer the indexed vector element into TempNeighbor.

  • cout<<" " <<TempNeighbor.Name;
    cout<<"," <<TempNeighbor.Distance;
    cout<<"," <<TempNeighbor.ShortestDistance;
    Print out the Neighbor Name, Distance and Straight Line Distance

Putting it all together

We now have the minimum components to test and run our code. The complete listing is below:

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

//Declare Data Structures

//Structure for Adding Edge to Graph

struct Neighbor
{
  string Name;
  int Distance;
  int ShortestDistance;
};

//Class Data Structure for City type Node:

class	City
{
public:
	string	Name;
	vector<Neighbor>		Neighbors;
	vector<Neighbor>::iterator	NeighborNumber;

	City();
	City(string);
	void	AddNeighbor	(string, int);
};

//Parameterless Class constructor

City::City()
{
	Name="";
	NeighborNumber=Neighbors.begin();
}

//Class Constructor with Name supplied:


City::City(string CityName)
{
	Name=CityName;	
	NeighborNumber=Neighbors.begin();
}

//Function or Method to Add Connected Node to City data structure

void	City::AddNeighbor(string NeighborName, int NeighborDistance)
{
	Neighbor TempNeighbor;
	TempNeighbor.Name=NeighborName;
	TempNeighbor.Distance=NeighborDistance;
	Neighbors.push_back(TempNeighbor);
	NeighborNumber=Neighbors.begin();
}

//Data Structure for Entire Map

vector<City>	Cities;


void	MakeMap();

//Function to Display contents of Cities data structure to screen:

void	PrintCities();
void	PrintCities()
{
	City		TempCity;
	Neighbor	TempNeighbor;

	vector<City>::iterator	CityNumber;

//Loop Through Entire Cities vector

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		TempCity=*CityNumber;
		cout<<"Current City: "<<TempCity.Name<<endl;
		cout<<"Neighbors: ";

//Loop Through Each Neighbor printing name and distance

		for(TempCity.NeighborNumber=TempCity.Neighbors.begin();
			TempCity.NeighborNumber<TempCity.Neighbors.end();
				TempCity.NeighborNumber++)
		{
			TempNeighbor=*TempCity.NeighborNumber;
			cout<<"  "<<TempNeighbor.Name;
			cout<<","<<TempNeighbor.Distance;
		}
		cout<<endl<<endl;
	}
}

//Program starts here:

int	main()
{
	MakeMap();
	PrintCities();
	return 0;
}

//Function used to enter data manually

void	MakeMap()
{
	City TempCity;

//Enter data for Arad

	TempCity.Name="Arad";
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Zerind",75);
	TempCity.AddNeighbor("Sibiu", 140);
	TempCity.AddNeighbor("Timisoara",118);
	Cities.push_back(TempCity);

//Enter data for Bucharest

	TempCity.Name="Bucharest";
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Giurgiu",90);
	TempCity.AddNeighbor("Urziceni",85);
	TempCity.AddNeighbor("Fagaras",211);
	TempCity.AddNeighbor("Pitesti",101);
	Cities.push_back(TempCity);
}
						

Figure DFS-7: Listing to enter and print data points.


The listing above is "cut and pasteable". Running the code through the linux g++ compiler gives the following output in the putty shell:

Depth First 1

Figure DFS-8: Depth-First Search Output


In order to continue with this guide, and start the discussion of Depth-First Search GetChildCity Function and the associated C++ code to perform the operation: Press the Button below:

Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-First C++ Solution

Depth-First Data Structure


Depth-First MakeMap()

Depth-First Display Data

Depth-First Initial Listing


Depth-First GetChildCity()

Depth-First Path Record


Depth-First Search Function


Depth-First PrintGoalPath()

Depth-First Main()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance