Java 类org.neo4j.graphdb.traversal.TraversalDescription 实例源码

private Traverser getPatternMatch(Node startNode, final List<String> patterns, final List<NodeLabel> nodeLabels, final List<LinkLabel> linkLabels) {
    TraversalDescription td = database.traversalDescription()
        .depthFirst()
        .evaluator( new Evaluator() {
            public Evaluation evaluate( final org.neo4j.graphdb.Path path ) {
                if ( path.length() == 0 ) {
                    return Evaluation.EXCLUDE_AND_CONTINUE;
                }
                boolean isToken = path.endNode().hasLabel(NodeLabel.WordToken);
                boolean included = isToken && (path.length() == 1 || nodeHasAnnotation(path.endNode(), linkLabels.get(path.length() - 1), patterns.get(path.length() - 1)));
                boolean continued = path.length() < patterns.size();
                return Evaluation.of( included, continued );
            }
        } )
        .relationships(LinkLabel.NEXT, Direction.OUTGOING)
        .relationships(LinkLabel.HAS_TYPE, Direction.INCOMING)
        .relationships(LinkLabel.HAS_LEMMA, Direction.INCOMING)
        .relationships(LinkLabel.HAS_POS_TAG, Direction.INCOMING)
        .relationships(LinkLabel.HAS_HEAD, Direction.INCOMING);
    return td.traverse(startNode);
}

public static List<String> getHypernyms(String cui){
  List<String> hypers = new ArrayList<>();

  try ( Transaction tx = graphDb.beginTx() ){
    TraversalDescription td = graphDb.traversalDescription()
        .breadthFirst()
        .relationships(RelReader.RelTypes.ISA, Direction.OUTGOING)
        .evaluator(Evaluators.excludeStartPosition());

    Node cuiNode = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui);
    if(cuiNode == null) return hypers;

    Traverser traverser = td.traverse(cuiNode);
    for(Path path : traverser){
      hypers.add(path.endNode().getProperty(RelReader.CUI_PROPERTY).toString());
    }
    tx.success();
  }
  return hypers;
}

public static List<String> getHyponyms(String cui){
  List<String> hypos = new ArrayList<>();

  try ( Transaction tx = graphDb.beginTx() ){
    TraversalDescription td = graphDb.traversalDescription()
        .breadthFirst()
        .relationships(RelReader.RelTypes.ISA, Direction.INCOMING)
        .evaluator(Evaluators.excludeStartPosition());

    Node cuiNode = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui);
    if(cuiNode == null) return hypos;

    Traverser traverser = td.traverse(cuiNode);
    for(Path path : traverser){
      hypos.add(path.endNode().getProperty(RelReader.CUI_PROPERTY).toString());
    }
    tx.success();
  }
  return hypos;    
}

public static boolean isa(String cui1, String cui2){
  boolean match=false;
  try ( Transaction tx = graphDb.beginTx() ){
    Node cui1Node = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui1);
    Node cui2Node = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui2);
    if(cui1Node == null || cui2Node == null) return match;

    TraversalDescription td = graphDb.traversalDescription()
        .breadthFirst()
        .relationships(RelReader.RelTypes.ISA, Direction.OUTGOING)
        .evaluator(Evaluators.excludeStartPosition())
        .evaluator(Evaluators.includeWhereEndNodeIs(cui2Node));

    Traverser traverser = td.traverse(cui1Node);
    if(traverser.iterator().hasNext()){
      match = true;
    }
    tx.success();
  }
  return match;
}

public static int minDistance(String cui1, String cui2){
  int distance = -1;
  try ( Transaction tx = graphDb.beginTx() ){
    Node cui1Node = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui1);
    Node cui2Node = graphDb.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, cui2);
    if(cui1Node == null || cui2Node == null) return distance;

    TraversalDescription td = graphDb.traversalDescription()
        .breadthFirst()
        .relationships(RelReader.RelTypes.ISA, Direction.OUTGOING)
        .evaluator(Evaluators.excludeStartPosition())
        .evaluator(Evaluators.includeWhereEndNodeIs(cui2Node));

    Traverser traverser = td.traverse(cui1Node);
    for(Path path : traverser){
      int len = path.length();
      if(distance == -1 || len < distance){
        distance = len;
      }
    }
    tx.success();
  }
  return distance;
}

@Test
public void testRelReader() throws IOException{

  RelReader reader = new RelReader(neo4jLocation);
  reader.batchBuildGraph(new File("my_test_umls/"), "CtakesAllTuis.txt", "SNOMEDCT_US");
  GraphDatabaseService db = new GraphDatabaseFactory().newEmbeddedDatabase(new File(neo4jLocation));

  try ( Transaction tx = db.beginTx() ){
    TraversalDescription td = db.traversalDescription()
        .breadthFirst()
        .relationships(RelReader.RelTypes.ISA, Direction.INCOMING)
        .evaluator(Evaluators.excludeStartPosition());

    Node cuiNode = db.findNode(RelReader.DictLabels.Concept, RelReader.CUI_PROPERTY, "C0007102");
    Assert.assertNotNull(cuiNode);
    Traverser traverser = td.traverse(cuiNode);
    for(Path path : traverser){
      System.out.println("At depth " + path.length() + " => " + path.endNode().getProperty("cui"));
    }
  }
  db.shutdown();
}

@Test
public void shouldReturnExpectedResultForUnboundedPathLengthSuccess() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 0,
                    Step.UNLIMITED));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(0, 1);
    expectedPathLengthCounts.put(1, 1);
    expectedPathLengthCounts.put(2, 1);
    expectedPathLengthCounts.put(3, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForBoundedRangePathLengthSuccess() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 0, 2));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(0, 1);
    expectedPathLengthCounts.put(1, 1);
    expectedPathLengthCounts.put(2, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForBranchedGraphSuccess() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post),\n"
            + "(comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post)"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 1, 2),
            Step.one(node().hasLabel(Labels.Post)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(2, 1);
    expectedPathLengthCounts.put(3, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

public static org.neo4j.graphdb.Traverser traverse( Node node, Order traversalOrder,
        StopEvaluator stopEvaluator,
        ReturnableEvaluator returnableEvaluator,
        Object... relationshipTypesAndDirections )
{
    assertNotNull( traversalOrder, "order" );
    assertNotNull( stopEvaluator, "stop evaluator" );
    assertNotNull( returnableEvaluator, "returnable evaluator" );

    if ( relationshipTypesAndDirections.length % 2 != 0
         || relationshipTypesAndDirections.length == 0 )
    {
        throw new IllegalArgumentException();
    }
    TraverserImpl result = new TraverserImpl();
    TraversalDescription description = traversal( result, traversalOrder,
            stopEvaluator, returnableEvaluator );
    description = description.expand( toExpander( relationshipTypesAndDirections ) );
    result.iter = description.traverse( node ).iterator();
    return result;
}

private static TraversalDescription traversal( TraverserImpl traverser,
        Order order, StopEvaluator stopEvaluator,
        ReturnableEvaluator returnableEvaluator )
{
    TraversalDescription description = BASE_DESCRIPTION;
    switch ( order )
    {
    case BREADTH_FIRST:
        description = description.breadthFirst();
        break;
    case DEPTH_FIRST:
        description = description.depthFirst();
        break;

    default:
        throw new IllegalArgumentException( "Onsupported traversal order: "
                                            + order );
    }

    description = description.prune( new Pruner( traverser, stopEvaluator ) );
    description = description.filter( new Filter( traverser,
            returnableEvaluator ) );

    return description;
}

@Description("com.maxdemarzi.hiphop(node) | Return Paths starting from node alternating pattern")
@Procedure(name = "com.maxdemarzi.hiphop", mode = Mode.READ)
public Stream<PathResult> hiphop( @Name("startNode") Node startNode) {
    TraversalDescription myTraversal = db.traversalDescription()
            .depthFirst()
            .expand(hipHopExpander)
            .evaluator(hiphopEvaluator);

    return  myTraversal.traverse(startNode).stream().map(PathResult::new);
}

@Description("com.maxdemarzi.hiphopdistinct(node) | Return Paths starting from node alternating pattern")
@Procedure(name = "com.maxdemarzi.hiphopdistinct", mode = Mode.READ)
public Stream<NodeResult> hiphopDistinct( @Name("startNode") Node startNode) {
    TraversalDescription myTraversal = db.traversalDescription()
            .depthFirst()
            .expand(hipHopExpander)
            .evaluator(hiphopEvaluator);

    return  myTraversal.traverse(startNode).nodes().stream().distinct().map(NodeResult::new);
}

@POST
public Response energization(String body, @Context GraphDatabaseService db) throws IOException {
    HashMap input = Validators.getValidEquipmentIds(body);

    Set<Node> startingEquipment = new HashSet<>();
    Set results = new HashSet<>();
    ArrayList<Long> skip = new ArrayList<>();

    try (Transaction tx = db.beginTx()) {
        ((Collection) input.get("ids")).forEach((id) -> startingEquipment.add(db.findNode(Labels.Equipment, "equipment_id", id)));

        if (startingEquipment.isEmpty()) {
            throw Exceptions.equipmentNotFound;
        }

        startingEquipment.forEach(bus -> {
            InitialBranchState.State<Double> ibs;
            ibs = new InitialBranchState.State<>((Double) bus.getProperty("voltage", 999.0), 0.0);
            TraversalDescription td = db.traversalDescription()
                    .depthFirst()
                    .expand(expander, ibs)
                    .uniqueness(Uniqueness.NODE_GLOBAL)
                    .evaluator(evaluator);

            for (org.neo4j.graphdb.Path position : td.traverse(bus)) {
                Node endNode = position.endNode();
                if (!skip.contains(endNode.getId())) {
                    results.add(position.endNode().getProperty("equipment_id"));
                    skip.add(endNode.getId());
                }

                endNode.setProperty("Energized", true);
            }
        });
        tx.success();
    }
    return  Response.ok().entity(objectMapper.writeValueAsString(results)).build();
}

/***
 * @param parent
 * @param relationship
 * @param traverseEquivalentEdges
 * @return the entailment
 */
public Collection<Node> getEntailment(Node parent, DirectedRelationshipType relationship,
    boolean traverseEquivalentEdges) {
  Set<Node> entailment = new HashSet<>();
  TraversalDescription description = graphDb.traversalDescription().depthFirst()
      .relationships(relationship.getType(), relationship.getDirection())
      .evaluator(Evaluators.fromDepth(0)).evaluator(Evaluators.all());
  if (traverseEquivalentEdges) {
    description = description.relationships(OwlRelationships.OWL_EQUIVALENT_CLASS);
  }
  for (Path path : description.traverse(parent)) {
    entailment.add(path.endNode());
  }
  return entailment;
}

public Traverser getTraverser(String task, Direction direction){
    TraversalDescription td = Traversal.description()
            .breadthFirst()
            .relationships( TaskRelations.DEPENDS_ON, direction )
            .evaluator(Evaluators.excludeStartPosition());
    return td.traverse(getNode(task));
}

/**
 * filters must start with @NodeFilterDescriptor and alternate between @NodeFilterDescriptor
 * and @RelationshipFilterDescriptor
 * 
 * @param td
 * @param steps
 * @return copy of td, with @StepsEvaluator and @StepsExpander attached
 */
public final TraversalDescription build( TraversalDescription td, Step... steps )
{
    List<StepExpander> stepExpanders = new ArrayList<StepExpander>();
    List<StepEvaluator> stepEvaluators = new ArrayList<StepEvaluator>();

    for ( int i = 0; i < steps.length - 1; i++ )
    {
        Step step = steps[i];

        if ( step.minRepetitions() == Step.UNLIMITED )
            throw new StepsException( StepsExceptionType.MIN_REPETITIONS_MUST_BE_FINITE_POSITIVE_INT );

        if ( step.minRepetitions() > step.maxRepetitions() )
            throw new StepsException( StepsExceptionType.MIN_REPETITIONS_MUST_BE_LOWER_THAN_MAX_REPETITIONS );

        if ( null == step.relationshipDescriptor() )
            throw new StepsException( StepsExceptionType.ONLY_LAST_STEP_MAY_OMIT_RELATIONSHIP_DESCRIPTOR );

        stepEvaluators.add( buildStepEvaluator( step.nodeDescriptor(), step.minRepetitions(),
                step.maxRepetitions(), false ) );
        stepExpanders.add( buildStepExpander( step.relationshipDescriptor() ) );
    }

    Step lastStep = steps[steps.length - 1];
    stepEvaluators.add( buildStepEvaluator( lastStep.nodeDescriptor(), lastStep.minRepetitions(),
            lastStep.maxRepetitions(), true ) );
    // if last step only contains node descriptor expander not necessary
    if ( false == ( lastStep.relationshipDescriptor() == null ) )
        stepExpanders.add( buildStepExpander( lastStep.relationshipDescriptor() ) );

    StepsExpander ex = new StepsExpander( stepExpanders.toArray( new StepExpander[stepExpanders.size()] ) );
    StepsEvaluator ev = new StepsEvaluator( stepEvaluators.toArray( new StepEvaluator[stepEvaluators.size()] ) );
    return td.evaluator( ev ).expand( ex, INITIAL_BRANCH_STATE );
}

@Test
public void shouldReturnExpectedResultForPathLength0MatchSuccess() {
    long startNodeId = createGraph("CREATE (post:Post)\n" + "RETURN id(post) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.one(node().hasLabel(Labels.Post)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(0, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForPathLength0MatchFailure() {
    long startNodeId = createGraph("CREATE (post:Post)\n" + "RETURN id(post) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.one(node().hasLabel(Labels.Comment)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForPathLength1MatchSuccess() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Post)\n" + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(
            baseTraversalDescription,
            // Steps
            Step.one(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING)),
            Step.one(node().hasLabel(Labels.Post)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(1, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForPathLength1MatchFailure() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Post)\n" + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(
            baseTraversalDescription,
            // Steps
            Step.one(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING)),
            Step.one(node().hasLabel(Labels.Comment)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForPathLength2MatchSuccess() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyExact(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 1),
            Step.one(node().hasLabel(Labels.Post)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(2, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForPathLength2MatchFailure() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyExact(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 2),
            Step.one(node().hasLabel(Labels.Comment)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldReturnExpectedResultForUnboundedPathLengthFailure() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Post),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 0,
                    Step.UNLIMITED));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldNotWorkWhenDirectionsAreReversed() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post),\n"
            + "(comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post)"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.INCOMING), 1, 2),
            Step.one(node().hasLabel(Labels.Post)));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

@Test
public void shouldWorkForPatternGraph() {
    long startNodeId = createGraph("CREATE (comment:Comment)-[:REPLY_OF]->(:Comment)-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(post1:Post),\n"
            + "(post1)-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(:Post),\n"
            + "(post1)-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(:Post)\n"
            + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.manyRange(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 0, 1),
            Step.manyRange(node().hasLabel(Labels.Post),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 2, 3));

    /*
    -------C1---------===============P2============
    (C)-[R]->(C)-[R]->(P)-[R]->(p:P)-[R]->(P)-[R]->(P)
                      ===============P2============
                      ===============P3=====================
                               (p:P)-[R]->(P)-[R]->(P)-[R]->(P)
     */

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    expectedPathLengthCounts.put(4, 2);
    expectedPathLengthCounts.put(5, 2);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

void assertThatExpectedNumberAndLengthOfPathsAreDiscovered(GraphDatabaseService db, long startNodeId,
                                                           TraversalDescription td, Map<Integer, Integer> expectedPathLengthCounts) {
    boolean exceptionThrown = false;
    try (Transaction tx = db.beginTx()) {
        Node startNode = db.getNodeById(startNodeId);
        Map<Integer, Integer> actualPathLengthCounts = pathLengthCounts(td.traverse(startNode));
        assertThat(actualPathLengthCounts, equalTo(expectedPathLengthCounts));
        tx.success();
    } catch (Exception e) {
        e.printStackTrace();
        exceptionThrown = true;
    }
    assertThat(exceptionThrown, is(false));
}

public TraversalDescription order( BranchOrderingPolicy selector )
{
    if ( this.branchSelector == selector )
    {
        return this;
    }
    return new TraversalDescriptionImpl( expander, uniqueness, uniquenessParameter,
            evaluator, selector );
}

public TraversalDescription expand(RelationshipExpander expander)
{
    if ( expander.equals( this.expander ) )
    {
        return this;
    }
    return new TraversalDescriptionImpl( Traversal.expander( expander ), uniqueness,
            uniquenessParameter, evaluator, branchSelector );
}

public static ResourceIterable<Path> create(final List<Node> roots, final TraversalDescription td) {
  return new ResourceIterable<Path>() {
    @Override
    public ResourceIterator<Path> iterator() {
      return new MultiRootPathIterator(roots, td);
    }
  };
}

public static ResourceIterable<Node> create(final List<Node> roots, final TraversalDescription td) {
  return new ResourceIterable<Node>() {
    @Override
    public ResourceIterator<Node> iterator() {
      return new MultiRootNodeIterator(roots, td);
    }
  };
}

private void assertTraversalSizes(TraversalDescription td, int child1, int child1Syn, int child2, int child2Syn, int root, int bas) {
  assertEquals("child1 traversal wrong", child1, Iterators.count(td.traverse(this.child1).iterator()));
  assertEquals("child1Syn traversal wrong", child1Syn, Iterators.count(td.traverse(this.child1Syn).iterator()));
  assertEquals("child2 traversal wrong", child2, Iterators.count(td.traverse(this.child2).iterator()));
  assertEquals("child2Syn traversal wrong", child2Syn, Iterators.count(td.traverse(this.child2Syn).iterator()));
  assertEquals("root traversal wrong", root, Iterators.count(td.traverse(this.root).iterator()));
  assertEquals("bas traversal wrong", bas, Iterators.count(td.traverse(this.bas).iterator()));

}

private Traverser getFriends(final Node person) {
    TraversalDescription td = graphDb.traversalDescription().breadthFirst().relationships(RelTypes.KNOWS, Direction.OUTGOING)
            .evaluator(Evaluators.excludeStartPosition());
    return td.traverse(person);
}

private Traverser findHackers(final Node startNode) {
    TraversalDescription td = graphDb.traversalDescription().breadthFirst().relationships(RelTypes.CODED_BY, Direction.OUTGOING)
            .relationships(RelTypes.KNOWS, Direction.OUTGOING).evaluator(Evaluators.includeWhereLastRelationshipTypeIs(RelTypes.CODED_BY));
    return td.traverse(startNode);
}

private Long collectFlights(ArrayList<HashMap> results, Node departureAirportDay, TraversalDescription td, Double score, HashMap input, Long minDistance) {
    int recordLimit = (Integer)input.get("record_limit");
    // Stop collecting records if I already reached the requested limit
    if(results.size() >= recordLimit) {
        return minDistance;
    }

    for (org.neo4j.graphdb.Path position : td.traverse(departureAirportDay)) {
        // We check this twice because I want to stop collecting records before I even begin traversing
        // if I have reached the limit, or as soon as I reach the limit while traversing
        if(results.size() < recordLimit) {
            HashMap<String, Object> result = new HashMap<>();
            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();
                }
            }
            // Update our minimum distance as we go along
            if (distance < minDistance) {
                minDistance = distance;
            }

            // Add the flight to our result set for now, but it may be filtered out again if we find a
            // smaller minimum  distance while traversing
            if (distance < 2.5 * minDistance) {
                result.put("flights", flights);
                result.put("score", score);
                result.put("distance", distance);
                results.add(result);
            }
        } else {
            break;
        }
    }

    return minDistance;
}

@Override
public void run() {
  logger.info("Starting clique merge");

  Transaction tx = graphDb.beginTx();
  ResourceIterable<Node> allNodes = graphDb.getAllNodes();
  int size = Iterators.size(allNodes.iterator());
  tx.success();
  tx.close();

  logger.info(size + " nodes left to process");

  tx = graphDb.beginTx();
  TraversalDescription traversalDescription =
      graphDb.traversalDescription().breadthFirst().uniqueness(Uniqueness.NODE_GLOBAL);
  for (RelationshipType rel : relationships) {
    traversalDescription = traversalDescription.relationships(rel, Direction.BOTH);
  }

  Set<Long> processedNodes = new HashSet<Long>();

  for (Node baseNode : allNodes) {

    size -= 1;

    if (size % 100000 == 0) {
      logger.info(size + " nodes left to process");
    }

    if (size % batchCommitSize == 0) {
      logger.fine("Node batch commit");
      tx.success();
      tx.close();
      tx = graphDb.beginTx();
    }

    logger.fine("Processing Node - " + baseNode.getProperty(NodeProperties.IRI));

    if (!processedNodes.contains(baseNode.getId())) {
      // Keep a list of equivalentNodes
      List<Node> clique = new ArrayList<Node>();
      for (Node node : traversalDescription.traverse(baseNode).nodes()) {
        logger.fine("-- " + node.getProperty(NodeProperties.IRI));
        clique.add(node);
        processedNodes.add(node.getId());
      }

      logger.fine("clique size: " + clique.size());
      if (clique.size() == 1) {
        Node defactoLeader = clique.get(0);
        markAsCliqueLeader(defactoLeader);
      } else {
        Node leader = electCliqueLeader(clique, prefixLeaderPriority);
        markAsCliqueLeader(leader);
        clique.remove(leader); // keep only the peasants
        moveEdgesToLeader(leader, clique, tx);
        ensureLabel(leader, clique);
      }

    }

  }

  tx.success();
  tx.close();
}

/**
 * Create a reachability index on a graph.
 * 
 * @throws InterruptedException
 */
public void createIndex(Predicate<Node> nodePredicate) throws InterruptedException {
  if (indexExists()) {
    throw new IllegalStateException(
        "Reachability index already exists. Drop it first and then recreate it.");
  }

  long startTime = System.currentTimeMillis();
  Set<Entry<Long, Integer>> hopCoverages = getHopCoverages(nodePredicate);
  logger.info(format("Calculated hop coverage in %d second(s)",
      TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis() - startTime)));

  InMemoryReachabilityIndex inMemoryIndex = new InMemoryReachabilityIndex();

  TraversalDescription incomingTraversal = graphDb.traversalDescription().breadthFirst()
      .uniqueness(Uniqueness.NODE_GLOBAL).expand(new DirectionalPathExpander(Direction.INCOMING))
      .evaluator(new ReachabilityEvaluator(inMemoryIndex, Direction.INCOMING, nodePredicate));

  TraversalDescription outgoingTraversal = graphDb.traversalDescription().breadthFirst()
      .uniqueness(Uniqueness.NODE_GLOBAL).expand(new DirectionalPathExpander(Direction.OUTGOING))
      .evaluator(new ReachabilityEvaluator(inMemoryIndex, Direction.OUTGOING, nodePredicate));

  startTime = System.currentTimeMillis();

  try (Transaction tx = graphDb.beginTx()) {
    for (Entry<Long, Integer> coverage : hopCoverages) {

      Node workingNode = graphDb.getNodeById(coverage.getKey());

      if (coverage.getValue() < 0) {
        inMemoryIndex.put(coverage.getKey(), new InOutList());
      } else {
        InOutListTraverser incomingListTaverser = new InOutListTraverser(incomingTraversal,
            workingNode);
        incomingListTaverser.start();

        InOutListTraverser outgoingListTaverser = new InOutListTraverser(outgoingTraversal,
            workingNode);
        outgoingListTaverser.start();

        incomingListTaverser.join();
        outgoingListTaverser.join();
      }

    }
    tx.success();
  }

  logger.info("Built an InMemoryReachability index in " + ((System.currentTimeMillis() - startTime) / 1000)
      + " sec(s).");
  commitIndexToGraph(inMemoryIndex);
  logger.info("Reachability index created.");
}

InOutListTraverser(TraversalDescription td, Node startNode) {
  checkNotNull(startNode, "startNode must not be null.");
  this.traversalDescription = td;
  this.startNode = startNode;
}

@Test
public void complexExample() {
    long startNodeId = createGraph(

            "CREATE (comment:Comment)-[:REPLY_OF]->(:Comment {content : 'hi'})-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(post:Post),\n"

                    + "(post)-[:REPLY_OF]->(:Post {title : 'non-things'})-[:REPLY_OF]->(:Post),\n"

                    + "(post)-[:REPLY_OF]->(:Post {title : 'things'})-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(:Post)\n"

                    + "RETURN id(comment) AS id");

    TraversalDescription td = stepsBuilder.build(baseTraversalDescription,
            // Steps
            Step.one(node().hasLabel(Labels.Comment),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING)),

            Step.one(node().hasLabel(Labels.Comment).propertyEquals("content", "hi"),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING)),

            Step.manyExact(node().hasLabel(Labels.Post),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 1),

            Step.one(node().hasLabel(Labels.Post).propertyEquals("title", "things"),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING)),

            Step.manyRange(node().hasLabel(Labels.Post),
                    relationship().hasType(RelTypes.REPLY_OF).hasDirection(Direction.OUTGOING), 0,
                    Step.UNLIMITED));

    Map<Integer, Integer> expectedPathLengthCounts = new HashMap<Integer, Integer>();
    /*
    (comment:Comment)-[:REPLY_OF]->(:Comment {content : 'hi'})-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(post:Post)
    (post)-[:REPLY_OF]->(:Post {title : 'things'})-[:REPLY_OF]->(:Post)
     */
    expectedPathLengthCounts.put(5, 1);
    /*
    (comment:Comment)-[:REPLY_OF]->(:Comment {content : 'hi'})-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(post:Post)
    (post)-[:REPLY_OF]->(:Post {title : 'things'})-[:REPLY_OF]->(:Post)-[:REPLY_OF]->(:Post)
     */
    expectedPathLengthCounts.put(6, 1);
    assertThatExpectedNumberAndLengthOfPathsAreDiscovered(db, startNodeId, td, expectedPathLengthCounts);
}

public TraversalDescription prune( PruneEvaluator pruning )
{
    return evaluator( pruning == PruneEvaluator.NONE ? Evaluators.all() :
            new WrappedPruneEvaluator( pruning ) );
}