Find all trains which overtake another train

Question

My task: find all trains, which overtake another train and return their trainId.

Implementation-suggestion:

for all trains B
    for all trains A
        find station C, where A departs and B later departs than A (the earliest one)
            if there is such one
                for all stations D, where A stops after C and B also stops
                    if B stops at D earlier than A, then B is a overtaker!

I implemented the algorithm, but it is very very slow, I need some help to improve this code. I have 3 input (.dat) files, where I build of each a Object which is like a list (StationList, TrainList, Schedule) and of each line (in this files) a own Object (Train, Station, Entry) which are all entries of the respective "list".

train.h

#ifndef TRAIN_H
#define TRAIN_H

#include <string>
#include <vector>

using namespace std;

class Train{
public:
  Train(string s);
  Train(int pId);     //for comparisons

  bool operator< (const Train &t) const;
  int getId() { return id; }

private:
  int id;
  int numberOfWaggons;
};

class TrainList{
public:
  TrainList(char const *filename);
  Train give(int index) { return trains[index]; }
  int length() { return trains.size(); }

private:
  vector<Train> trains;
};

#endif

train.cc

#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include "train.h"

using namespace std;

Train::Train(string s) {
  stringstream ss(s);
  ss >> id >> numberOfWaggons;
}

Train::Train(int pId) {
  id = pId;
}

TrainList::TrainList(char const *filename){
  ifstream input(filename);
  string line;

  while(getline(input,line))
    trains.push_back(Train(line));

  sort(trains.begin(), trains.end());
}

bool Train::operator< (const Train &t) const {
  return id < t.id;
}

station.h

#ifndef STATION_H
#define STATION_H

#include <string>
#include <vector>

using namespace std;

class Station {
public:
  Station(string s);
  Station(int pId);   // for comparisons

  string getName();
  bool operator< (const Station &s) const;
  int getId(){ return id; }

private:
  int id;
  string name;
};

class StationList {
public:
  StationList(char const *filename);
  Station give(int index) { return stations[index]; }
  int length() { return stations.size(); }

private:
  vector<Station> stations;
};

#endif

station.cc

#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include "station.h"

using namespace std;

Station::Station(string s) {
  stringstream ss(s);
  ss >> id >> name;
}

Station::Station(int pId) {
  id = pId;
}

StationList::StationList(char const *filename){
  ifstream input(filename);
  string line;

  while(getline(input,line))
    stations.push_back(Station(line));

  sort(stations.begin(), stations.end());
}

string Station::getName() {
  return name;
}

bool Station::operator< (const Station &s) const  {
  return id < s.id;
}

schedule.h

#ifndef SCHEDULE_H
#define SCHEDULE_H

#include <string>
#include <vector>

using namespace std;

class Entry{
public:
  Entry(string s);
  Entry(int pId, int time, int param);     //time=dep or arr, param 0 for time=arrival //for comparisons

  bool operator< (const Entry &e) const;
  bool operator== (const Entry &e) const;

  int getTrainId(){ return trainId; }
  int getArrival(){ return arrival; }
  int getDeparture(){ return departure; }

private:
  int trainId, stationId, arrival, departure, parameter;
};

class Schedule{
public:
  Schedule(char const *filename);
  int lookup(int trainId, int stationId, int param);
  int length() { return allEntries.size(); }
  Entry give(int index) { return allEntries[index]; }

private:
  vector<Entry> allEntries;
};

#endif

schedule.cc

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include "schedule.h"

using namespace std;

Entry::Entry(string s) {
  stringstream ss(s);
  int arrHour, arrMin, depHour, depMin;
  ss >> trainId >> stationId >> arrHour >> arrMin >> depHour >> depMin;
  /* Then it is not the first, but the last train */
  if(depHour == 0 && depMin == 0)
    depHour = 24;

  arrival = arrHour*60+arrMin;
  departure = depHour*60+depMin;
}

Entry::Entry(int pId, int statId, int param) {
  trainId = pId;
  stationId = statId;
  parameter = param;
}

Schedule::Schedule(char const *filename){
  ifstream input(filename);
  string line;

  while(getline(input,line)){
    allEntries.push_back(Entry(line));
  }
  sort(allEntries.begin(), allEntries.end());
}

int Schedule::lookup(int trainId, int stationId, int param) {
  Entry item(trainId, stationId, param);
  vector<Entry>::iterator it = find(allEntries.begin(), allEntries.end(), item);
  if (it != allEntries.end()){
    Entry e = *it;
    return (param == 0) ? e.getArrival() : e.getDeparture();
  }
  else
    return -1;
}

bool Entry::operator< (const Entry &e) const  {
  return (trainId == e.trainId && arrival < e.arrival) || trainId < e.trainId;
}

bool Entry::operator== (const Entry &e) const  {
  return (trainId == e.trainId && stationId == e.stationId);
}

and finally (here is the very ugly algorithm):

main.cc

#include <iostream>
#include <fstream>
#include "station.h"
#include "train.h"
#include "schedule.h"

using namespace std;

int main(int argc, char *argv[]) {

  StationList stations = StationList("stations.dat");
  TrainList trains = TrainList("trains.dat");
  Schedule schedule = Schedule("schedule.dat");

  for(int b = 0; b < trains.length(); b++){
    for(int a = 0; a < trains.length(); a++){
      for(int c = 0; c < stations.length(); c++){
        int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
        int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);

        if(departureA == -1 || departureB == -1)
          continue;

        if(departureA < departureB){
          for(int d = 0; d < trains.length(); d++){
            int arrivalA = schedule.lookup(trains.give(a).getId(), stations.give(d).getId(), 0);
            int arrivalB = schedule.lookup(trains.give(b).getId(), stations.give(d).getId(), 0);

            if(arrivalA == -1 || arrivalB == -1)
              continue;

            if(arrivalA > departureA && arrivalB > departureB && arrivalB < arrivalA){
              cout << "FOUND" << endl;
              break;
            }
          }
        }
      }
    }
  }   
}

Answer 1

The algorithm is not ugly. Every step is necessary, but it can be tweaked to avoid doing unnecessary work.

1. Speed up by skipping instructions

The easiest way to speed up algorithms with nested loops is to bail out of each loop as quickly as possible. For example:

    int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
    int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);

    if(departureA == -1 || departureB == -1)
      continue;

If the first schedule.lookup(...) for departureA returns -1, then you don't need to do the second lookup.

    int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
    if(departureA == -1)
      continue;

    int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);
    if(departureB == -1)
      continue;

Do the same in the inner loop for arrivalA and arrivalB.

Even earlier:

for(int b = 0; b < trains.length(); b++){
  for(int a = 0; a < trains.length(); a++){
    if(a == b) { continue; } // A train can't overtake itself.

2. Speed up by using the structure of the data

You can quickly find a name in a large phone book because the names are sorted. You sort TrainList, StationList, and the Entrys in Schedule, but don't make use of the fact that the lists are sorted. C++'s std::find searches through the entire list and does not stop when it has passed where an entry should be if it existed. So, write your own search routine that stops if it reaches an Entry that is larger than the search item (as defined by operator<(...).

Edited to indicate the proper function for performing binary search in C++
However, this is not taking full advantage of the sorted list. Binary search allows for finding an item in a sorted list without looking at nearly as many entries. In fact, binary search only works on sorted lists. This is implemented as std::lower_bound() in the <algorithm> header.

If adding structure doesn't help, don't do it. For example, I don't see how sorting the Trains in TrainList helps.

Other comments:

• Logic error: for(int d = 0; d < trains.length(); d++) should use stations.length().
• Entry::parameter is never used.
• There are two types of Entrys: one that contains the schedule information, and one that just contains train and station IDs. I see how you're using it in the Schedule::lookup(...) method to find the Entry with the complete data, but it's a bit confusing at first to see an Entry be created in order to search for it. You already have the Entry, why are you looking for it?
• The output of main() does not actually identify the overtaken trains.

Answer 2

The algorithm is overly complex.

First, some general remarks.

1. If you use find() in a loop, you're doing it wrong.

A search operation in a loop can be replaced by a grouping operation. Perform a single pass over the list and group it into a hashset.

2. If you can't reduce complexity, change the variable.

Kruskal's and Prim's algorithm both calculate the minimum spanning tree of a graph, but their complexity depends on edges (Kruskal) vs. vertices (Prim).

In most nested problems the variable to loop over can be chosen. Decide on the smallest.

In your case, the number of trains and stations is probably large, but each train stops at only a couple of stations.

Let's apply them.

for all trains B
    for all trains A

The number of trains is large, so we loop over the schedule instead.

function PointToPointConnections(Train T)
    for all stations A in schedule[T]
        for all stations B in schedule[T][A..end]
            append new PointToPointConnection to result list
    return result list

main
    for all trains T
        get PointToPointConnections(T)
        concatenate them to a large list

We now have a large list of all point-to-point connections. Each entry consist of

[origin, destination, departure, arrival, train id]

We group this list into a hashset by the [origin, destination] tuple.

for all PointToPointConnections
    group by [origin, destination]

Now, there's a set of list. Each of them is identified by a [origin, destination] tuple and contains the connections between those points.

[Berlin, Hamburg] ->
    17:01, 20:04, IRE 4272
    17:06, 19:11, EC 378
    17:42, 19:24, ICE 1508
[Berlin, Stuttgart] ->
    ...

Most of those sublists contain few or even only one item. Finding overtaking trains becomes a cheap operation.

for all sublists
    for all connections A in sublist
        for all connections B in sublist
            if A.departure > B.departure and A.arrival < B.arrival
                print("A overtakes B")

In the example, EC 378 and ICE 1508 overtake IRE 4272.

The complete algorithm.

create empty hashset (key: tuple, value: list of triples)
for all trains T
    get PointToPointConnections(T)
    for all point-to-point connections
        append the triple [departure, arrival, train id]
        to the sublist with key [origin, destination]
        in the hashset
for all sublists in the hashset
    for all connections A in sublist
        for all connections B in sublist
            if A.departure > B.departure and A.arrival < B.arrival
                print("A overtakes B")