Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Breadth-First Print Cities

That's all the code we need to get the data in. Now, we need a routine to display the contents of our vectors. Referring to Figure Agent-18, we see that PrintCities ( ) still needs to be defined. Listed below is the void function PrintCities ( ):

void PrintCities()
{
  City TempCity;
  Neighbor TempNeighbor;

  vector<City> ::iterator CityNumber;
  vector<Neighbor> ::iterator NeighborNumber;

  cout<<endl<<endl;

  for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
  {
    TempCity=*CityNumber;
    cout<<"Current City: "<<TempCity.Name<<endl;
    cout<<"Neighbors: ";
    for(NeighborNumber=TempCity.Neighbors.begin( );NeighborNumber<TempCity.Neighbors.end( );NeighborNumber++)
    {
      TempNeighbor=*NeighborNumber;
      cout<<" " <<TempNeighbor.Name;
      cout<<"," <<TempNeighbor.Distance;
      cout<<"," <<TempNeighbor.ShortestDistance;
    }
    cout<<endl<<endl;
  }
}

Figure BFS-9: Code to print contents of Cities vector


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 City Structure.

  • 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

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

struct City
{
  string Name;
  vector <Neighbor> Neighbors;
};

vector<City> Cities;

//Declare Functions

void MakeMap( );
void PrintCities( );
Neighbor MakeNeighbor(string, int, int);

//Program Start Here:

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

//MakeMap Function Listing:
//Additional Data will have to be input

void MakeMap()
{
  City TempCity;
  Neighbor TempNeighbor;

  //Enter Data for Oradea

  TempCity.Name="Oradea";

  TempNeighbor.Name="Zerind";
  TempNeighbor.Distance=71;
  TempNeighbor.ShortestDistance=374;
  TempCity.Neighbors.push_back(TempNeighbor);

  TempNeighbor.Name="Sibiu";
  TempNeighbor.Distance=151;
  TempNeighbor.ShortestDistance=253;
  TempCity.Neighbors.push_back(TempNeighbor);

  Cities.push_back(TempCity);

//Enter Data for Zerind

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

  TempCity.Neighbors.push_back(MakeNeighbor("Oradea",71,380));
  TempCity.Neighbors.push_back(MakeNeighbor("Arad",75,366));

  Cities.push_back(TempCity);
}

//MakeNeighbor Function Listing:

Neighbor MakeNeighbor(string NeighborName, int PathLength, int StraightLineDistance)
{
  Neighbor SomeCity;

  SomeCity.Name =NeighborName;
  SomeCity.Distance =PathLength;
  SomeCity.ShortestDistance =StraightLineDistance;

  return SomeCity;
}

//Output Entire Data Structure

void PrintCities()
{
  City TempCity;
  Neighbor TempNeighbor;

  vector<City> ::iterator CityNumber;
  vector<Neighbor> ::iterator NeighborNumber;

  cout<<endl<<endl;

  for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
  {
    TempCity=*CityNumber;
    cout<<"Current City: "<<TempCity.Name<<endl;
    cout<<"Neighbors: ";
    for(NeighborNumber=TempCity.Neighbors.begin();NeighborNumber< TempCity.Neighbors.end();NeighborNumber++)
    {
      TempNeighbor=*NeighborNumber;
      cout<<" " <<TempNeighbor.Name;
      cout<<"," <<TempNeighbor.Distance;
      cout<<"," <<TempNeighbor.ShortestDistance;
      }
    cout<<endl<<endl;
  }
}

Figure BFS-10: Initial Functional Road Map Program


I tested the code in BFS-9 and placed it in a file called r1.cpp and compiled it with the Linux GNU compiler. The final CR-LF did not copy and paste, so we get the warning, but it created the a.out executable anyways. As you can see, the output of PrintCities ( ) is the same as the input from MakeMap ( ). so it looks like we're good up to here:

rm1 Output

Figure BFS-11: First Level Output of Road Map program.


The last piece of information needed to completely fill the data structure is the following table of straight-line distance between each Neighbor and Bucharest:

City Distance City Distance City Distance City Distance
Arad 366 Bucharest 0 Craiova 160 Drobeta 242
Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151
Iasi 226 Lugoj 244 Mehadia 241 Neamt 234
Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253
Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374

Figure BFS-12: Straight Line Distances to Bucharest


Entering all the data from the map as well as the data from Agent-25 will output the database as follows:

RoadMap Database

Figure BFS-13: Road Map Database

In order to continue with this guide, and continue the discussion on Developing the Path Record to keep track of our progression: 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