how to traverse first neighbors and their relationships

Question

I guess this can be trivially achieved but can't figure it out. Is it possible to achieve the following in one traversal (Neo4j 1.9RC2): starting from a node, include all its first neighbors (depth 1) and include all links between it's neighbors (if any). The direction is irrelevant.

Here's a test scenario:

  +-+     +-+                 +-+
  |7+----->5|                 |4+------+
  +++     +-+-----------------+-+      |
   |        |                 |        |
   |        |      +--+       |        |
   |        +------|1 |-------+        |
  ++>              +-++               +-+     +-+
  |8|                |                |2+-----|6|
  +-+                +----------------+++     +-+
                                       |
                                       |
                                      +-+
                                      |3|
                                      +-+

starting from node 1, i want to include nodes 2,4 and 5 and relationships 2-4 and 4-5, but not 2-6 or 5-7. And the test fixture:

Node[] nodes = new Node[10];
Transaction tx = graphDb.beginTx();
try {
    for (int i = 1; i < 10; i++) {
        Node node = graphDb.createNode();
        node.setProperty("id", i);
        otuIdIndex.add(node, "id", i);
        nodes[i] = node;//nodes[0] is empty!
    }
    nodes[1].createRelationshipTo(nodes[2], RelTypes.CONNECTED_TO);
    nodes[1].createRelationshipTo(nodes[4], RelTypes.CONNECTED_TO);
    nodes[1].createRelationshipTo(nodes[5], RelTypes.CONNECTED_TO);
    nodes[2].createRelationshipTo(nodes[4], RelTypes.CONNECTED_TO);
    nodes[2].createRelationshipTo(nodes[6], RelTypes.CONNECTED_TO);
    nodes[3].createRelationshipTo(nodes[2], RelTypes.CONNECTED_TO);
    nodes[5].createRelationshipTo(nodes[4], RelTypes.CONNECTED_TO);
    nodes[7].createRelationshipTo(nodes[5], RelTypes.CONNECTED_TO);
    nodes[7].createRelationshipTo(nodes[8], RelTypes.CONNECTED_TO);
    tx.success();
} finally {
    tx.finish();
}

final TraversalDescription traversalDescription = Traversal.description().breadthFirst()
        .relationships(RelTypes.CONNECTED_TO, Direction.BOTH)
        .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL)
        .evaluator(Evaluators.toDepth(2))
        .evaluator(Evaluators.excludeStartPosition());
for (Path path : traversalDescription.traverse(nodes[1])) {
    System.out.println(path);
}

The output is:

(1)--[CONNECTED_TO,0]-->(2)
(1)--[CONNECTED_TO,1]-->(4)
(1)--[CONNECTED_TO,2]-->(5)
(1)--[CONNECTED_TO,0]-->(2)--[CONNECTED_TO,3]-->(4)
(1)--[CONNECTED_TO,0]-->(2)--[CONNECTED_TO,4]-->(6)
(1)--[CONNECTED_TO,0]-->(2)<--[CONNECTED_TO,5]--(3)
(1)--[CONNECTED_TO,1]-->(4)<--[CONNECTED_TO,6]--(5)
(1)--[CONNECTED_TO,2]-->(5)<--[CONNECTED_TO,7]--(7)

and what I'm trying to do is to exclude these three:

(1)--[CONNECTED_TO,0]-->(2)<--[CONNECTED_TO,5]--(3)
(1)--[CONNECTED_TO,0]-->(2)--[CONNECTED_TO,4]-->(6)
(1)--[CONNECTED_TO,2]-->(5)<--[CONNECTED_TO,6]--(7)

Lasse suggested the following cypher query http://console.neo4j.org/?id=3ihr7l:

start one=node:node_auto_index(name='One') 
match one-[r:R*1]->m, m-[s]-l--one 
return distinct s

which sort of does what I need but I'm wondering if this is doable with Traversal.

Answer 1

Ok, found one way of doing this, but it's way too slow, in a 200K nodes/700K relationships db it takes a second to load one network compared to 0.006sec for fromDepth(1).toDepth(1) evaluator (150 times factor):

final TraversalDescription traversalDescription = Traversal.description().breadthFirst()                                    
        .relationships(RelTypes.CONNECTED_TO, Direction.BOTH)                                                               
        .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL)                                                                         
        .evaluator(Evaluators.includeIfAcceptedByAny(new PathEvaluator() {                                                  
            private final Set<Long> firstNeighbors = new HashSet<Long>();                                                   
            @Override                                                                                                       
            public Evaluation evaluate(Path path, BranchState state) {                                                      
                if (path.length() == 0) {                                                                                    
                    return Evaluation.EXCLUDE_AND_CONTINUE;                                                                 
                } else if (path.length() == 1) {                                                                             
                    firstNeighbors.add(path.endNode().getId());                                                             
                    return Evaluation.INCLUDE_AND_CONTINUE;                                                                 
                } else if (path.length() == 2) {                                                                            
                    final Iterator<Node> iterator = path.nodes().iterator();                                                
                    iterator.next();//start node, just skip                                                                 
                    Node firstNeighbor = iterator.next();                                                                   
                    if (firstNeighbors.contains(path.endNode().getId()) && firstNeighbors.contains(firstNeighbor.getId())) {
                        return Evaluation.INCLUDE_AND_CONTINUE;                                                             
                    } else {                                                                                                
                        return Evaluation.EXCLUDE_AND_CONTINUE;                                                             
                    }                                                                                                       
                } else {                                                                                                    
                    return Evaluation.EXCLUDE_AND_PRUNE;                                                                    
                }                                                                                                           
            }                                                                                                               

            @Override                                                                                                       
            public Evaluation evaluate(Path path) {                                                                         
                return evaluate(path, null);                                                                                
            }                                                                                                               
        }));     

Update: tstorms suggested a faster query:

public class NeoTraversal {

public static void main(final String[] args) {
    final GraphDatabaseService db = new GraphDatabaseFactory()
            .newEmbeddedDatabaseBuilder("/neo4j")
            .loadPropertiesFromURL(NeoTraversal.class.getClassLoader().getResource("neo4j.properties"))
            .newGraphDatabase();
    final Set<Long> uniquePartnerRels = new HashSet<Long>();
    long startTime = System.currentTimeMillis();
    final Node start = db.getNodeById(36);
    for (final Path path : Traversal.description()
            .breadthFirst()
            .relationships(Rel.COOCCURS_WITH, Direction.BOTH)
            .uniqueness(Uniqueness.NODE_GLOBAL)
            .evaluator(Evaluators.atDepth(1))
            .traverse(start)) {
        Node partner = start.equals(path.startNode()) ? path.endNode() : path.startNode();
        for (final Path partnerPath : Traversal.description()
                .depthFirst()
                .relationships(Rel.COOCCURS_WITH, Direction.BOTH)
                .uniqueness(Uniqueness.RELATIONSHIP_PATH)
                .evaluator(Evaluators.atDepth(2))
                .evaluator(Evaluators.includeWhereEndNodeIs(start))
                .traverse(partner)) {
            uniquePartnerRels.add(partnerPath.relationships().iterator().next().getId());
        }
    }
    System.out.println("Execution time: " + (System.currentTimeMillis() - startTime));
    System.out.println(uniquePartnerRels.size());
}

static enum Rel implements RelationshipType {
    COOCCURS_WITH
}

}