Если вы никогда не смотрели Firefly , остановите все, что вы делаете, и доберитесь до него, вы можете вернуться и прочитать этот пост позже. Хорошо, хорошо, где мы были. Светлячок. Серия начинается через несколько сотен лет после того, как люди начинают терраформировать новую звездную систему, и она следует за приключениями ренегатской команды Serenity, космического корабля класса «Светляк», работа которого состоит из грузовых пробегов или контрабанды, в то время как не удается держись подальше от неприятностей. В этой серии нет скоростных путешествий налегке, поэтому корабли не могут просто «искривляться», куда хотят. Вместо этого они путешествуют с планет и лун, обмениваясь грузом, заправляясь топливом и пытаясь зарабатывать на жизнь. Мы собираемся смоделировать « Стих » Firefly в Neo4j, и посмотрим, как мы можем найти маршруты для перемещения нашего незаконного груза из одного места в другое.
Вы можете посмотреть видео о том, как выглядит Стих здесь . Мы собираемся добавить несколько станций к нашим планетам и лунам. Они представляют космические станции, космические порты, зоны приземления и везде, где может приземлиться корабль, чтобы забрать и сбросить груз. Примером этого в сериале являются « Подслушивающие доки» , где экипаж подобрал Саймона Тэма (доктора), « Дериал Бук» (проповедника) и Лоуренса Добсона.(предупреждение спойлера: агент под прикрытием) в качестве оплаты пассажиров. Мы также собираемся добавить узлы с пометкой «Стыковка», которые представляют собой событие, когда корабль прибывает и затем покидает станцию. Эти стыковки связаны и следуют по маршруту, по которому будет следовать судно. Мы можем видеть время прибытия, отъезда и транзита. Наш груз может перемещаться из одного места в другое на одном корабле — если случится так, что он пройдет весь путь туда — но, скорее всего, он перейдет к другому на разных станциях по пути. Они представлены отношением Transhipment, которое также имеет свойство транзитного времени, которое сообщает нам, сколько времени занимает выгрузка, транспортировка и перегрузка груза с одной станции на другую. Перегрузки могут происходить только внутри планеты, луны или между лунами и планетами, вращающимися вокруг друг друга.
Используя стрелки, наша модель выглядит так:
Допустим, мы хотим перевезти реку Там в стазисе от планеты Лондиниум до луны Ариополис, вращающейся вокруг планеты Ариэль , и похоже, что маршруты между ними проходят через планету Сионон . Если вы вспомните ряд прошлых публикаций в блогах, моделирующих и просматривающих полеты , вы, возможно, помните, что мы можем сделать это в Neo4j, создав описание обхода., Мы можем начать с Londinium и найти все исходящие пути, пока не доберемся до Ariopolis. Мы также можем начать с Ариополиса и найти все входящие пути, пока не доберемся до Лондиниума. Но не лучше ли начать с Лондиниума и Ариополиса и попытаться встретиться посередине? Конечно, было бы, но для этого нам нужно описать специальное описание обхода в Neo4j, называемое двунаправленным описанием обхода .
Двунаправленное описание обхода может принимать два описания обхода. Один для начальной стороны нашего обхода и один для конечной стороны обхода. Однако он также может взять одно описание обхода и отразить их. Следуя нормальному пути от начала и обратному пути от конца. Я хочу показать вам немного сложный пример, поэтому мы будем использовать mirroredSides.
Одна вещь, которую я не показывал вам в предыдущих примерах обхода, это то, что наш обход может сохранять состояние . Мы будем использовать это состояние, чтобы отслеживать время в нашем обходе и избегать времени, уходящего в прошлое при обычном перемещении или в будущее при обратном. Он принимает два параметра, в нашем случае это будет самое раннее время, когда мы хотим уехать, и самое позднее время, когда мы хотим приехать.
InitialBranchState.State<Long> ibs = new InitialBranchState.State<>(
(Long)input.get("departure_long"),
(Long)input.get("arrival_long")
);Мы следуем путями с обоих концов, что происходит, когда они встречаются посередине в каком-то узле? Нам нужно оценить этот путь и убедиться, что он правильный. Нам не нужны стыковочные узлы с датами отправления и прибытия за пределами наших лимитов, поэтому мы создадим оценщик маршрутов с этими параметрами.
RouteEvaluator routeEvaluator = new RouteEvaluator(
(Long)input.get("departure_long"),
(Long)input.get("arrival_long")
);Ниже мы можем увидеть функцию оценки в нашем RouteEvaluator, которая исключает любые пути, которые нарушают наши ограничения:
public Evaluation evaluate(Path path) {
for (Node node: path.nodes()) {
Long nodeDeparture = (Long)node.getProperty("departure", departure);
Long nodeArrival = (Long)node.getProperty("arrival", arrival);
if (nodeDeparture < departure || nodeArrival > arrival) {
return Evaluation.EXCLUDE_AND_PRUNE;
}
}
return Evaluation.INCLUDE_AND_CONTINUE;
}Мы реализуем PathExpander (здесь он называется RouteExpander), но пока оставим это в покое и закончим создание нашего описания обхода и описания двунаправленного обхода. Наше описание прохождения будет отслеживать отношения, которые он видел на каждом пути, и гарантирует, что мы не будем преследовать свои собственные хвосты, сохраняя их уникальными:
RouteExpander routeExpander = new RouteExpander(
(long)input.get("arrival_long"),
(long)input.get("time_limit"));
TraversalDescription td = db.traversalDescription()
.breadthFirst()
.expand(routeExpander, ibs)
.uniqueness(Uniqueness.RELATIONSHIP_PATH);
BidirectionalTraversalDescription bidirtd = db.bidirectionalTraversalDescription()
.mirroredSides(td)
.collisionEvaluator(routeEvaluator);Заметьте, что мы выполняем этот обход шириной в первом направлении в режиме истинного двунаправленного поиска, но мы могли бы также пройти и в самой глубине. Хорошо, давайте вернемся к RouteExpander. Здесь происходит вся магия. Мы возьмем время прибытия в нашем конструкторе вместе с stopTime. На любом графике вы можете столкнуться с множеством возможных путей, поэтому мы используем stopTime, чтобы добавить ограничение времени к нашему поиску пути, которое гарантирует, что наше исследование пути не займет более X миллисекунд. Мы путешествуем от планет и лун к другим планетам и лунам, но мы не можем просто сбрасывать грузы случайно, мы используем станции, расположенные на этих планетах и лунах, поэтому в качестве первого шага мы найдем их на нашем пути. Как только мы добираемся до станции, мы можем проверить стыковки, связанные с ней, или можем перейти на другую станцию. Если бы мы сделали перевод,затем нам нужно добавить время трансфера к времени прибытия предыдущей стыковки, чтобы узнать, где мы находимся. Наконец, мы найдем док-станции, которые не приходят слишком поздно и отправляются после нашего текущего времени. Мы также должны сделать то же самое в обратном порядке. Итак, давайте посмотрим на это в обычном направлении:
public class RouteExpander implements PathExpander<Long> {
private long arrival;
private long stopTime;
public RouteExpander(long arrival, long stopTime) {
this.arrival = arrival;
this.stopTime = System.currentTimeMillis() + stopTime;
}
@Override
public Iterable<Relationship> expand(Path path, BranchState<Long> branchState) {
// Stop if we are over our time limit
if (System.currentTimeMillis() < stopTime) {
// We will start at a Moon or Planet, but need to get to a station
if ( path.endNode().hasLabel(Labels.Moon) || path.endNode().hasLabel(Labels.Planet)) {
return path.endNode().getRelationships(
Direction.INCOMING, RelationshipTypes.LOCATED_AT);
}
// When we reach a station, we need to continue to its dockings or other stations via transhipment.
if ( path.endNode().hasLabel(Labels.Station)) {
// If we transfered here, our new times should be our arrival + transit time
if (path.lastRelationship().isType(RelationshipTypes.TRANSHIPMENT)) {
Node lastDocking = null;
Iterator<Node> iterator = path.reverseNodes().iterator();
while (iterator.hasNext()) {
lastDocking = iterator.next();
if (lastDocking.hasLabel(Labels.Docking)) { break;}
}
Long previousArrival = (long)lastDocking.getProperty("arrival");
previousArrival += (long)path.lastRelationship().getProperty("transit_time");
branchState.setState(previousArrival);
}
return path.endNode().getRelationships(
RelationshipTypes.HAS_DOCKING,
RelationshipTypes.TRANSHIPMENT);
}
// Ignore any Dockings that arrive too late.
Long lastArrival = (long)path.endNode().getProperty("arrival", arrival);
if ( lastArrival <= arrival ) {
// Ignore any Transits that we cannot catch due to time.
Long lastDeparture = branchState.getState();
Long departure = (Long) path.endNode().getProperty("departure", lastDeparture);
if (departure >= lastDeparture) {
branchState.setState(departure);
return path.endNode().getRelationships(
RelationshipTypes.CONNECTED_TO,
RelationshipTypes.HAS_DOCKING);
}
}
}
return Collections.emptyList();
}В обратном методе мы делаем то же самое, но в обратном порядке (сюрприз!). Вы можете увидеть полный код этого класса на github .
Теперь мы можем наконец вызвать traverse для нашего двунаправленного обхода, проходящего в нашей начальной точке и конечной точке (которые являются узлами планеты и луны). Для каждого найденного пути мы будем собирать узлы вдоль маршрута и время в карту результатов. Обратите внимание, что я использую getAllProperties. Это довольно недавнее дополнение к API и настоятельно рекомендуется вместо того, чтобы получать по одному свойству за раз. Нам нужны даты отправления и прибытия из стыковочных узлов, а не со станции или планеты / луны, где мы можем оказаться, так что это выглядит немного забавно:
for (org.neo4j.graphdb.Path position : bidirtd.traverse(startingPoint, endingPoint)) {
HashMap<String, Object> result = new HashMap<>();
ArrayList<Map> steps = new ArrayList<>();
for (Node node : position.nodes()) {
Map<String, Object> vsidInfo = node.getAllProperties();
vsidInfo.put("label", node.getLabels().iterator().next().name());
steps.add(vsidInfo);
}
result.put("steps", steps);
result.put("departure_date", steps.get(2).get("departure_date"));
result.put("arrival_date", steps.get(steps.size() - 3).get("arrival_date"));
result.put("travel_time", (long)steps.get(steps.size() - 3).get("arrival")
- (long)steps.get(2).get("departure"));
results.add(result);
}Мы возьмем все наши результаты и отсортируем их с помощью RouteComparator, который сначала выберет кратчайший путь, а затем те, которые имеют самое короткое время прохождения, самое раннее прибытие, код стыковки отправления и, наконец, код стыковки прибытия для заказа на сортировку. Вы можете видеть этот класс RouteComparator на github .
Наконец, мы возьмем верхние пути X, основанные на параметре recordLimit.
return Response.ok().entity(
objectMapper.writeValueAsString(
results.subList(0,
Math.min(results.size(), recordLimit)
))).build();Как только мы настроим наше расширение и создадим некоторые примеры данных, мы можем запросить его следующим образом:
:POST /v1/service/query {
"from":"Londinium",
"to":"Sihnon",
"departure_date":"11/06/2215",
"arrival_date": "12/04/2215" }Наконец мы можем увидеть наши результаты:
[
{
"departure_date": "11/06/2215 12:00 PM",
"steps": [
{
"name": "Londinium",
"label": "Planet"
},
{
"name": "Aldik",
"label": "Station"
},
{
"code": "d1",
"arrival": 7758072000,
"departure_date": "11/06/2215 12:00 PM",
"departure": 7758158400,
"label": "Docking",
"arrival_date": "11/05/2215 12:00 PM"
},
{
"code": "d2",
"arrival": 7758244800,
"departure_date": "11/08/2215 12:00 PM",
"departure": 7758331200,
"label": "Docking",
"arrival_date": "11/07/2215 12:00 PM"
},
{
"name": "Lirerim",
"label": "Station"
},
{
"name": "Sihnon",
"label": "Planet"
}
],
"arrival_date": "11/07/2215 12:00 PM",
"travel_time": 86400
}
]Который выглядит как:
Если вы хотите увидеть полный исходный код , он как обычно на github. Взгляните на некоторые тесты для более сложных прохождений.
Возможно, вам не понадобится в ближайшее время переправлять контрабанду через солнечные системы, но, надеюсь, вы сможете связать пример с чем-то, над чем вы работаете. Traversal Framework является довольно мощным инструментом в Neo4j, узнать его , и вы будете в состоянии убить проблемы с мозгом .
У каждого поклонника Firefly есть что-то, что они любят в шоу. Я собираюсь завершить эту запись в блоге моей любимой сценой из Firefly.
Саймон: Я пытаюсь изложить это как можно деликатнее … Откуда я знаю, что ты не убьешь меня во сне?
Мал: Ты не знаешь меня, сынок, поэтому позволь мне однажды объяснить тебе это: если я когда-нибудь тебя убью, ты проснешься. Вы встретитесь со мной и будете вооружены.
Саймон: Ты всегда такой сентиментальный?
Мал: У меня был хороший день.
Саймон: На вас был Альянс, преступники и дикари … Половина людей на корабле были ранены или ранены, включая вас самих, и вы укрываете известных беглецов.
Мал: Ну, мы все еще летим.
Саймон: Это не так много.
Mal: Этого достаточно.