Graph Walks

What this page covers

get_neighbors returns the outgoing edges from a node. This page shows how to build common graph traversals — BFS, depth-bounded search, and path finding — on top of that primitive.

get_neighbors

pub async fn get_neighbors(&self, node_id: &str) -> Result<Vec<(String, String)>>

Returns every (predicate, object) pair where subject == node_id. The order is the Strand insertion order for the subject's index entries.

use gnosis::Gnosis;

async fn list_outgoing(g: &Gnosis, node: &str) -> Result<(), Box<dyn std::error::Error>> {
    for (predicate, object) in g.get_neighbors(node).await? {
        println!("{node} --[{predicate}]--> {object}");
    }
    Ok(())
}

get_neighbors walks only the subject index. For the inverse ("who points at me?"), issue a query against the object position:

use gnosis::{Gnosis, QueryPattern};

async fn list_incoming(g: &Gnosis, node: &str) -> Result<Vec<(String, String)>, Box<dyn std::error::Error>> {
    let triples = g.query(&QueryPattern {
        subject:   None,
        predicate: None,
        object:    Some(node.to_string()),
    }).await?;

    Ok(triples.into_iter()
        .map(|t| (t.subject, t.predicate))
        .collect())
}

Breadth-first traversal

use std::collections::{HashSet, VecDeque};
use gnosis::Gnosis;

async fn bfs(g: &Gnosis, start: &str, max_depth: usize) -> Result<HashSet<String>, Box<dyn std::error::Error>> {
    let mut visited = HashSet::new();
    let mut frontier: VecDeque<(String, usize)> = VecDeque::new();

    visited.insert(start.to_string());
    frontier.push_back((start.to_string(), 0));

    while let Some((node, depth)) = frontier.pop_front() {
        if depth >= max_depth {
            continue;
        }
        for (_pred, neighbor) in g.get_neighbors(&node).await? {
            if visited.insert(neighbor.clone()) {
                frontier.push_back((neighbor, depth + 1));
            }
        }
    }

    Ok(visited)
}

This is O(V + E) in the explored subgraph, with one strand read per neighbor.

Predicate-filtered traversal

get_neighbors returns every predicate. For typed walks (only "trusts" edges, for instance), filter at the caller or use query directly:

use std::collections::{HashSet, VecDeque};
use gnosis::{Gnosis, QueryPattern};

async fn typed_bfs(
    g: &Gnosis,
    start: &str,
    predicate: &str,
    max_depth: usize,
) -> Result<Vec<String>, Box<dyn std::error::Error>> {
    let mut visited = HashSet::from([start.to_string()]);
    let mut frontier: VecDeque<(String, usize)> = VecDeque::from([(start.to_string(), 0)]);
    let mut path = Vec::new();

    while let Some((node, depth)) = frontier.pop_front() {
        path.push(node.clone());
        if depth >= max_depth {
            continue;
        }
        let edges = g.query(&QueryPattern {
            subject:   Some(node),
            predicate: Some(predicate.to_string()),
            object:    None,
        }).await?;

        for t in edges {
            if visited.insert(t.object.clone()) {
                frontier.push_back((t.object, depth + 1));
            }
        }
    }

    Ok(path)
}

Shortest path

A standard BFS with a parent map. Gnosis has no built-in shortest-path operator; build it from get_neighbors:

use std::collections::{HashMap, VecDeque};
use gnosis::Gnosis;

async fn shortest_path(g: &Gnosis, from: &str, to: &str) -> Result<Option<Vec<String>>, Box<dyn std::error::Error>> {
    if from == to {
        return Ok(Some(vec![from.to_string()]));
    }

    let mut parent: HashMap<String, String> = HashMap::new();
    let mut frontier: VecDeque<String> = VecDeque::new();
    frontier.push_back(from.to_string());

    while let Some(node) = frontier.pop_front() {
        for (_p, next) in g.get_neighbors(&node).await? {
            if next == to {
                let mut path = vec![next.clone(), node.clone()];
                let mut cur = &node;
                while let Some(p) = parent.get(cur) {
                    path.push(p.clone());
                    cur = p;
                }
                path.reverse();
                return Ok(Some(path));
            }
            if !parent.contains_key(&next) && next != from {
                parent.insert(next.clone(), node.clone());
                frontier.push_back(next);
            }
        }
    }

    Ok(None)
}

Performance notes

Every neighbor lookup is one DashMap::get plus up to O(degree) Strand reads.
For dense graphs, batch your traversal: collect all next-hop node ids first, then call query with a Some(predicate) once per predicate type rather than get_neighbors per node.
Strand reads dominate. If your traversal visits the same node twice, cache neighbors at the caller.

Limits

Capability	Today	Workaround
Built-in BFS/DFS	No	Build on `get_neighbors`
Edge labels (typed edges)	Per-predicate, yes	Filter in the caller or via `query`
Weighted edges	No	Encode weight in the object string (or use a parallel Lens)
Bidirectional walks	Forward only via `get_neighbors`	Use `query` on the object index for reverse