Name: Sung Il Choi

Course: CSI 203

Subject: Project

Instructor: Dr. Wang

 

                                                Road planner

 

            Road planner is a program which design to gives an optimal road plan from Norristown to Temple University. The program involves taking into account the uncertainties that could crop up in the planning process such as snow, traffic jam, accident etc. Program takes several factors to make road plan. The factors are time, date, weather and road condition. The program takes accounted these factors to decide the road plan. The Active logic is used for reasoning about the choice of road, based on distance, weather and road condition. If one of road has accident or mad weather, program is able to decide to change or continues with the plan. Sometime road with mad condition can be faster than taking alternative plan. 

 

This program is small that can be use in large scale with sufficient information. It also can be used in navigation  system. Now this days, Navigation system is very popular for car. The current navigation system only give position of car and map. With Active logic, the trip is going to be more pleasant. Such system can be incorporated in Fedex, UPS, military, and several transportation company.

           

Case study: Road Planner

 

Problem

 

 Creates a program that gives a best possible road from Norristown to Temple University. Also It need to be able to change the road plan according to user's need. Program should display the approximate time and distance. If one of the road have accident or closed, It should give a alternative plan or tell continue with plan.

 

Analysis

 

 To give best possible road from Norristown to Temple University, It use Dijkstra's algorithm and need to take current date, time, weather condition and road condition from the user. 

 

1.   Date and month: if date is holiday, all road are clear.

2.   Time : if time is rush hour,  average speed is decreasing by 1/2 time.

3.   weather condition: if weather condition is mad, travel time is increasing by level of weather condition. The level of weather condition scale between 1 to 10.

4.   Road condition: ask user if there is any mad condition,  input the street.

Input from the user are:

    Date

    Time

    Weather condition

    Road condition( only accident )

Output for user are:

    Distance

    average speed

    Sequence of road

 

Dijkstra's Algorithm

procedure Dijkstra(G:weighted connected simple graph, with all weights positive)

{G has vertices a = V0, V1,......,Vn = z and weights w(vi, vj) where (vi,vj) = ~ if {vi, vj} is not an edge in G}

For i:= 1 to n

            L(vi):= ~

L(a) := 0

S:= null

{the labels are now initialized so that the label of a is zero and all other labels are ~, and S is the empty set}

while z not belong to S

begin

            u:= a vertex not in s with L(u) minimal

            S:= S u {u}

            for all vertices v not in S

                 if L(u) + w(u, v) < L(v) then L(v):= L(u) + w(u, v)

            {this adds a vertex to S with minimal label and updates the labels of             vertices not in S}

end {L(z) = length of shortest path from a to z}

 

Design

 

 The program divides into three subprogram.

 

            Initial Algorithm

            1. Ask current date, time, weather and road condition.

            2. Makes the road plan.

            3. Display the result

 

            Algorithm Refinements

            Step 2 Refinement

            2.1 Find shortest path using Dijkstra’s Algorithm

            2.2 Takes factors to decide if the path is optimal road.

            2.3 if the path is not optimal, find shortest path.

            Step 3 Refinement

            3.1 Display average speed

            3.2 Display travel distance

            3.3 Display roads

code:

 

#include<iostream>

#include<string>

#include<fstream>

#include<cstdlib>

using namespace std;

 

struct road

{          

            string names;

            int mile, time;

            char connect, traclight;

};

 

#define infile "road.dat"//infile

 

//function definition

void mainmenu(char &hour,int &date, char &accident, string &street);

void sortpath(int& totalmile, float& totaltime, road allroad[10], char& root);

void decision(char accident, char hour, road allroad[10],float totaltime,int totalmile, char root,string street, int date);

char findstreet(road allroad[10], string street);

char holiday(int date);

void loadroad(ifstream& eds,road allroad[10]);

void display(char root, road allroad[10], int totaltime, int totalmile);

 

 

 

 

int main()

{

            int date, option, totalmile;

            float totaltime;

            char accident,hour, root = 'a';

            string street;

            road allroad[10];

            ifstream eds;

 

           

            //prepare files

            eds.open(infile);

            if (eds.fail())

            {

                        cerr<<"******* ERROR: cannot open" <<infile<<"for input."<<endl;

                        return EXIT_FAILURE;//failure return

            } 

           

            //call all fuction

            loadroad(eds,allroad);

            mainmenu(hour,date, accident, street);

            sortpath(totalmile, totaltime, allroad, root);

           

            //close file

            eds.close();

 

            return 0;

}

 

//begining of mainmenu fuction

void mainmenu(char &hour,int &date, char &accident, string &street)

{

           

            cout<<"Please type r:rush hour and n:normal hour"<<endl;

            cout<<"please enter time: ";

            cin>>hour;

            cout<<"Please enter date: ";

            cin>>date;

            cout<<"Please type y:yes or n: no"<<endl;

            cout<<"is there any accident? ";

            cin>>accident;

            if ( tolower(accident) == 'y')

            {

                        cout<<"Please enter street: ";

                        cin>>street;

            }

}//end of mainmenu function

 

//begining of sortpath function

void sortpath(int& totalmile, float& totaltime, road allroad[10], char& root)

{

            int temptime, tempmile;

            char con = root;

            for(int y=1; y <= 2; y++)

            {

                        for(int x=0; x < 10; x++)

                                    {

                                                con = allroad[x].connect;

                                                if ((con =='con') || (con == 'u'))

                                                {

                                                            temptime += allroad[x].time;

                                                            tempmile += allroad[x].mile;

 

                                                }

                                    }

                        //compare the total distance

                        if(tempmile < totalmile)

                        {

                        totaltime = temptime;

                        totalmile = tempmile;

                        root = con;

                        }

            con = 'b';

            }

 

}// end of sortpath function

 

//beginig of decision function

//use Active Logic to make decision

void decision(char accident, char hour, road allroad[10],float totaltime,int totalmile, char root,string street, int date)

{

            char now[3];//store conclusion

            now[3] = 'y'; //now[3] is future step. It has positive value

           

            //making decision for now[0], now[1], now[2].

if (accident == 'y')

            {            if (findstreet(allroad, street) == 'y')

                        now[0] = 'n';

            } else now[0] = 'y';

            if (hour == 'r')

                        now[1] = 'n';

                        else now[1] = 'y';

            if (holiday(date) =='y')

                        now[2] = 'y';

                        else now[2] = 'n';

 

                        //making final decision

                        for(int x = 0; x < 2;x++)

                        {

                                    if((now[x] == 'y') || (now[x+1] == 'y'))

                                                now[3] = 'y';

                                    else now[3] = 'n';

                        }

 

                        //if now[3] is 'y' then display the result

                        //else find the another road

                        if (now[3] == 'y')

                                    display(root,allroad, totaltime, totalmile);

                        else {

                                                for(int z = 0; z < 10; z++)

                                                {

                                                            if (allroad[z].connect == root)

                                                                        allroad[z].connect = 'n';

                                                }                                              

                                                sortpath(totalmile, totaltime, allroad, root);

                                                display(root, allroad, totaltime, totalmile);

                                    }

}//end of decision function

                                               

 

//subfunction of decision

//begining of findstreet

char findstreet(road allroad[10], string street)

{

            char result = 'n';

 

            for(int x=0; x < 10; x++)

            {

                        if (street == allroad[x].names)

                        result = 'y';

            }

           

            return result;

}//end of findstreet

 

//subfunction of decision

//beginng of holiday

char holiday(int date)

{

            char result;

 

            switch(date)

            {

                        case 1:

                        case 25:

                        case 8:

                        case 23:

                        case 17:

                                    result = 'y';

                                    break;

                        default:

                                    result = 'n';

            }

 

            return result;

}//end of holiday

 

//begining of loadroad function

//load street into memory  

void loadroad(ifstream& eds,road allroad[10])

{

            string streets;

            int nummile, time, x;

            char connected, traffilight;

 

            //read first street

            eds>>streets>>connected>>nummile>>time>>traffilight;

            x = 0;

            while(!eds.eof())

            {

                       

                        //storing information into array

                        allroad[x].names = streets;

                        allroad[x].connect = connected;

                        allroad[x].mile = nummile;

                        allroad[x].time = time;

                        allroad[x].traclight = traffilight;

                        //updating counter

                        x+=1;

                        //read next street

                        eds>>streets>>connected>>nummile>>time>>traffilight;

 

            } // end while

 

}//end of loadroad function

 

//display the result

//beigning of display function

void display(char root, road allroad[10], int totaltime, int totalmile)

{

            cout<<" Road plan"<<endl;

            cout<<"---------------------"<<endl;

            for(int x =0; x < 10;x++)

            {

                        if((allroad[x].connect == root) || (allroad[x].connect == 'u'))

                                    cout<<allroad[x].names<<endl;

            }

            cout<<endl;

            cout<<"Distances is: "<<totalmile<<endl; 

            totaltime = totaltime / 2;

cout<<"Average mph: "<<totaltime<<endl;

}//end of display function

 

 

Data file:road.dat

 

Norristow u 0 1 y

476south a 2 3 n

363north b 3 1 y

76east a 7 2 n

73east b 12 1 y

roosbelt a 3 3 n

309south b 4 2 n

cheltelham b 2 2 y

broad b 4 2 y

midbroad u 4 2 y

Temple u 0 2 y