Как вы моделируете Layover и Продолжительность путешествия на графике - PullRequest
Новая
       25

Как вы моделируете Layover и Продолжительность путешествия на графике

1 голос
/ 18 марта 2020

Мы создаем копию сайта amtrak.com и хотели бы реализовать алгоритм поиска для поиска путей между станцией A и станцией B.

В настоящее время мы не можем эффективно фильтровать параметры поиска на уровне графика. Например, две поездки, поездка 1 и поездка 2, которые go от станции A-> B -> C могут привести к (действительному, но неэффективному) результату: обратная поездка 1 из A-> B и переход к поездке 2 для B -> C.

Наша текущая модель выглядит следующим образом: 

class Route {
  int id
  List<Trip> trips
}

class Trip {
  int id
  List<Stop> stops
}

class Stop {
  String station
  Time arrival
  Time departure
  int sequence
}

В настоящее время мы используем JGraphT следующим образом: 

Graph<StationEntity, StopTimeEntityEdge> g = new SimpleDirectedGraph<>(StopTimeEntityEdge.class);
for (TripEntity trip : tripRepository.findAll()) {
  List<StopTimeEntity> stops = trip.getStops();
  for (int i = 0; i < stops.size(); i++) {
    g.addVertex(stops.get(i).getStation());
  }
  for (int i = 0; i < stops.size() - 1; i++) {
    g.addEdge(stops.get(i).getStation(), stops.get(i + 1).getStation(), new StopTimeEntityEdge(stops.get(i), stops.get(i + 1)));
  }
}
AllDirectedPaths<StationEntity, StopTimeEntityEdge> searchAlgorithm = new AllDirectedPaths<>(g);
List<GraphPath<StationEntity, StopTimeEntityEdge>> iPaths = searchAlgorithm.getAllPaths(fromStation, toStation, true, 9999);
return iPaths;

Полный исходный код можно увидеть здесь .

Эта проблема дополнительно обсуждается здесь , но у меня возникли некоторые трудности при построении расширенного графика.

...