0
# Traversal and Path Finding
1

2
Graph traversal framework providing programmatic path finding, relationship filtering, and bidirectional traversal with customizable evaluation criteria and path expansion strategies for exploring graph structures.
3

4
## Capabilities
5

6
### Traversal Description
7

8
Interface for describing how to perform graph traversals with configurable evaluation rules and relationship filtering.
9

10
```java { .api }
11
/**
12
 * Describes how to perform graph traversals
13
 */
14
public interface TraversalDescription {
15
    
16
    /**
17
     * Specify which relationships to follow during traversal
18
     * @param relationshipType Type of relationships to follow
19
     * @return Modified traversal description
20
     */
21
    TraversalDescription relationships(RelationshipType relationshipType);
22
    
23
    /**
24
     * Specify relationships and direction to follow
25
     * @param relationshipType Type of relationships to follow
26
     * @param direction Direction to traverse relationships
27
     * @return Modified traversal description
28
     */
29
    TraversalDescription relationships(RelationshipType relationshipType, Direction direction);
30
    
31
    /**
32
     * Use depth-first traversal strategy
33
     * @return Modified traversal description
34
     */
35
    TraversalDescription depthFirst();
36
    
37
    /**
38
     * Use breadth-first traversal strategy
39
     * @return Modified traversal description
40
     */
41
    TraversalDescription breadthFirst();
42
    
43
    /**
44
     * Set the maximum depth for traversal
45
     * @param depth Maximum depth to traverse
46
     * @return Modified traversal description
47
     */
48
    TraversalDescription evaluator(Evaluator evaluator);
49
    
50
    /**
51
     * Set path evaluator to control traversal behavior
52
     * @param evaluator Path evaluator
53
     * @return Modified traversal description
54
     */
55
    TraversalDescription evaluator(PathEvaluator<Path> evaluator);
56
    
57
    /**
58
     * Set the path expander for relationship traversal
59
     * @param expander Path expander
60
     * @return Modified traversal description
61
     */
62
    TraversalDescription expand(PathExpander<Path> expander);
63
    
64
    /**
65
     * Set uniqueness strategy for nodes and relationships
66
     * @param uniqueness Uniqueness strategy
67
     * @return Modified traversal description
68
     */
69
    TraversalDescription uniqueness(Uniqueness uniqueness);
70
    
71
    /**
72
     * Start traversal from the specified node
73
     * @param startNode Starting node for traversal
74
     * @return Traverser for executing the traversal
75
     */
76
    Traverser traverse(Node startNode);
77
    
78
    /**
79
     * Start traversal from multiple starting nodes
80
     * @param startNodes Starting nodes for traversal
81
     * @return Traverser for executing the traversal
82
     */
83
    Traverser traverse(Node... startNodes);
84
}
85
```
86

87
**Usage Examples:**
88

89
```java
90
import org.neo4j.graphdb.traversal.*;
91
import org.neo4j.graphdb.Direction;
92
import static org.neo4j.graphdb.traversal.Evaluators.*;
93

94
try (Transaction tx = graphDb.beginTx()) {
95
    Node startNode = tx.findNode(Label.label("Person"), "name", "Alice");
96
    
97
    // Simple depth-first traversal
98
    TraversalDescription td = tx.traversalDescription()
99
        .depthFirst()
100
        .relationships(RelationshipType.withName("FRIENDS"), Direction.OUTGOING)
101
        .evaluator(toDepth(3));
102
    
103
    for (Path path : td.traverse(startNode)) {
104
        Node endNode = path.endNode();
105
        System.out.println("Found friend: " + endNode.getProperty("name") + 
106
                          " at depth " + path.length());
107
    }
108
    
109
    // Breadth-first traversal with multiple relationship types
110
    TraversalDescription td2 = tx.traversalDescription()
111
        .breadthFirst()
112
        .relationships(RelationshipType.withName("FRIENDS"))
113
        .relationships(RelationshipType.withName("COLLEAGUES"))
114
        .evaluator(toDepth(2))
115
        .uniqueness(Uniqueness.NODE_GLOBAL);
116
    
117
    for (Node node : td2.traverse(startNode).nodes()) {
118
        System.out.println("Connected person: " + node.getProperty("name"));
119
    }
120
    
121
    tx.commit();
122
}
123
```
124

125
### Traverser Interface
126

127
Interface for executing graph traversals and accessing traversal results.
128

129
```java { .api }
130
/**
131
 * Executes graph traversals
132
 */
133
public interface Traverser extends Iterable<Path> {
134
    
135
    /**
136
     * Get all nodes found during traversal
137
     * @return Iterable of nodes
138
     */
139
    Iterable<Node> nodes();
140
    
141
    /**
142
     * Get all relationships traversed during traversal
143
     * @return Iterable of relationships
144
     */
145
    Iterable<Relationship> relationships();
146
    
147
    /**
148
     * Get all paths found during traversal
149
     * @return Iterable of paths (same as iterator())
150
     */
151
    Iterable<Path> paths();
152
    
153
    /**
154
     * Get iterator over paths
155
     * @return Iterator over paths
156
     */
157
    @Override
158
    Iterator<Path> iterator();
159
}
160
```
161

162
### Path Evaluators
163

164
Interfaces and implementations for controlling traversal behavior and filtering paths.
165

166
```java { .api }
167
/**
168
 * Evaluates paths during traversal to control continuation and inclusion
169
 */
170
public interface PathEvaluator<T> {
171
    
172
    /**
173
     * Evaluate a path and return evaluation result
174
     * @param path Path to evaluate
175
     * @return Evaluation result
176
     */
177
    Evaluation evaluate(Path path);
178
}
179

180
/**
181
 * Simple evaluator interface for backward compatibility
182
 */
183
public interface Evaluator extends PathEvaluator<Path> {
184
    /**
185
     * Evaluate a path
186
     * @param path Path to evaluate
187
     * @return Evaluation result
188
     */
189
    @Override
190
    Evaluation evaluate(Path path);
191
}
192

193
/**
194
 * Evaluation result indicating whether to include path and continue traversal
195
 */
196
public enum Evaluation {
197
    /** Include this path in results and continue traversal */
198
    INCLUDE_AND_CONTINUE,
199
    
200
    /** Include this path in results but don't continue traversal */
201
    INCLUDE_AND_PRUNE,
202
    
203
    /** Don't include this path but continue traversal */
204
    EXCLUDE_AND_CONTINUE,
205
    
206
    /** Don't include this path and don't continue traversal */
207
    EXCLUDE_AND_PRUNE
208
}
209
```
210

211
**Usage Examples:**
212

213
```java
214
// Custom path evaluator
215
PathEvaluator<Path> customEvaluator = new PathEvaluator<Path>() {
216
    @Override
217
    public Evaluation evaluate(Path path) {
218
        Node endNode = path.endNode();
219
        
220
        // Only include paths ending at Person nodes
221
        if (!endNode.hasLabel(Label.label("Person"))) {
222
            return Evaluation.EXCLUDE_AND_CONTINUE;
223
        }
224
        
225
        // Stop at depth 4
226
        if (path.length() >= 4) {
227
            return Evaluation.INCLUDE_AND_PRUNE;
228
        }
229
        
230
        // Include young people and continue
231
        Integer age = (Integer) endNode.getProperty("age", 0);
232
        if (age < 30) {
233
            return Evaluation.INCLUDE_AND_CONTINUE;
234
        }
235
        
236
        // Exclude older people but continue traversal
237
        return Evaluation.EXCLUDE_AND_CONTINUE;
238
    }
239
};
240

241
// Use custom evaluator
242
TraversalDescription td = tx.traversalDescription()
243
    .breadthFirst()
244
    .relationships(RelationshipType.withName("KNOWS"))
245
    .evaluator(customEvaluator);
246

247
for (Path path : td.traverse(startNode)) {
248
    Node person = path.endNode();
249
    System.out.println("Young person found: " + person.getProperty("name"));
250
}
251
```
252

253
### Built-in Evaluators
254

255
Factory class providing common path evaluators for typical traversal scenarios.
256

257
```java { .api }
258
/**
259
 * Factory for common path evaluators
260
 */
261
public final class Evaluators {
262
    
263
    /**
264
     * Evaluator that includes all paths up to a maximum depth
265
     * @param depth Maximum depth to traverse
266
     * @return Path evaluator
267
     */
268
    public static PathEvaluator<Path> toDepth(int depth);
269
    
270
    /**
271
     * Evaluator that includes paths from a minimum depth
272
     * @param depth Minimum depth to include
273
     * @return Path evaluator
274
     */
275
    public static PathEvaluator<Path> fromDepth(int depth);
276
    
277
    /**
278
     * Evaluator that includes paths within a depth range
279
     * @param minDepth Minimum depth (inclusive)
280
     * @param maxDepth Maximum depth (inclusive)
281
     * @return Path evaluator
282
     */
283
    public static PathEvaluator<Path> includingDepths(int minDepth, int maxDepth);
284
    
285
    /**
286
     * Evaluator that excludes start node from results
287
     * @return Path evaluator
288
     */
289
    public static PathEvaluator<Path> excludeStartPosition();
290
    
291
    /**
292
     * Evaluator that includes all paths
293
     * @return Path evaluator
294
     */
295
    public static PathEvaluator<Path> all();
296
    
297
    /**
298
     * Evaluator that returns at specific depth only
299
     * @param depth Exact depth to return
300
     * @return Path evaluator
301
     */
302
    public static PathEvaluator<Path> atDepth(int depth);
303
}
304
```
305

306
### Path Expanders
307

308
Interfaces and implementations for controlling how relationships are expanded during traversal.
309

310
```java { .api }
311
/**
312
 * Controls how relationships are expanded during traversal
313
 */
314
public interface PathExpander<STATE> {
315
    
316
    /**
317
     * Expand from a path to get next relationships
318
     * @param path Current path
319
     * @return Iterable of relationships to explore
320
     */
321
    Iterable<Relationship> expand(Path path, BranchState<STATE> state);
322
    
323
    /**
324
     * Reverse this path expander
325
     * @return Reversed path expander
326
     */
327
    PathExpander<STATE> reverse();
328
}
329

330
/**
331
 * Factory for common path expanders
332
 */
333
public final class PathExpanders {
334
    
335
    /**
336
     * Create expander for all relationships
337
     * @return Path expander
338
     */
339
    public static PathExpander<Path> allTypesAndDirections();
340
    
341
    /**
342
     * Create expander for specific relationship types and directions
343
     * @param types Array of relationship types and directions
344
     * @return Path expander
345
     */
346
    public static PathExpander<Path> forTypesAndDirections(RelationshipType... types);
347
    
348
    /**
349
     * Create expander for outgoing relationships of specific types
350
     * @param types Relationship types
351
     * @return Path expander
352
     */
353
    public static PathExpander<Path> forTypeAndDirection(RelationshipType type, Direction direction);
354
    
355
    /**
356
     * Create expander that filters by relationship properties
357
     * @param baseExpander Base expander to filter
358
     * @param filter Property filter
359
     * @return Filtered path expander
360
     */
361
    public static PathExpander<Path> forConstantDirectionWithTypes(
362
        Direction direction, RelationshipType... types);
363
}
364
```
365

366
### Bidirectional Traversal
367

368
Interface for bidirectional traversal providing collision detection and optimized path finding.
369

370
```java { .api }
371
/**
372
 * Bidirectional traversal configuration
373
 */
374
public interface BidirectionalTraversalDescription {
375
    
376
    /**
377
     * Set the start side traversal description
378
     * @param startSide Traversal description for start side
379
     * @return Modified bidirectional traversal description
380
     */
381
    BidirectionalTraversalDescription startSide(TraversalDescription startSide);
382
    
383
    /**
384
     * Set the end side traversal description
385
     * @param endSide Traversal description for end side
386
     * @return Modified bidirectional traversal description
387
     */
388
    BidirectionalTraversalDescription endSide(TraversalDescription endSide);
389
    
390
    /**
391
     * Set collision evaluator for detecting path intersections
392
     * @param collisionEvaluator Collision evaluator
393
     * @return Modified bidirectional traversal description
394
     */
395
    BidirectionalTraversalDescription collisionEvaluator(
396
        PathEvaluator<Path> collisionEvaluator);
397
    
398
    /**
399
     * Set side selector for controlling alternation between sides
400
     * @param sideSelector Side selector
401
     * @return Modified bidirectional traversal description
402
     */
403
    BidirectionalTraversalDescription sideSelector(SideSelector sideSelector);
404
    
405
    /**
406
     * Find paths between start and end nodes
407
     * @param start Start node
408
     * @param end End node
409
     * @return Iterable of paths found
410
     */
411
    Iterable<Path> traverse(Node start, Node end);
412
}
413
```
414

415
**Advanced Traversal Examples:**
416

417
```java
418
// Complex traversal with multiple constraints
419
try (Transaction tx = graphDb.beginTx()) {
420
    Node alice = tx.findNode(Label.label("Person"), "name", "Alice");
421
    
422
    // Find all reachable people within 3 hops, excluding blocked relationships
423
    PathExpander<Path> expander = new PathExpander<Path>() {
424
        @Override
425
        public Iterable<Relationship> expand(Path path, BranchState<Path> state) {
426
            List<Relationship> validRels = new ArrayList<>();
427
            
428
            for (Relationship rel : path.endNode().getRelationships(Direction.OUTGOING)) {
429
                // Skip blocked relationships
430
                if (!rel.hasProperty("blocked")) {
431
                    // Only follow certain relationship types
432
                    if (rel.isType(RelationshipType.withName("FRIENDS")) ||
433
                        rel.isType(RelationshipType.withName("COLLEAGUES"))) {
434
                        validRels.add(rel);
435
                    }
436
                }
437
            }
438
            
439
            return validRels;
440
        }
441
        
442
        @Override
443
        public PathExpander<Path> reverse() {
444
            return this; // Simplified for example
445
        }
446
    };
447
    
448
    TraversalDescription td = tx.traversalDescription()
449
        .breadthFirst()
450
        .expand(expander)
451
        .evaluator(Evaluators.toDepth(3))
452
        .evaluator(Evaluators.excludeStartPosition())
453
        .uniqueness(Uniqueness.NODE_GLOBAL);
454
    
455
    System.out.println("People reachable from Alice:");
456
    for (Node person : td.traverse(alice).nodes()) {
457
        System.out.println("  " + person.getProperty("name"));
458
    }
459
    
460
    tx.commit();
461
}
462

463
// Bidirectional traversal for shortest path
464
try (Transaction tx = graphDb.beginTx()) {
465
    Node start = tx.findNode(Label.label("Person"), "name", "Alice");
466
    Node end = tx.findNode(Label.label("Person"), "name", "Bob");
467
    
468
    TraversalDescription forwardTraversal = tx.traversalDescription()
469
        .breadthFirst()
470
        .relationships(RelationshipType.withName("KNOWS"), Direction.OUTGOING);
471
    
472
    TraversalDescription backwardTraversal = tx.traversalDescription()
473
        .breadthFirst()
474
        .relationships(RelationshipType.withName("KNOWS"), Direction.INCOMING);
475
    
476
    BidirectionalTraversalDescription bidirectional = tx.bidirectionalTraversalDescription()
477
        .startSide(forwardTraversal)
478
        .endSide(backwardTraversal)
479
        .collisionEvaluator(Evaluators.all());
480
    
481
    for (Path path : bidirectional.traverse(start, end)) {
482
        System.out.println("Found path of length " + path.length());
483
        for (Node node : path.nodes()) {
484
            System.out.println("  " + node.getProperty("name"));
485
        }
486
        break; // Just get the first (shortest) path
487
    }
488
    
489
    tx.commit();
490
}
491

492
// Traversal with stateful path expander
493
public class StatefulExpander implements PathExpander<Integer> {
494
    private final int maxBudget;
495
    
496
    public StatefulExpander(int maxBudget) {
497
        this.maxBudget = maxBudget;
498
    }
499
    
500
    @Override
501
    public Iterable<Relationship> expand(Path path, BranchState<Integer> state) {
502
        Integer remainingBudget = state.getState();
503
        if (remainingBudget == null) {
504
            remainingBudget = maxBudget;
505
        }
506
        
507
        List<Relationship> affordable = new ArrayList<>();
508
        
509
        for (Relationship rel : path.endNode().getRelationships()) {
510
            Integer cost = (Integer) rel.getProperty("cost", 1);
511
            if (cost <= remainingBudget) {
512
                affordable.add(rel);
513
                // Set remaining budget for next level
514
                state.setState(remainingBudget - cost);
515
            }
516
        }
517
        
518
        return affordable;
519
    }
520
    
521
    @Override
522
    public PathExpander<Integer> reverse() {
523
        return new StatefulExpander(maxBudget);
524
    }
525
}
526

527
// Use stateful expander
528
TraversalDescription costAwareTraversal = tx.traversalDescription()
529
    .breadthFirst()
530
    .expand(new StatefulExpander(10))
531
    .evaluator(Evaluators.toDepth(5));
532

533
for (Path path : costAwareTraversal.traverse(startNode)) {
534
    System.out.println("Found affordable path: " + path.length() + " hops");
535
}
536
```