Traversal and Path Finding

/**
 * Describes how to perform graph traversals
 */
public interface TraversalDescription {
    
    /**
     * Specify which relationships to follow during traversal
     * @param relationshipType Type of relationships to follow
     * @return Modified traversal description
     */
    TraversalDescription relationships(RelationshipType relationshipType);
    
    /**
     * Specify relationships and direction to follow
     * @param relationshipType Type of relationships to follow
     * @param direction Direction to traverse relationships
     * @return Modified traversal description
     */
    TraversalDescription relationships(RelationshipType relationshipType, Direction direction);
    
    /**
     * Use depth-first traversal strategy
     * @return Modified traversal description
     */
    TraversalDescription depthFirst();
    
    /**
     * Use breadth-first traversal strategy
     * @return Modified traversal description
     */
    TraversalDescription breadthFirst();
    
    /**
     * Set the maximum depth for traversal
     * @param depth Maximum depth to traverse
     * @return Modified traversal description
     */
    TraversalDescription evaluator(Evaluator evaluator);
    
    /**
     * Set path evaluator to control traversal behavior
     * @param evaluator Path evaluator
     * @return Modified traversal description
     */
    TraversalDescription evaluator(PathEvaluator<Path> evaluator);
    
    /**
     * Set the path expander for relationship traversal
     * @param expander Path expander
     * @return Modified traversal description
     */
    TraversalDescription expand(PathExpander<Path> expander);
    
    /**
     * Set uniqueness strategy for nodes and relationships
     * @param uniqueness Uniqueness strategy
     * @return Modified traversal description
     */
    TraversalDescription uniqueness(Uniqueness uniqueness);
    
    /**
     * Start traversal from the specified node
     * @param startNode Starting node for traversal
     * @return Traverser for executing the traversal
     */
    Traverser traverse(Node startNode);
    
    /**
     * Start traversal from multiple starting nodes
     * @param startNodes Starting nodes for traversal
     * @return Traverser for executing the traversal
     */
    Traverser traverse(Node... startNodes);
}

import org.neo4j.graphdb.traversal.*;
import org.neo4j.graphdb.Direction;
import static org.neo4j.graphdb.traversal.Evaluators.*;

try (Transaction tx = graphDb.beginTx()) {
    Node startNode = tx.findNode(Label.label("Person"), "name", "Alice");
    
    // Simple depth-first traversal
    TraversalDescription td = tx.traversalDescription()
        .depthFirst()
        .relationships(RelationshipType.withName("FRIENDS"), Direction.OUTGOING)
        .evaluator(toDepth(3));
    
    for (Path path : td.traverse(startNode)) {
        Node endNode = path.endNode();
        System.out.println("Found friend: " + endNode.getProperty("name") + 
                          " at depth " + path.length());
    }
    
    // Breadth-first traversal with multiple relationship types
    TraversalDescription td2 = tx.traversalDescription()
        .breadthFirst()
        .relationships(RelationshipType.withName("FRIENDS"))
        .relationships(RelationshipType.withName("COLLEAGUES"))
        .evaluator(toDepth(2))
        .uniqueness(Uniqueness.NODE_GLOBAL);
    
    for (Node node : td2.traverse(startNode).nodes()) {
        System.out.println("Connected person: " + node.getProperty("name"));
    }
    
    tx.commit();
}

/**
 * Executes graph traversals
 */
public interface Traverser extends Iterable<Path> {
    
    /**
     * Get all nodes found during traversal
     * @return Iterable of nodes
     */
    Iterable<Node> nodes();
    
    /**
     * Get all relationships traversed during traversal
     * @return Iterable of relationships
     */
    Iterable<Relationship> relationships();
    
    /**
     * Get all paths found during traversal
     * @return Iterable of paths (same as iterator())
     */
    Iterable<Path> paths();
    
    /**
     * Get iterator over paths
     * @return Iterator over paths
     */
    @Override
    Iterator<Path> iterator();
}

/**
 * Evaluates paths during traversal to control continuation and inclusion
 */
public interface PathEvaluator<T> {
    
    /**
     * Evaluate a path and return evaluation result
     * @param path Path to evaluate
     * @return Evaluation result
     */
    Evaluation evaluate(Path path);
}

/**
 * Simple evaluator interface for backward compatibility
 */
public interface Evaluator extends PathEvaluator<Path> {
    /**
     * Evaluate a path
     * @param path Path to evaluate
     * @return Evaluation result
     */
    @Override
    Evaluation evaluate(Path path);
}

/**
 * Evaluation result indicating whether to include path and continue traversal
 */
public enum Evaluation {
    /** Include this path in results and continue traversal */
    INCLUDE_AND_CONTINUE,
    
    /** Include this path in results but don't continue traversal */
    INCLUDE_AND_PRUNE,
    
    /** Don't include this path but continue traversal */
    EXCLUDE_AND_CONTINUE,
    
    /** Don't include this path and don't continue traversal */
    EXCLUDE_AND_PRUNE
}

// Custom path evaluator
PathEvaluator<Path> customEvaluator = new PathEvaluator<Path>() {
    @Override
    public Evaluation evaluate(Path path) {
        Node endNode = path.endNode();
        
        // Only include paths ending at Person nodes
        if (!endNode.hasLabel(Label.label("Person"))) {
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }
        
        // Stop at depth 4
        if (path.length() >= 4) {
            return Evaluation.INCLUDE_AND_PRUNE;
        }
        
        // Include young people and continue
        Integer age = (Integer) endNode.getProperty("age", 0);
        if (age < 30) {
            return Evaluation.INCLUDE_AND_CONTINUE;
        }
        
        // Exclude older people but continue traversal
        return Evaluation.EXCLUDE_AND_CONTINUE;
    }
};

// Use custom evaluator
TraversalDescription td = tx.traversalDescription()
    .breadthFirst()
    .relationships(RelationshipType.withName("KNOWS"))
    .evaluator(customEvaluator);

for (Path path : td.traverse(startNode)) {
    Node person = path.endNode();
    System.out.println("Young person found: " + person.getProperty("name"));
}

/**
 * Factory for common path evaluators
 */
public final class Evaluators {
    
    /**
     * Evaluator that includes all paths up to a maximum depth
     * @param depth Maximum depth to traverse
     * @return Path evaluator
     */
    public static PathEvaluator<Path> toDepth(int depth);
    
    /**
     * Evaluator that includes paths from a minimum depth
     * @param depth Minimum depth to include
     * @return Path evaluator
     */
    public static PathEvaluator<Path> fromDepth(int depth);
    
    /**
     * Evaluator that includes paths within a depth range
     * @param minDepth Minimum depth (inclusive)
     * @param maxDepth Maximum depth (inclusive)
     * @return Path evaluator
     */
    public static PathEvaluator<Path> includingDepths(int minDepth, int maxDepth);
    
    /**
     * Evaluator that excludes start node from results
     * @return Path evaluator
     */
    public static PathEvaluator<Path> excludeStartPosition();
    
    /**
     * Evaluator that includes all paths
     * @return Path evaluator
     */
    public static PathEvaluator<Path> all();
    
    /**
     * Evaluator that returns at specific depth only
     * @param depth Exact depth to return
     * @return Path evaluator
     */
    public static PathEvaluator<Path> atDepth(int depth);
}

/**
 * Controls how relationships are expanded during traversal
 */
public interface PathExpander<STATE> {
    
    /**
     * Expand from a path to get next relationships
     * @param path Current path
     * @return Iterable of relationships to explore
     */
    Iterable<Relationship> expand(Path path, BranchState<STATE> state);
    
    /**
     * Reverse this path expander
     * @return Reversed path expander
     */
    PathExpander<STATE> reverse();
}

/**
 * Factory for common path expanders
 */
public final class PathExpanders {
    
    /**
     * Create expander for all relationships
     * @return Path expander
     */
    public static PathExpander<Path> allTypesAndDirections();
    
    /**
     * Create expander for specific relationship types and directions
     * @param types Array of relationship types and directions
     * @return Path expander
     */
    public static PathExpander<Path> forTypesAndDirections(RelationshipType... types);
    
    /**
     * Create expander for outgoing relationships of specific types
     * @param types Relationship types
     * @return Path expander
     */
    public static PathExpander<Path> forTypeAndDirection(RelationshipType type, Direction direction);
    
    /**
     * Create expander that filters by relationship properties
     * @param baseExpander Base expander to filter
     * @param filter Property filter
     * @return Filtered path expander
     */
    public static PathExpander<Path> forConstantDirectionWithTypes(
        Direction direction, RelationshipType... types);
}

/**
 * Bidirectional traversal configuration
 */
public interface BidirectionalTraversalDescription {
    
    /**
     * Set the start side traversal description
     * @param startSide Traversal description for start side
     * @return Modified bidirectional traversal description
     */
    BidirectionalTraversalDescription startSide(TraversalDescription startSide);
    
    /**
     * Set the end side traversal description
     * @param endSide Traversal description for end side
     * @return Modified bidirectional traversal description
     */
    BidirectionalTraversalDescription endSide(TraversalDescription endSide);
    
    /**
     * Set collision evaluator for detecting path intersections
     * @param collisionEvaluator Collision evaluator
     * @return Modified bidirectional traversal description
     */
    BidirectionalTraversalDescription collisionEvaluator(
        PathEvaluator<Path> collisionEvaluator);
    
    /**
     * Set side selector for controlling alternation between sides
     * @param sideSelector Side selector
     * @return Modified bidirectional traversal description
     */
    BidirectionalTraversalDescription sideSelector(SideSelector sideSelector);
    
    /**
     * Find paths between start and end nodes
     * @param start Start node
     * @param end End node
     * @return Iterable of paths found
     */
    Iterable<Path> traverse(Node start, Node end);
}

// Complex traversal with multiple constraints
try (Transaction tx = graphDb.beginTx()) {
    Node alice = tx.findNode(Label.label("Person"), "name", "Alice");
    
    // Find all reachable people within 3 hops, excluding blocked relationships
    PathExpander<Path> expander = new PathExpander<Path>() {
        @Override
        public Iterable<Relationship> expand(Path path, BranchState<Path> state) {
            List<Relationship> validRels = new ArrayList<>();
            
            for (Relationship rel : path.endNode().getRelationships(Direction.OUTGOING)) {
                // Skip blocked relationships
                if (!rel.hasProperty("blocked")) {
                    // Only follow certain relationship types
                    if (rel.isType(RelationshipType.withName("FRIENDS")) ||
                        rel.isType(RelationshipType.withName("COLLEAGUES"))) {
                        validRels.add(rel);
                    }
                }
            }
            
            return validRels;
        }
        
        @Override
        public PathExpander<Path> reverse() {
            return this; // Simplified for example
        }
    };
    
    TraversalDescription td = tx.traversalDescription()
        .breadthFirst()
        .expand(expander)
        .evaluator(Evaluators.toDepth(3))
        .evaluator(Evaluators.excludeStartPosition())
        .uniqueness(Uniqueness.NODE_GLOBAL);
    
    System.out.println("People reachable from Alice:");
    for (Node person : td.traverse(alice).nodes()) {
        System.out.println("  " + person.getProperty("name"));
    }
    
    tx.commit();
}

// Bidirectional traversal for shortest path
try (Transaction tx = graphDb.beginTx()) {
    Node start = tx.findNode(Label.label("Person"), "name", "Alice");
    Node end = tx.findNode(Label.label("Person"), "name", "Bob");
    
    TraversalDescription forwardTraversal = tx.traversalDescription()
        .breadthFirst()
        .relationships(RelationshipType.withName("KNOWS"), Direction.OUTGOING);
    
    TraversalDescription backwardTraversal = tx.traversalDescription()
        .breadthFirst()
        .relationships(RelationshipType.withName("KNOWS"), Direction.INCOMING);
    
    BidirectionalTraversalDescription bidirectional = tx.bidirectionalTraversalDescription()
        .startSide(forwardTraversal)
        .endSide(backwardTraversal)
        .collisionEvaluator(Evaluators.all());
    
    for (Path path : bidirectional.traverse(start, end)) {
        System.out.println("Found path of length " + path.length());
        for (Node node : path.nodes()) {
            System.out.println("  " + node.getProperty("name"));
        }
        break; // Just get the first (shortest) path
    }
    
    tx.commit();
}

// Traversal with stateful path expander
public class StatefulExpander implements PathExpander<Integer> {
    private final int maxBudget;
    
    public StatefulExpander(int maxBudget) {
        this.maxBudget = maxBudget;
    }
    
    @Override
    public Iterable<Relationship> expand(Path path, BranchState<Integer> state) {
        Integer remainingBudget = state.getState();
        if (remainingBudget == null) {
            remainingBudget = maxBudget;
        }
        
        List<Relationship> affordable = new ArrayList<>();
        
        for (Relationship rel : path.endNode().getRelationships()) {
            Integer cost = (Integer) rel.getProperty("cost", 1);
            if (cost <= remainingBudget) {
                affordable.add(rel);
                // Set remaining budget for next level
                state.setState(remainingBudget - cost);
            }
        }
        
        return affordable;
    }
    
    @Override
    public PathExpander<Integer> reverse() {
        return new StatefulExpander(maxBudget);
    }
}

// Use stateful expander
TraversalDescription costAwareTraversal = tx.traversalDescription()
    .breadthFirst()
    .expand(new StatefulExpander(10))
    .evaluator(Evaluators.toDepth(5));

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