Graph Traversal

Overview

The Graph API provides a powerful traversal interface called "walkers" that enables you to navigate and analyze your graph in a flexible, type-safe way. Walkers are the primary method for querying and manipulating graph data.

Basic Concepts

Walkers are built by chaining steps that define how to traverse the graph. Each step performs a specific operation, such as:

Starting at specific vertices
Moving to connected edges
Filtering elements
Collecting data
Modifying the graph

Traversal Order (Depth-First)

By default, the Graph API walker performs a Depth-First Search (DFS) traversal. This means it explores as far as possible along each branch before backtracking.

In the diagram above:

The traversal starts at node A.
It explores the left branch first: A → B → D → E.
After reaching the end of the left branch (E), it backtracks to B, then A.
It then explores the right branch: A → C → F.
The final DFS order is indicated by the numbers: A(1) → B(2) → D(3) → E(4) → C(5) → F(6).
The orange arrows highlight the path taken during the traversal.

This DFS behaviour is fundamental to how walkers navigate the graph.

Examples

Basic Traversal

Here's an example that finds all Project vertices that were created by someone that a Person knows:

// Basic traversal example showing a complex path through the graph
pub fn basic_traversal_example<G>(graph: &G)
where
    G: Graph<Vertex = Vertex, Edge = Edge> + SupportsVertexLabelIndex + SupportsEdgeLabelIndex,
{
    // Find all Person vertices who know someone who created a Project
    let _results = graph
        .walk()
        .vertices(Vertex::person()) // Start with Person vertices
        .edges(Edge::follows()) // Follow "follows" edges
        .tail() // Move to the target Person
        .edges(Edge::created()) // Follow "created" edges
        .tail() // Move to the Project
        .filter_project()
        .collect::<Vec<_>>(); // Collect results
}

This traversal:

Starts with Person vertices
Follows "knows" edges to find friends
Follows "created" edges from friends
Filters for Project vertices
Collects the results

Working with Context

Walkers have a built-in context system that allows you to store and transform data as you traverse the graph:

// Context example showing how to calculate the total age of all friends
pub fn context_traversal_example<G>(graph: &G, person_id: G::VertexId)
where
    G: Graph<Vertex = Vertex, Edge = Edge> + SupportsEdgeLabelIndex,
{
    // Calculate total age of all friends of a person
    let _total_age = graph
        .walk()
        .vertices_by_id(vec![person_id])
        .edges(Edge::follows())
        .tail()
        .filter_person()
        .push_context(|v, _| {
            // Store age in context
            if let Some(person) = v.project::<Person<_>>() {
                person.age()
            } else {
                0
            }
        })
        .fold(0, |acc, _, age| acc + age.deref());
}

In this example, we:

Start with a specific person
Find all friends (via "knows" edges)
Filter for Person vertices
Store each person's age in the context
Sum up all the ages

Walker Steps

The Graph API provides many steps that can be combined to create complex traversals. Each step is documented with:

See the Walker Steps section for detailed documentation on each available step.

graph-api