Outputting route from SF-NYC

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#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;
  }
}




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

What do you mean by that?
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.
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?
It didn't crash when I changed it to this. (Added equals sign).

1
2
3
4
 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.
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.
(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.
Last edited on
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.
1
2
3
4
5
 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!
Last edited on
That worked! You are amazing, thanks a lot!
Topic archived. No new replies allowed.