core/src/main/java/com/orientechnologies/orient/core/sql/parser/OMatchStatement.java
private void updateScheduleStartingAt(PatternNode startNode, Set<PatternNode> visitedNodes, Set<PatternEdge> visitedEdges,
      Map<String, Set<String>> remainingDependencies, List<EdgeTraversal> resultingSchedule) {
    // OrientDB requires the schedule to contain all edges present in the query, which is a stronger condition
    // than simply visiting all nodes in the query. Consider the following example query:
    //     MATCH {
    //         class: A,
    //         as: foo
    //     }.in() {
    //         as: bar
    //     }, {
    //         class: B,
    //         as: bar
    //     }.out() {
    //         as: foo
    //     } RETURN $matches
    // The schedule for the above query must have two edges, even though there are only two nodes and they can both
    // be visited with the traversal of a single edge.
    //
    // To satisfy it, we obey the following for each non-optional node:
    // - ignore edges to neighboring nodes which have unsatisfied dependencies;
    // - for visited neighboring nodes, add their edge if it wasn't already present in the schedule, but do not
    //   recurse into the neighboring node;
    // - for unvisited neighboring nodes with satisfied dependencies, add their edge and recurse into them.
    visitedNodes.add(startNode);
    for (Set<String> dependencies : remainingDependencies.values()) {
      dependencies.remove(startNode.alias);
    }

    Map<PatternEdge, Boolean> edges = new LinkedHashMap<PatternEdge, Boolean>();
    for (PatternEdge outEdge : startNode.out) {
      edges.put(outEdge, true);
    }
    for (PatternEdge inEdge : startNode.in) {
      edges.put(inEdge, false);
    }

    for (Map.Entry<PatternEdge, Boolean> edgeData : edges.entrySet()) {
      PatternEdge edge = edgeData.getKey();
      boolean isOutbound = edgeData.getValue();
      PatternNode neighboringNode = isOutbound ? edge.in : edge.out;

      if (!remainingDependencies.get(neighboringNode.alias).isEmpty()) {
        // Unsatisfied dependencies, ignore this neighboring node.
        continue;
      }

      if (visitedNodes.contains(neighboringNode)) {
        if (!visitedEdges.contains(edge)) {
          // If we are executing in this block, we are in the following situation:
          // - the startNode has not been visited yet;
          // - it has a neighboringNode that has already been visited;
          // - the edge between the startNode and the neighboringNode has not been scheduled yet.
          //
          // The isOutbound value shows us whether the edge is outbound from the point of view of the startNode.
          // However, if there are edges to the startNode, we must visit the startNode from an already-visited
          // neighbor, to preserve the validity of the traversal. Therefore, we negate the value of isOutbound
          // to ensure that the edge is always scheduled in the direction from the already-visited neighbor
          // toward the startNode. Notably, this is also the case when evaluating "optional" nodes -- we always
          // visit the optional node from its non-optional and already-visited neighbor.
          //
          // The only exception to the above is when we have edges with "while" conditions. We are not allowed
          // to flip their directionality, so we leave them as-is.
          boolean traversalDirection;
          if (startNode.optional || edge.item.isBidirectional()) {
            traversalDirection = !isOutbound;
          } else {
            traversalDirection = isOutbound;
          }

          visitedEdges.add(edge);
          resultingSchedule.add(new EdgeTraversal(edge, traversalDirection));
        }
      } else if (!startNode.optional) {
        // If the neighboring node wasn't visited, we don't expand the optional node into it, hence the above check.
        // Instead, we'll allow the neighboring node to add the edge we failed to visit, via the above block.
        if (visitedEdges.contains(edge)) {
          // Should never happen.
          throw new AssertionError("The edge was visited, but the neighboring vertex was not: " + edge + " " + neighboringNode);
        }

        visitedEdges.add(edge);
        resultingSchedule.add(new EdgeTraversal(edge, isOutbound));
        updateScheduleStartingAt(neighboringNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
      }
    }
  }
private void updateScheduleStartingAt(PatternNode startNode, Set<PatternNode> visitedNodes, Set<PatternEdge> visitedEdges,
      Map<String, Set<String>> remainingDependencies, List<EdgeTraversal> resultingSchedule) {
    // OrientDB requires the schedule to contain all edges present in the query, which is a stronger condition
    // than simply visiting all nodes in the query. Consider the following example query:
    //     MATCH {
    //         class: A,
    //         as: foo
    //     }.in() {
    //         as: bar
    //     }, {
    //         class: B,
    //         as: bar
    //     }.out() {
    //         as: foo
    //     } RETURN $matches
    // The schedule for the above query must have two edges, even though there are only two nodes and they can both
    // be visited with the traversal of a single edge.
    //
    // To satisfy it, we obey the following for each non-optional node:
    // - ignore edges to neighboring nodes which have unsatisfied dependencies;
    // - for visited neighboring nodes, add their edge if it wasn't already present in the schedule, but do not
    //   recurse into the neighboring node;
    // - for unvisited neighboring nodes with satisfied dependencies, add their edge and recurse into them.
    visitedNodes.add(startNode);
    for (Set<String> dependencies : remainingDependencies.values()) {
      dependencies.remove(startNode.alias);
    }

    Map<PatternEdge, Boolean> edges = new LinkedHashMap<PatternEdge, Boolean>();
    for (PatternEdge outEdge : startNode.out) {
      edges.put(outEdge, true);
    }
    for (PatternEdge inEdge : startNode.in) {
      edges.put(inEdge, false);
    }

    for (Map.Entry<PatternEdge, Boolean> edgeData : edges.entrySet()) {
      PatternEdge edge = edgeData.getKey();
      boolean isOutbound = edgeData.getValue();
      PatternNode neighboringNode = isOutbound ? edge.in : edge.out;

      if (!remainingDependencies.get(neighboringNode.alias).isEmpty()) {
        // Unsatisfied dependencies, ignore this neighboring node.
        continue;
      }

      if (visitedNodes.contains(neighboringNode)) {
        if (!visitedEdges.contains(edge)) {
          // If we are executing in this block, we are in the following situation:
          // - the startNode has not been visited yet;
          // - it has a neighboringNode that has already been visited;
          // - the edge between the startNode and the neighboringNode has not been scheduled yet.
          //
          // The isOutbound value shows us whether the edge is outbound from the point of view of the startNode.
          // However, if there are edges to the startNode, we must visit the startNode from an already-visited
          // neighbor, to preserve the validity of the traversal. Therefore, we negate the value of isOutbound
          // to ensure that the edge is always scheduled in the direction from the already-visited neighbor
          // toward the startNode. Notably, this is also the case when evaluating "optional" nodes -- we always
          // visit the optional node from its non-optional and already-visited neighbor.
          //
          // The only exception to the above is when we have edges with "while" conditions. We are not allowed
          // to flip their directionality, so we leave them as-is.
          boolean traversalDirection;
          if (startNode.optional || edge.item.isBidirectional()) {
            traversalDirection = !isOutbound;
          } else {
            traversalDirection = isOutbound;
          }

          visitedEdges.add(edge);
          resultingSchedule.add(new EdgeTraversal(edge, traversalDirection));
        }
      } else if (!startNode.optional) {
        // If the neighboring node wasn't visited, we don't expand the optional node into it, hence the above check.
        // Instead, we'll allow the neighboring node to add the edge we failed to visit, via the above block.
        if (visitedEdges.contains(edge)) {
          // Should never happen.
          throw new AssertionError("The edge was visited, but the neighboring vertex was not: " + edge + " " + neighboringNode);
        }

        visitedEdges.add(edge);
        resultingSchedule.add(new EdgeTraversal(edge, isOutbound));
        updateScheduleStartingAt(neighboringNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
      }
    }
  }
Start a depth-first traversal from the starting node, adding all viable unscheduled edges and vertices.

@param startNode             the node from which to start the depth-first traversal
@param visitedNodes          set of nodes that are already visited (mutated in this function)
@param visitedEdges          set of edges that are already visited and therefore don't need to be scheduled (mutated in this
function)
@param remainingDependencies dependency map including only the dependencies that haven't yet been satisfied (mutated in this
function)
@param resultingSchedule     the schedule being computed i.e. appended to (mutated in this function)