Статьи

Поиск рейса с помощью Neo4j Traversal API

Снимок экрана 2015-08-30 в 2.21.07 утра

До появления Cypher, если вы хотите описать обход графов в Neo4j, вы должны использовать Java API-интерфейс Traversal Framework . API-интерфейс Traversal — это одна из многих скрытых жемчужин Neo4j, и сегодня мы рассмотрим его подробнее. Обход графа — это путешествие в путешествие. У всех поездок есть отправная точка (или точки), так что это первое, что мы должны сделать, выяснить, где на графике мы начинаем. Это может быть один или несколько узлов, но они отправятся в путешествие по тем же правилам, так что будет проще, если это будет только один узел или узлы одного и того же «типа».

Затем мы должны построить набор правил или описание, которому будут следовать узлы. Первое решение — Заказ . Должен ли узел следовать по пути до конца как можно дальше (сначала в глубину), или он должен исследовать каждый путь по одному шагу за раз (в ширину). Подумайте об этом, у вас есть развилка на дороге, идете ли вы до конца одного пути, или вы делаете один шаг на одном пути, возвращаетесь, а затем делаете один шаг на другом пути, затем два шаги по первому пути, затем назад и два шага по второму пути и т. д.? Вы можете сказать, что следующий путь до конца будет проще (менее требователен к памяти) и в большинстве случаев это предпочтительный порядок.

Следующее решение, которое вы должны принять, — это уникальность . Хотите ли вы иметь возможность посещать узлы несколько раз, отношения многократно, вам все равно? При использовании Cypher вы не можете сопоставить шаблон, который повторяется в одном и том же отношении несколько раз, это обеспечивает уникальность отношения. Если вы не занимаетесь анализом графиков, это то, чем вы хотите заниматься большую часть времени.

Какие типы отношений вы должны пройти, чтобы добраться до пункта назначения? Это роль расширителей пути . Возвращаясь к нашей аналогии, вы можете перейти по дорогам из желтого кирпича, но не из красного кирпича. Может быть, вы хотите прогуляться по одному типу отношений для первого шага, а другой тип отношений — для второго шага.

У всех путешествий есть конец, но не все они успешны. Оценщик решает , если мы достигаем действительный конец обхода, или если мы должны продолжать идти, или если мы направились вниз плохой путь , и нужно просто остановиться. Это также может сказать нам, когда мы зашли достаточно далеко, и не должны предпринимать дальнейших шагов.

Как это выглядит в коде? Давайте взглянем:


TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

Эквивалент в Cypher будет выглядеть примерно так:


MATCH (n)<-[:KNOWS|LIKES*5]-()

Но что, если вы позволили пройти отношения KNOWS в любом направлении, как в примере с документацией?


TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

Это было бы намного сложнее, чтобы попытаться написать на Cypher. Заметьте, как мы останавливаемся на глубине 5? Это общий оценщик, который встроен в фреймворк. Есть дюжина или около того на выбор, и вы можете смешивать и сочетать их. Заметьте, как «.relationships» вызывается дважды? Вы можете использовать этот вспомогательный метод для построения PathExpander . В качестве альтернативы вы можете использовать PathExpanderBuilder, чтобы сделать несколько интересных, таких как:


PathExpanderBuilder
        .allTypesAndDirections()
        .remove(RelationshipTypes.LIKES)
        .add(RelationshipTypes.LIKES, Direction.INCOMING) 

Это ограничит PathExpander, чтобы он следовал только отношениям Direction.INCOMING для RelationshipTypes.LIKES, в то же время следуя любому другому типу отношений в любом направлении. Попробуйте это в Cypher. Вы также можете полностью настроить свои оценщики и расширители, написав их самостоятельно. Давайте посмотрим, как мы применили бы то, что видели, для создания механизма планирования полетов в Neo4j.

Наш сервис собирает список стартовых аэропортов, а не только один, потому что некоторые столичные районы предоставляют пассажирам несколько вариантов аэропортов. В Чикаго у нас есть O’Hare и Midway. Это будет требовать список конечных аэропортов (по той же причине). Это потребует даты полета. Список авиакомпаний с высоким приоритетом (для случаев использования часто летающих пассажиров и обратных рейсов). При желании может потребоваться ограничение на количество записей, которые он может вернуть, или максимальное время, необходимое для сбора этих результатов.

У нас есть модель из последнего поста в блоге , поэтому вернитесь к ней, если вы ее еще не видели. Поэтому первое, что мы хотим сделать, — это создать собственный оценщик, который собирает действительные маршруты полетов (представленные в виде путей в нашем обходе).

Это работает, беря список потенциальных мест назначения и максимальной длины. Он оценивает каждый шаг по пути, и если это не та длина, которая нам нужна, он просто исключает этот путь как слишком короткий и продолжается. Если мы окажемся в узле, который не является AirportDay, мы исключим его и продолжим. Если мы окажемся в узле AirportDay, то мы проверим, является ли это одним из направлений, которое мы хотим. Если это так, то мы включаем этот путь и идем другим путем. Если нет, мы исключаем этот путь и идем попробовать другой.


public class ReachedDestinationAtEvaluator implements Evaluator {
    private ArrayList<String> destinations;
    private int length;

    public ReachedDestinationAtEvaluator(ArrayList<String> destinations, int length) {
        this.destinations = destinations;
        this.length = length;
    }

    @Override
    public Evaluation evaluate(Path path) {
        if (path.length() < length) {
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }

        Node lastNode = path.endNode();
        if (!lastNode.hasLabel(Labels.AirportDay)){
            return Evaluation.EXCLUDE_AND_CONTINUE;
        } else if (destinations.contains( ((String)lastNode.getProperty("key")).substring(0,3) )) {
            return Evaluation.INCLUDE_AND_PRUNE;
        }
        return Evaluation.EXCLUDE_AND_PRUNE;
    }
}

Мы будем использовать несколько расширителей в нашем запросе. Мы создаем NonStopExpander путем реализации PathExpander. Конструктор выбирает пункты назначения, которые мы хотим достичь, Авиалинии, которые мы собираемся попробовать, и stopTime, чтобы прекратить проход, если у нас заканчивается время. Метод, который описывает, как пройти по графику — это «развернуть». Мы хотим вернуть коллекцию отношений. Один из способов сделать это — использовать длину пути и использовать его, чтобы указать, какие отношения следует вернуть. Если мы зашли в тупик, мы вернем пустой список примерно так:


public class NonStopExpander implements PathExpander {
    protected ArrayList<String> destinations;
    protected RelationshipType[] relationshipTypes;
    protected long stopTime;

    public NonStopExpander(ArrayList<String> destinations,  RelationshipType[] relationshipTypes, long stopTime) {
        this.destinations = new ArrayList<>();
        this.relationshipTypes = new RelationshipType[0];
        this.stopTime = System.currentTimeMillis();
    }

    @Override
    public Iterable<Relationship> expand(Path path, BranchState state) {
        if (System.currentTimeMillis() < stopTime) {
            switch (path.length()) {
                case 0:
                    return path.endNode().getRelationships(Direction.OUTGOING, RelationshipTypes.HAS_DESTINATION);
                case 1: {
                    Node lastNode = path.endNode();
                    if (destinations.contains((String) lastNode.getProperty("code"))) {
                        return path.endNode().getRelationships(Direction.OUTGOING, relationshipTypes);
                    } else {
                        return Collections.emptyList();
                    }
                }
                 case 2:
                 case 3: {
                     return path.endNode().getRelationships(Direction.OUTGOING, relationshipTypes);
                 }
                default:
                    return Collections.emptyList();
            }
        } else {
            return Collections.emptyList();
        }
    }
}

Я выложу изображение модели ниже, чтобы было легче следить. В path.length «0» мы находимся в нашей начальной точке, поэтому мы пересекаем отношения HAS_DESTINATION. Когда-то наш путь теперь имеет длину 1, поэтому мы проверяем код пункта назначения, чтобы убедиться, что он совпадает с пунктом назначения. Если это не так, мы сдаемся, в противном случае мы продолжаем два прыжка в наших отношениях AirlineFlight до тех пор, пока не достигнем узла AirportDay, и оценщик не вступит во владение.

тип полета

Итак, как нам получить эти отношения AirlineFlight? Мы создадим узел с метаданными с именем свойства «Авиакомпании». Мы создадим группу авиакомпаний и подключим их к этой «метаноде». Затем мы можем запросить на графике имена отношений AirlineFlight, которые мы должны пройти.

Снимок экрана 2015-09-04 в 2.18.58 PM

Код ниже. Мы будем называть это при первом запросе, и каждый раз, когда авиакомпания добавляется / удаляется или обновляется из нашей системы.


    public static void setFlightTypes(@Context GraphDatabaseService db) {
        Set<RelationshipType> flightTypes = new HashSet<>();
        try (Transaction tx = db.beginTx()) {
            Node airlines = db.findNode(Labels.Metadata, "name", "Airlines");
            if (airlines!=null) {
                for (Relationship r : airlines.getRelationships(Direction.INCOMING, RelationshipTypes.IS_AIRLINE)) {
                    final Node carrier = r.getStartNode();
                    final String flightType = carrier.getProperty("code") + "_FLIGHT";
                    flightTypes.add(DynamicRelationshipType.withName(flightType));
                }
            }
            Service.flightTypes = flightTypes;
        }
    }

Чтобы получить заказ на основе запроса, мы создаем ListOrderedSet и сначала добавляем запрос авиакомпаниям с высоким приоритетом, а затем всем остальным. Дублированные записи не изменят порядок.


        // Add High Priority Airlines to be checked first, and then add the rest
        Set<RelationshipType> orderedFlightTypes = new ListOrderedSet<>();
        for ( String airline : (ArrayList<String>)input.get("airlines")) {
            orderedFlightTypes.add(DynamicRelationshipType.withName(airline + "_FLIGHT"));
        }

        // Adding full list of Airlines, duplicates do not affect original ordering
        orderedFlightTypes.addAll(flightTypes);

Теперь мы можем создать наш расширитель:


        NonStopExpander nonStopExpander = new NonStopExpander(
                (ArrayList<String>)input.get("to"),
                flightTypes.toArray(new RelationshipType[flightTypes.size()]),
                (long)input.get("time_limit")
        );

… а также наше TraversalDescription:


TraversalDescription nonStopTraversalDescription = db.traversalDescription()
                            .depthFirst()
                            .expand(nonStopExpander)
                            .evaluator(reachedDestinationEvaluator)
                            .uniqueness(Uniqueness.RELATIONSHIP_PATH);

Наконец, мы можем вызвать метод «traverse» нашего TraversalDescription и добавить свойства полета в наш массив результатов, который мы конвертируем в JSON и отправляем обратно в конце.


            for (org.neo4j.graphdb.Path position : td.traverse(departureAirportDay)) {
                ArrayList<HashMap> flights = new ArrayList<>();
                Long distance = 0L;
                for (Node flight : position.nodes()) {
                    if (flight.hasLabel(Labels.Flight)) {
                        HashMap flightInfo = new HashMap();
                        for (String property : flight.getPropertyKeys()) {
                            flightInfo.put(property, flight.getProperty(property));
                        }
                        flights.add(flightInfo);
                        distance += ((Number) flight.getProperty("distance")).longValue();
                    }
                }

                    result.put("flights", flights);
                    result.put("distance", distance);
                    results.add(result);
            }

We do this a few more times for direct, one stop and two stop flights. I’ve split them up for my sanity, for performance reasons (remember it goes depth first) and to allow the query to limit the number of stops that are allowed on the itinerary. The complete source code is available on github as always. So make sure your hand luggage is securely stowed, your seats are upright, tray tables put away, your phones are in airplane mode, your seat-belts fastened and have a nice flight.