/* SI 335 Spring 2012
* Project 6
* YOUR NAME HERE
*/
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
// Prints an error message and exits ungracefully
void error (const char* msg);
// Looks up the given vertex name in the array of names,
// and returns the index of that vertex in the array.
// Uses the linearSearch algorithm for search in an unsorted array.
int lookup (const string& name, const string* names, int n);
int main(int argc, char** argv) {
// Get the filename
if (argc != 2) {
cerr << "Usage: " << argv[0] << " <graph_file>" << endl;
error("Need graph filename as argument.");
}
ifstream graph(argv[1]);
int n, m;
// Read in the sizes
graph >> n >> m;
if (n <= 0) error("n must be positive");
if (m <= 0) error("m must be positive");
// Declare storage
// Location names are stored in an array of strings
// Edges are stored in a pair of adjacency matrices,
// one for time and one for cost.
// The index of a vertex in either matrix is defined as the
// index of that NAME in the array of strings.
string* names = new string[n];
int** times = new int*[n]; // Note: double pointer = 2-D array
int** costs = new int*[n];
times[0] = new int[n*n];
costs[0] = new int[n*n];
for (int i=1; i<n; ++i) {
times[i] = times[i-1]+n;
costs[i] = costs[i-1]+n;
}
// Initialize the adjacency matrix.
// IMPORTANT: I am using the weight of -1 to stand for "infinity".
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (i == j) {
times[i][j] = 0;
costs[i][j] = 0;
}
else {
times[i][j] = -1;
costs[i][j] = -1;
}
}
}
// Read in the location names
for (int i=0; i<n; ++i)
graph >> names[i];
// Read in the edges
string uname, vname;
int uind, vind;
int time, cost;
for (int i=0; i<m; ++i) {
graph >> uname >> vname >> time >> cost;
// Look up the index of each name
uind = lookup (uname, names, n);
vind = lookup (vname, names, n);
if (uind < 0 || vind < 0) error ("Invalid edge name");
// Set the weight in each adjacency matrix,
// in BOTH DIRECTIONS (for undirected array)
times[uind][vind] = time;
times[vind][uind] = time;
costs[uind][vind] = cost;
costs[vind][uind] = cost;
}
graph.close();
// Now read in and process the requests
int timeCost;
while (cin >> uname >> vname >> timeCost) {
int uind = lookup (uname, names, n);
int vind = lookup (vname, names, n);
if (uind < 0 || vind < 0) error("Invalid starting/ending point");
/*******************************************************************
* My algorithm for the shortest paths is REALLY BAD.
* What it does is a depth-first EXPLORATION to examine every
* possible path from the starting vertex to find the shortest path
* to the ending vertex. Once the length of the shortest path is
* known, it does a SECOND exploration to find (again) that actual
* path. Notice that this is a depth-first "exploration" as opposed
* to a normal DFS because it is never marking any nodes as "black",
* only gray basically. This makes it have exponential time. SLOW!
******************************************************************/
vector<int> curPath; // The currently-explored path
int curLength = 0; // The length of curPath
vector<int> fringe; // vectors make good stacks.
int shortest = -1; // length of the shortest path found so far
fringe.push_back(uind);
while (!fringe.empty()) {
int cur = fringe.back();
// Search for cur in the curPath (check if that vertex is "gray")
bool white = true;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == cur) white = false;
}
if (white) {
// cur is an unexplored vetex ON THIS PATH.
// Update curLength (stays at 0 if curPath is empty)
if (!curPath.empty()) {
int previous = curPath.back();
curLength += costs[previous][cur] + timeCost*times[previous][cur];
}
// Add cur to the path
curPath.push_back(cur);
if (cur == vind) {
// Found a path to the destination!
if (shortest == -1 || curLength < shortest)
shortest = curLength;
continue; // Skip to the next iteration of the while loop.
}
// Add all cur's children to the fringe.
// Skip children that are already in curPath though!
for (int child=0; child<n; ++child) {
bool inpath = false;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == child) inpath = true;
}
if (!inpath && costs[cur][child] >= 0)
fringe.push_back(child);
}
}
else {
// cur has just finished being explored, so pop it off.
fringe.pop_back();
curPath.pop_back();
if (!curPath.empty()) {
int previous = curPath.back();
curLength -= costs[previous][cur] + timeCost*times[previous][cur];
}
}
}
if (curLength < 0) error("No path exists");
// Now we know that curLength is the length of the shortest path.
// But we still don't have the actual path! So we have to go through the
// ENTIRE SEARCH a second time until we find it again.
fringe.push_back(uind);
while (!fringe.empty()) {
int cur = fringe.back();
// Search for cur in the curPath (check if that vertex is "gray")
bool white = true;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == cur) white = false;
}
if (white) {
// cur is an unexplored vetex ON THIS PATH.
// Update curLength (stays at 0 if curPath is empty)
if (!curPath.empty()) {
int previous = curPath.back();
curLength += costs[previous][cur] + timeCost*times[previous][cur];
}
// Add cur to the path
curPath.push_back(cur);
if (cur == vind) {
// Found a path to the destination!
if (curLength == shortest) {
// WE FOUND IT!
break; // Break out of the while loop.
}
continue; // Skip to the next iteration of the while loop.
}
// Add all cur's children to the fringe.
// Skip children that are already in curPath though!
for (int child=0; child<n; ++child) {
bool inpath = false;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == child) inpath = true;
}
if (!inpath && costs[cur][child] >= 0)
fringe.push_back(child);
}
}
else {
// cur has just finished being explored, so pop it off.
fringe.pop_back();
curPath.pop_back();
if (!curPath.empty()) {
int previous = curPath.back();
curLength -= costs[previous][cur] + timeCost*times[previous][cur];
}
}
}
// Now print out the actual length and path.
cout << curLength;
for (int j=0; j<curPath.size(); ++j)
cout << ' ' << names[curPath[j]];
cout << endl;
}
// Clean up memory
delete [] names;
delete [] times[0];
delete [] times;
delete [] costs[0];
delete [] costs;
return 0;
}
// Prints an error message and exits ungracefully
void error (const char* msg) {
cerr << "ERROR:" << endl << msg << endl;
exit(1);
}
// Looks up the given vertex name in the array of names,
// and returns the index of that vertex in the array.
// Uses the linearSearch algorithm for search in an unsorted array.
int lookup (const string& name, const string* names, int n) {
for (int i=0; i<n; ++i) {
if (names[i].compare(name) == 0)
return i;
}
return -1;
}