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

До появления 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 ) );

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

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

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

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;
    }
}

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();
        }
    }
}

    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;
        }
    }

        // 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 nonStopTraversalDescription = db.traversalDescription()
                            .depthFirst()
                            .expand(nonStopExpander)
                            .evaluator(reachedDestinationEvaluator)
                            .uniqueness(Uniqueness.RELATIONSHIP_PATH);

            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);
            }