railsystem.cpp

卡内基梅隆大学SSD5数据结构的实验内容包括实验1－5的所有要提交的文件

#pragma warning (disable:4786)
#pragma warning (disable:4503)

#include "RailSystem.h"
#define MAXSIZE 10000
#include<stack>

void RailSystem::reset(void) {

    // TODO: reset the data objects of the 
    // City objects' contained in cities
	map<string,City*>::iterator it=cities.begin();
	for(;it!=cities.end();it++)
	{

		it->second->from_city="";
		it->second->total_distance=0;
		it->second->total_fee=MAXSIZE;
		it->second->visited=false;
	}
}

RailSystem::RailSystem(string const &filename) {
    
    load_services(filename);
}

void RailSystem::load_services(string const &filename) {

	ifstream inf(filename.c_str());
	string from, to;
	int fee, distance;

	while ( inf.good() ) {

		// Read in the from city, to city, the fee, and distance.
		inf >> from >> to >> fee >> distance;

		if ( inf.good() ) {
		
			// TODO: Add entries in the cities container and
			// and services in the rail system for the new 
            // cities we read in.	
			City* fCity=new City(from);
			City* tCity=new City(to);
		    cities.insert(map<string, City*>::value_type(from,fCity));
            cities.insert(map<string, City*>::value_type(to,tCity));
			if(outgoing_services[from].size()==0)
			{
				list<Service*> temp;
			    outgoing_services[from]=temp;
				outgoing_services[from].push_back(new Service(to,fee,distance));
			}	
			else
				outgoing_services[from].push_back(new Service(to,fee,distance));
		}
	}

	inf.close();
}

RailSystem::~RailSystem(void) {

    // TODO: release all the City* and Service*
    // from cities and outgoing_services
	//for(map<string,City*>::iterator it=cities.begin();it!=cities.end();it++)
	map<string,City*>::iterator it;
	for(it=cities.begin();it!=cities.end();it++)
	{
		City *p=it->second;
		delete p;
	}
	cities.clear();
	map<string,list<Service*> >::iterator itr;
	for(itr=outgoing_services.begin();itr!=outgoing_services.end();itr++)
	{
		list<Service*> serList=itr->second;
		for(int i=0;i<serList.size();i++)
		{
			Service* service=serList.front();
			serList.pop_front();
			delete service;
		}
		serList.clear();
	}
	outgoing_services.clear();
}

void RailSystem::output_cheapest_route(const string& from,
                const string& to, ostream& out) {

	reset();
	pair<int, int> totals = calc_route(from, to);

	if (totals.first == INT_MAX) {
		out << "There is no route from " << from << " to " << to << "\n";
	} else {
		out << "The cheapest route from " << from << " to " << to << "\n";
		out << "costs " << totals.first << " euros and spans " << totals.second
			<< " kilometers\n";
        cout << recover_route(to) << "\n\n";
	}
}

bool RailSystem::is_valid_city(const string& name) {

	return cities.count(name) == 1;
}

pair<int, int> RailSystem::calc_route(string from, string to) {

	priority_queue<City*, vector<City*>, Cheapest> candidates;
    // TODO: Implement Dijkstra's shortest path algorithm to
    // find the cheapest route between the cities
	
	City* sourceCity=cities[from];
	sourceCity->total_fee=0;
	candidates.push(sourceCity);
	while(!candidates.empty())
	{
		City* city= candidates.top();
		city->visited=true;
		candidates.pop();
		list<Service*> &li = outgoing_services[city->name];
		list<Service*>::iterator itr;
		for(itr=li.begin();itr!=li.end();itr++)
		{
			Service* service = *itr;
			City* adjacency_city= cities[service->destination];
			if(adjacency_city->visited==false)
			{
				if((city->total_fee+service->fee)<adjacency_city->total_fee)
				{
					//其中total_fee表示源顶点到当前节点的最短路径
					//service_fee表示邻接边的权重
					adjacency_city->total_fee=city->total_fee+service->fee;
					adjacency_city->from_city=city->name;
					adjacency_city->total_distance=city->total_distance+service->distance;
					candidates.push(adjacency_city);
				}
			}
			
		}
		if(city->name==to)
		{
			city->visited=true;
			break;
		}
	}
		
	// Return the total fee and total distance.
	// Return (INT_MAX, INT_MAX) if not path is found.
	if (cities[to]->visited) {
		return pair<int,int>(cities[to]->total_fee, cities[to]->total_distance);
	} else {
		return pair<int,int>(INT_MAX, INT_MAX);
 	}

}

string RailSystem::recover_route(const string& city) {
	
	// TODO: walk backwards through the cities
	// container to recover the route we found
    City* to=cities[city];
	string path;
	stack<string> pathNames;
	while(1)
	{
		pathNames.push(to->name);
		if(to->from_city=="")
			break;
		to=cities[to->from_city];
	}
	while(!pathNames.empty())
	{
		string city=pathNames.top();
		   path+=city;
		if(pathNames.size()!=1)
		{
				path+=" to ";
		}
		pathNames.pop();
	}
	return path;
}