core/src/main/java/com/orientechnologies/orient/core/sql/parser/OMatchStatement.java
private List<EdgeTraversal> getTopologicalSortedSchedule(Map<String, Long> estimatedRootEntries, Pattern pattern) {
    List<EdgeTraversal> resultingSchedule = new ArrayList<EdgeTraversal>();
    Map<String, Set<String>> remainingDependencies = getDependencies(pattern);
    Set<PatternNode> visitedNodes = new HashSet<PatternNode>();
    Set<PatternEdge> visitedEdges = new HashSet<PatternEdge>();

    // Sort the possible root vertices in order of estimated size, since we want to start with a small vertex set.
    List<OPair<Long, String>> rootWeights = new ArrayList<OPair<Long, String>>();
    for (Map.Entry<String, Long> root : estimatedRootEntries.entrySet()) {
      rootWeights.add(new OPair<Long, String>(root.getValue(), root.getKey()));
    }
    Collections.sort(rootWeights);

    // Add the starting vertices, in the correct order, to an ordered set.
    Set<String> remainingStarts = new LinkedHashSet<String>();
    for (OPair<Long, String> item : rootWeights) {
      remainingStarts.add(item.getValue());
    }
    // Add all the remaining aliases after all the suggested start points.
    for (String alias : pattern.aliasToNode.keySet()) {
      if (!remainingStarts.contains(alias)) {
        remainingStarts.add(alias);
      }
    }

    while (resultingSchedule.size() < pattern.numOfEdges) {
      // Start a new depth-first pass, adding all nodes with satisfied dependencies.
      // 1. Find a starting vertex for the depth-first pass.
      PatternNode startingNode = null;
      List<String> startsToRemove = new ArrayList<String>();
      for (String currentAlias : remainingStarts) {
        PatternNode currentNode = pattern.aliasToNode.get(currentAlias);

        if (visitedNodes.contains(currentNode)) {
          // If a previous traversal already visited this alias, remove it from further consideration.
          startsToRemove.add(currentAlias);
        } else if (remainingDependencies.get(currentAlias).isEmpty()) {
          // If it hasn't been visited, and has all dependencies satisfied, visit it.
          startsToRemove.add(currentAlias);
          startingNode = currentNode;
          break;
        }
      }
      remainingStarts.removeAll(startsToRemove);

      if (startingNode == null) {
        // We didn't manage to find a valid root, and yet we haven't constructed a complete schedule.
        // This means there must be a cycle in our dependency graph, or all dependency-free nodes are optional.
        // Therefore, the query is invalid.
        throw new OCommandExecutionException("This query contains MATCH conditions that cannot be evaluated, "
            + "like an undefined alias or a circular dependency on a $matched condition.");
      }

      // 2. Having found a starting vertex, traverse its neighbors depth-first,
      //    adding any non-visited ones with satisfied dependencies to our schedule.
      updateScheduleStartingAt(startingNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
    }

    if (resultingSchedule.size() != pattern.numOfEdges) {
      throw new AssertionError("Incorrect number of edges: " + resultingSchedule.size() + " vs " + pattern.numOfEdges);
    }

    return resultingSchedule;
  }
private List<EdgeTraversal> getTopologicalSortedSchedule(Map<String, Long> estimatedRootEntries, Pattern pattern) {
    List<EdgeTraversal> resultingSchedule = new ArrayList<EdgeTraversal>();
    Map<String, Set<String>> remainingDependencies = getDependencies(pattern);
    Set<PatternNode> visitedNodes = new HashSet<PatternNode>();
    Set<PatternEdge> visitedEdges = new HashSet<PatternEdge>();

    // Sort the possible root vertices in order of estimated size, since we want to start with a small vertex set.
    List<OPair<Long, String>> rootWeights = new ArrayList<OPair<Long, String>>();
    for (Map.Entry<String, Long> root : estimatedRootEntries.entrySet()) {
      rootWeights.add(new OPair<Long, String>(root.getValue(), root.getKey()));
    }
    Collections.sort(rootWeights);

    // Add the starting vertices, in the correct order, to an ordered set.
    Set<String> remainingStarts = new LinkedHashSet<String>();
    for (OPair<Long, String> item : rootWeights) {
      remainingStarts.add(item.getValue());
    }
    // Add all the remaining aliases after all the suggested start points.
    for (String alias : pattern.aliasToNode.keySet()) {
      if (!remainingStarts.contains(alias)) {
        remainingStarts.add(alias);
      }
    }

    while (resultingSchedule.size() < pattern.numOfEdges) {
      // Start a new depth-first pass, adding all nodes with satisfied dependencies.
      // 1. Find a starting vertex for the depth-first pass.
      PatternNode startingNode = null;
      List<String> startsToRemove = new ArrayList<String>();
      for (String currentAlias : remainingStarts) {
        PatternNode currentNode = pattern.aliasToNode.get(currentAlias);

        if (visitedNodes.contains(currentNode)) {
          // If a previous traversal already visited this alias, remove it from further consideration.
          startsToRemove.add(currentAlias);
        } else if (remainingDependencies.get(currentAlias).isEmpty()) {
          // If it hasn't been visited, and has all dependencies satisfied, visit it.
          startsToRemove.add(currentAlias);
          startingNode = currentNode;
          break;
        }
      }
      remainingStarts.removeAll(startsToRemove);

      if (startingNode == null) {
        // We didn't manage to find a valid root, and yet we haven't constructed a complete schedule.
        // This means there must be a cycle in our dependency graph, or all dependency-free nodes are optional.
        // Therefore, the query is invalid.
        throw new OCommandExecutionException("This query contains MATCH conditions that cannot be evaluated, "
            + "like an undefined alias or a circular dependency on a $matched condition.");
      }

      // 2. Having found a starting vertex, traverse its neighbors depth-first,
      //    adding any non-visited ones with satisfied dependencies to our schedule.
      updateScheduleStartingAt(startingNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
    }

    if (resultingSchedule.size() != pattern.numOfEdges) {
      throw new AssertionError("Incorrect number of edges: " + resultingSchedule.size() + " vs " + pattern.numOfEdges);
    }

    return resultingSchedule;
  }
private List < EdgeTraversal > getTopologicalSortedSchedule ( Map < String , Long > estimatedRootEntries , Pattern pattern ) { List < EdgeTraversal > resultingSchedule = new ArrayList < EdgeTraversal > ( ) ; Map < String , Set < String > > remainingDependencies = getDependencies ( pattern ) ; Set < PatternNode > visitedNodes = new HashSet < PatternNode > ( ) ; Set < PatternEdge > visitedEdges = new HashSet < PatternEdge > ( ) ; // Sort the possible root vertices in order of estimated size, since we want to start with a small vertex set. List < OPair < Long , String > > rootWeights = new ArrayList < OPair < Long , String > > ( ) ; for ( Map . Entry < String , Long > root : estimatedRootEntries . entrySet ( ) ) { rootWeights . add ( new OPair < Long , String > ( root . getValue ( ) , root . getKey ( ) ) ) ; } Collections . sort ( rootWeights ) ; // Add the starting vertices, in the correct order, to an ordered set. Set < String > remainingStarts = new LinkedHashSet < String > ( ) ; for ( OPair < Long , String > item : rootWeights ) { remainingStarts . add ( item . getValue ( ) ) ; } // Add all the remaining aliases after all the suggested start points. for ( String alias : pattern . aliasToNode . keySet ( ) ) { if ( ! remainingStarts . contains ( alias ) ) { remainingStarts . add ( alias ) ; } } while ( resultingSchedule . size ( ) < pattern . numOfEdges ) { // Start a new depth-first pass, adding all nodes with satisfied dependencies. // 1. Find a starting vertex for the depth-first pass. PatternNode startingNode = null ; List < String > startsToRemove = new ArrayList < String > ( ) ; for ( String currentAlias : remainingStarts ) { PatternNode currentNode = pattern . aliasToNode . get ( currentAlias ) ; if ( visitedNodes . contains ( currentNode ) ) { // If a previous traversal already visited this alias, remove it from further consideration. startsToRemove . add ( currentAlias ) ; } else if ( remainingDependencies . get ( currentAlias ) . isEmpty ( ) ) { // If it hasn't been visited, and has all dependencies satisfied, visit it. startsToRemove . add ( currentAlias ) ; startingNode = currentNode ; break ; } } remainingStarts . removeAll ( startsToRemove ) ; if ( startingNode == null ) { // We didn't manage to find a valid root, and yet we haven't constructed a complete schedule. // This means there must be a cycle in our dependency graph, or all dependency-free nodes are optional. // Therefore, the query is invalid. throw new OCommandExecutionException ( "This query contains MATCH conditions that cannot be evaluated, " + "like an undefined alias or a circular dependency on a $matched condition." ) ; } // 2. Having found a starting vertex, traverse its neighbors depth-first, //    adding any non-visited ones with satisfied dependencies to our schedule. updateScheduleStartingAt ( startingNode , visitedNodes , visitedEdges , remainingDependencies , resultingSchedule ) ; } if ( resultingSchedule . size ( ) != pattern . numOfEdges ) { throw new AssertionError ( "Incorrect number of edges: " + resultingSchedule . size ( ) + " vs " + pattern . numOfEdges ) ; } return resultingSchedule ; }
sort edges in the order they will be matched
sort edges in the order they will be matched