Outputting route from SF-NYC

[lordhalomaster]

Hey Everyone,

I needed some help with my program. The purpose of the program is to create two routes from SF-NYC from selected "legs". I have a collection of ~40 legs. Except for San Francisco, every city should have more than one path into it. Except for New York City, every city should have more than one path out of it. San Francisco is the start, and has no way into it, and New York City is the end, with no way out. I am supposed to output two things: any route from SF-NYC(getAnyRoute), and the shortest route from SF-NYC(getShortestRoute.)

The getAnyRoute outputs correctly. The problem is that my program crashes before the getShortestRoute function.
Any help is appreciated!
The code:

#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

#include <string>
using std::string;

#include <set>
using std::set;

#include <cassert>

class Leg;
class Route;
class ShortestRoute;

class Leg
{
  private:
	const string startCity;
	const string endCity;
	const double distance;

  public:
	Leg(const string startingLocation, const string endingLocation, const double miles): startCity(startingLocation), endCity(endingLocation), distance(miles){};
	friend class Route;
	friend class ShortestRoute;
	void operator=(const Leg&);//cassert
	friend ostream& operator<<(ostream&, const Leg&);
	friend ostream& operator<<(ostream&, const Route&);
};

class Route
{
  private:
    const Leg** const leg;
    const int num;
	const double tracker;

  public:
    Route(const Leg&);
    Route(const Route&, const Leg&);
	Route(const Route&);
	~Route(){delete[] leg;}
	bool isGreaterThan(const Route&) const;
	bool operator<(const Route&) const;
	friend class ShortestRoute;
	void operator=(const Route&);//cassert
	friend ostream& operator<<(ostream& out, const Route& r);
};

Route::Route(const Leg& aLeg):  leg(new const Leg*[1]), num(1), tracker(aLeg.distance)
{
	leg[0] = &aLeg;
}

Route::Route(const Route& route, const Leg& bLeg): leg(new const Leg*[route.num+1]), num(route.num+1),  tracker(route.tracker+bLeg.distance)
{
    if(route.leg[num-2]->endCity != bLeg.startCity)
    {
      delete[] leg;
      throw "End route city and start leg city don't match";
    }

    for(int i = 0; i< num-1; i++)
    {
      leg[i] = route.leg[i];
    }

    leg[route.num] = &bLeg;
}

Route::Route(const Route& cLeg): leg(new const Leg*[num]), num(cLeg.num), tracker(cLeg.tracker)
{
  for(int i=0; i<cLeg.num+1; i++)
  {
    leg[i] = cLeg.leg[i];
  }
}

class ShortestRoute
{
  private:
    static const Leg legs[];
    static const int det;

  public:
    static const Route getAnyRoute(const string, const string);
    static const Route getShortestRoute(const string, const string);
};


const Route ShortestRoute::getAnyRoute(const string from, const string to)
{
  for(int i = 0; i < det; i++)
  {
    if(legs[i].endCity.compare(to) == 0)
    {
      if(legs[i].startCity.compare(from) == 0)
      {
        return Route(legs[i]);
      }
      else
      {
        return Route(getAnyRoute(from, legs[i].startCity), legs[i]);
      }
    }
  }
  throw "No route possible from given vector";
}

Route const ShortestRoute::getShortestRoute(const string from, const string to)
{
  set<Route> routes;

  for(int i = 0; i < det; i++)
  {
    if(legs[i].endCity.compare(to) == 0)
    {
      if(legs[i].startCity.compare(from) == 0)
      {
        routes.insert(Route(legs[i]));
      }
      else
      {
        routes.insert(Route(getShortestRoute(from, legs[i].startCity), legs[i]));
      }
    }
  }
  set<Route>::iterator it = routes.begin();
  return *it;
}

const int ShortestRoute::det = 44;

const Leg ShortestRoute::legs[] =  //database
{
  Leg ("San Francisco", "Milpitas", 46.2),
  Leg ("Milpitas", "Dublin", 23.9),
  Leg ("Milpitas", "Stockton",70.7),
  Leg ("Dublin", "Stockton", 49.9),
  Leg ("Dublin", "Manteca", 42.8),
  Leg ("Stockton", "Elko", 468),
  Leg ("Stockton", "Reno", 179),
  Leg ("Manteca", "Elko", 477),
  Leg ("Manteca", "Reno", 189),
  Leg ("Elko", "Salt Lake City", 230),
  Leg ("Elko", "Logan", 264),
  Leg ("Reno", "Logan", 553),
  Leg ("Reno", "Salt Lake City", 518),
  Leg ("Logan", "Casper", 403),
  Leg ("Logan", "Cheyyene", 433),
  Leg ("Salt Lake City", "Logan", 82.3),
  Leg ("Salt Lake City", "Casper", 410),
  Leg ("Salt Lake City", "Cheyyene", 440),
  Leg ("Casper", "Lexington", 462),
  Leg ("Casper", "Rochester", 824),
  Leg ("Cheyyene", "Lexington", 282),
  Leg ("Cheyyene", "Rochester", 838),
  Leg ("Lexington", "Davenport", 520),
  Leg ("Lexington", "Indianapolis", 802),
  Leg ("Rochester", "Davenport", 251),
  Leg ("Rochester", "Indianapolis", 531),
  Leg ("Indianapolis", "Akron", 299),
  Leg ("Indianapolis", "Richmond", 213),
  Leg ("Davenport", "Akron", 521),
  Leg ("Davenport", "Richmond", 523),
  Leg ("Akron", "Pittsburgh", 111),
  Leg ("Akron", "Indiana", 155),
  Leg ("Richmond", "Pittsburgh", 394),
  Leg ("Richmond", "Indiana", 430),
  Leg ("Pittsburgh", "Lancaster", 238),
  Leg ("Pittsburgh", "New York City", 371),
  Leg ("Indiana", "Lancaster", 210),
  Leg ("Indiana", "Buffalo", 237),
  Leg ("Lancaster", "Buffalo", 320),
  Leg ("Buffalo", "New York City", 373),
  Leg ("San Francisco", "New York City", 21000),
};

int main()
{
  try
  {
    cout << "Any route form sf-nyc: " << endl;
    cout << ShortestRoute::getAnyRoute("San Francisco", "New York City");
    cout << "Shortest route from sf-nyc: " << endl;
    cout << ShortestRoute::getShortestRoute("San Francisco", "New York City");
  }
  catch(const char* a)
  {
    cout << "Error: " << a << endl;
  }
  cout << endl;
}

bool Route::operator<(const Route& r) const
{
  if(this->isGreaterThan(r))
    return false;
  else
    return true;
}

ostream& operator<<(ostream& out, const Leg& l)
{
  out << l.startCity << " to " << l.endCity << " is " << l.distance << "miles" << endl;
  return out;
}

ostream& operator<<(ostream& out, const Route &r)
{
  out << r.leg[0]->startCity;
  for(int i = 0; i < r.num; i++)
  {
    out << " to " << r.leg[i]->startCity;
  }
  out << " to " << r.leg[r.num-1]->endCity << " is " << r.tracker << " miles. " << endl;
  return out;
}
//
bool Route::isGreaterThan(const Route& r) const
{
  if(this->tracker > r.tracker)
  {
    return true;
  }
  else
  {
    return false;
  }
}

[Bdanielz]

Sorry maybe I am missing it but I do not see how you are dealing with your pointers in your copy constructor?

[lordhalomaster]

What do you mean by that?

[Hippogriff]

Looks like you are using num before it is initialized.

Route::Route(const Route& cLeg): leg(new const Leg*[num]), num(cLeg.num), tracker(cLeg.tracker)

As it says in the C++ standard.

non-static data members are initialized in order of declaration in the class definition.

Quick fix is to make sure you list num first in your class, probably nicer ways you could do it but it should work. Either way make sure num is initialized before Leg* uses it.

Your operator< seems to crash when both trackers are equal, I would do a check for that.

[lordhalomaster]

I made that quick fix you mentioned, and all of the warnings I was previously getting regarding initialization have disappeared. However the problem with the program crashing still persists. When you say do a check for when both trackers are equal, what do you mean? And where am I supposed to perform this check?

[Hippogriff]

It didn't crash when I changed it to this. (Added equals sign).

 if(this->tracker => r.tracker)
  {
    return true;
  }

But it depends on how you want your logic, but something similar to that.
If it's still crashing some more details would be helpful, I would also slowly go through it with a debugger to see where it is crashing.

[lordhalomaster]

Hey James2250. I tried what you mentioned above, and that didn't work. So I tried '>=' instead. It did compile properly and when I ran it, the program crashed in the same place. I think it might have to do with the Route const ShortestRoute::getShortestRoute(const string from, const string to) function because of the fact that the program chokes after it outputs getAnyRoute and right before its supposed to output the shortest route.

[Hippogriff]

(Opps, that = typo)

It runs for me correctly after fixing those 2 things I mentioned, so I'm not sure there is much else I can say.
http://codepad.org/6IglcvaA

You can try printing certain values from getShortestRoute to test if they are what you expect them to be.

[lordhalomaster]

Hi,

I tried compiling/running with visual studios this time, and it seemed to work properly!!

Just one last thing, any idea why "San Francisco to San Francisco to..." prints every time I output getAnyRoute and getShortestRoute? Its only supposed to print San Francisco once.

[Hippogriff]

 out << r.leg[0]->startCity;
  for(int i = 0; i < r.num; i++)
  {
    out << " to " << r.leg[i]->startCity;
  }

You are printing r.leg[0] twice. Start the for loop at i =1?
I haven't checked all of the numbers so I couldn't tell you if it is printing the right stuff for everything else.

Heading off, so good luck!

[lordhalomaster]

That worked! You are amazing, thanks a lot!