Struct GraphStore 

pub struct GraphStore { /* private fields */ }

In-memory knowledge graph supporting entities, relationships, BFS/DFS, shortest-path, weighted shortest-path, and graph analytics.

Guarantees

• Thread-safe via Arc<Mutex<_>>
• BFS/DFS are non-recursive (stack-safe)
• Shortest-path is hop-count based (BFS)
• Weighted shortest-path uses Dijkstra’s algorithm

Implementations

impl GraphStore

pub fn new() -> Self

Create a new, empty graph store.

pub fn add_entity(&self, entity: Entity) -> Result<(), AgentRuntimeError>

Add an entity to the graph.

If an entity with the same ID already exists, it is replaced.

pub fn get_entity(&self, id: &EntityId) -> Result<Entity, AgentRuntimeError>

Retrieve an entity by ID.

pub fn has_entity(&self, id: &EntityId) -> Result<bool, AgentRuntimeError>

Return true if an entity with the given id exists in the graph.

pub fn has_any_entities(&self) -> Result<bool, AgentRuntimeError>

Return true if the graph contains at least one entity.

pub fn entity_type_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of distinct entity label strings present in the graph.

pub fn labels(&self) -> Result<Vec<String>, AgentRuntimeError>

Return the distinct entity labels present in the graph, sorted.

pub fn incoming_count_for( &self, id: &EntityId, ) -> Result<usize, AgentRuntimeError>

Return the number of incoming relationships for the given entity.

Returns 0 if the entity has no in-edges or does not exist.

pub fn outgoing_count_for( &self, id: &EntityId, ) -> Result<usize, AgentRuntimeError>

Return the number of outbound edges from the given entity.

Returns 0 if the entity has no outgoing relationships.

pub fn sink_count(&self) -> Result<usize, AgentRuntimeError>

Return the count of entities that have no outgoing edges (sink nodes).

pub fn bidirectional_count(&self) -> Result<usize, AgentRuntimeError>

Return the count of entity pairs (A, B) where edges exist in both directions.

Each bidirectional pair is counted once.

pub fn has_self_loops(&self) -> Result<bool, AgentRuntimeError>

Return true if any relationship is a self-loop (from == to).

pub fn source_count(&self) -> Result<usize, AgentRuntimeError>

Return the count of entities that have no incoming edges (source nodes).

pub fn orphan_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of entities that have no outgoing relationships.

pub fn isolated_entity_count(&self) -> Result<usize, AgentRuntimeError>

Return the count of entities that have neither outgoing nor incoming relationships.

pub fn avg_relationship_weight(&self) -> Result<f64, AgentRuntimeError>

Return the mean weight of all relationships in the graph.

Returns 0.0 if no relationships have been added.

pub fn total_in_degree(&self) -> Result<usize, AgentRuntimeError>

Return the sum of in-degrees across all entities.

Equal to the total number of relationships in the graph (each relationship contributes 1 to the in-degree of its target entity).

pub fn relationship_count_between( &self, from: &EntityId, to: &EntityId, ) -> Result<usize, AgentRuntimeError>

Return the count of directed relationships from from to to.

Returns 0 if no such relationships exist.

pub fn edges_from( &self, id: &EntityId, ) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all relationships originating from id, in insertion order.

Returns an empty Vec if the entity has no outgoing relationships or does not exist.

pub fn neighbors_of( &self, id: &EntityId, ) -> Result<Vec<EntityId>, AgentRuntimeError>

Return the EntityIds reachable from id in a single hop, sorted.

Returns an empty Vec if the entity has no outgoing relationships or does not exist.

pub fn add_relationship( &self, rel: Relationship, ) -> Result<(), AgentRuntimeError>

Add a directed relationship between two existing entities.

Both source and target entities must already exist in the graph.

pub fn remove_relationship( &self, from: &EntityId, to: &EntityId, kind: &str, ) -> Result<(), AgentRuntimeError>

Remove a specific relationship by (from, to, kind).

Returns Err if no matching relationship exists.

pub fn remove_entity(&self, id: &EntityId) -> Result<(), AgentRuntimeError>

Remove an entity and all relationships involving it.

pub fn bfs(&self, start: &EntityId) -> Result<Vec<EntityId>, AgentRuntimeError>

Breadth-first search starting from start.

Returns entity IDs in BFS discovery order (not including the start node).

pub fn dfs(&self, start: &EntityId) -> Result<Vec<EntityId>, AgentRuntimeError>

Depth-first search starting from start.

Returns entity IDs in DFS discovery order (not including the start node).

pub fn shortest_path( &self, from: &EntityId, to: &EntityId, ) -> Result<Option<Vec<EntityId>>, AgentRuntimeError>

Find the shortest path (by hop count) between from and to.

Returns

• Some(path) — ordered list of EntityIds from from to to (inclusive)
• None — no path exists

pub fn shortest_path_weighted( &self, from: &EntityId, to: &EntityId, ) -> Result<Option<(Vec<EntityId>, f32)>, AgentRuntimeError>

Find the shortest weighted path between from and to using Dijkstra’s algorithm.

Uses Relationship::weight as edge cost. Negative weights are not supported and will cause this method to return an error.

Returns

• Ok(Some((path, total_weight))) — the shortest path and its total weight
• Ok(None) — no path exists between from and to
• Err(...) — either entity not found, or a negative edge weight was encountered

pub fn transitive_closure( &self, start: &EntityId, ) -> Result<HashSet<EntityId>, AgentRuntimeError>

Compute the transitive closure: all entities reachable from start (including start itself).

Uses a single lock acquisition and builds the result as a HashSet directly, avoiding the intermediate Vec that would otherwise be produced by delegating to bfs.

pub fn entity_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of entities in the graph.

pub fn node_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of entities in the graph.

Alias for entity_count using graph-theory terminology.

pub fn relationship_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of relationships in the graph.

pub fn average_out_degree(&self) -> Result<f64, AgentRuntimeError>

Return the average out-degree across all entities.

Returns 0.0 for an empty graph. The result is the total number of directed edges divided by the number of nodes.

pub fn in_degree_for( &self, entity_id: &EntityId, ) -> Result<usize, AgentRuntimeError>

Return the in-degree (number of incoming edges) for the given entity.

Returns 0 if the entity does not exist or has no incoming edges.

pub fn out_degree_for( &self, entity_id: &EntityId, ) -> Result<usize, AgentRuntimeError>

Return the out-degree (number of outgoing edges) for the given entity.

Returns 0 if the entity does not exist or has no outgoing edges.

pub fn predecessors( &self, entity_id: &EntityId, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities that have a directed edge pointing to entity_id (its predecessors in the directed graph).

Returns an empty Vec if the entity has no incoming edges or does not exist.

pub fn is_source(&self, entity_id: &EntityId) -> Result<bool, AgentRuntimeError>

Return true if the entity has no incoming edges (in-degree == 0).

In a DAG, source nodes (roots) have no predecessors. Returns false if the entity does not exist.

pub fn successors( &self, entity_id: &EntityId, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities directly reachable from entity_id via outgoing edges (its successors / immediate out-neighbors).

Returns an empty Vec if the entity has no outgoing edges or does not exist.

pub fn is_sink(&self, entity_id: &EntityId) -> Result<bool, AgentRuntimeError>

Return true if the entity has no outgoing edges (out-degree == 0).

In a DAG, sink nodes (leaves) have no successors. Returns true if the entity does not exist (unknown nodes cannot have outgoing edges).

pub fn reachable_from( &self, start: &EntityId, ) -> Result<HashSet<EntityId>, AgentRuntimeError>

Return the set of all entity IDs reachable from start via directed edges (BFS traversal). The starting node itself is not included.

Returns an empty HashSet if start has no outgoing edges or does not exist.

pub fn contains_cycle(&self) -> Result<bool, AgentRuntimeError>

Return true if the directed graph contains at least one cycle.

Uses iterative DFS with a three-colour scheme (unvisited / in-stack / done). An empty graph is acyclic.

pub fn edge_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of relationships in the graph.

Alias for relationship_count using graph-theory terminology.

pub fn is_acyclic(&self) -> Result<bool, AgentRuntimeError>

Return true if the directed graph contains no cycles.

Shorthand for !self.contains_cycle().

pub fn avg_out_degree(&self) -> Result<f64, AgentRuntimeError>

Return the mean out-degree across all entities.

Returns 0.0 for graphs with no entities.

pub fn avg_in_degree(&self) -> Result<f64, AgentRuntimeError>

Return the mean in-degree across all entities.

Returns 0.0 for graphs with no entities.

pub fn max_out_degree(&self) -> Result<usize, AgentRuntimeError>

Return the maximum out-degree across all entities, or 0 for empty graphs.

pub fn max_in_degree(&self) -> Result<usize, AgentRuntimeError>

Return the maximum in-degree across all entities, or 0 for empty graphs.

pub fn weight_stats(&self) -> Result<Option<(f64, f64, f64)>, AgentRuntimeError>

Return (min_weight, max_weight, mean_weight) across all relationships.

Returns None if the graph has no relationships.

pub fn isolated_nodes(&self) -> Result<HashSet<EntityId>, AgentRuntimeError>

Return the set of entity IDs that have no inbound and no outbound edges.

An isolated node is one that does not appear as a from or to endpoint in any relationship. Useful for detecting orphaned entities.

pub fn sum_edge_weights(&self) -> Result<f64, AgentRuntimeError>

Return the sum of all relationship weights in the graph.

Returns 0.0 for graphs with no relationships.

pub fn entity_ids(&self) -> Result<Vec<EntityId>, AgentRuntimeError>

Return all entity IDs in the graph without allocating full Entity objects.

Cheaper than all_entities when only IDs are needed.

pub fn is_empty(&self) -> Result<bool, AgentRuntimeError>

Return true if the graph contains no entities.

pub fn clear(&self) -> Result<(), AgentRuntimeError>

Remove all entities and relationships from the graph.

After this call entity_count() and relationship_count() both return 0.

pub fn entity_count_by_label( &self, label: &str, ) -> Result<usize, AgentRuntimeError>

Count entities whose label equals label (case-sensitive).

pub fn graph_density(&self) -> Result<f64, AgentRuntimeError>

Compute the directed graph density: |E| / (|V| × (|V| − 1)).

Returns 0.0 for graphs with fewer than two entities (no edges possible). A density of 1.0 means every possible directed edge is present.

pub fn entity_labels(&self) -> Result<Vec<String>, AgentRuntimeError>

Return all distinct entity label strings present in the graph, sorted.

pub fn relationship_kinds(&self) -> Result<Vec<String>, AgentRuntimeError>

Return all distinct relationship kind strings present in the graph, sorted.

pub fn relationship_kind_count(&self) -> Result<usize, AgentRuntimeError>

Return the number of distinct relationship kind strings present in the graph.

pub fn entities_with_self_loops( &self, ) -> Result<Vec<EntityId>, AgentRuntimeError>

Return the EntityIds of entities that have at least one self-loop relationship.

A self-loop is a relationship where from == to.

pub fn update_entity_label( &self, id: &EntityId, new_label: impl Into<String>, ) -> Result<bool, AgentRuntimeError>

Update the label of an existing entity in-place.

Returns Ok(true) if the entity was found and updated, Ok(false) if not found.

pub fn degree_centrality( &self, ) -> Result<HashMap<EntityId, f32>, AgentRuntimeError>

Compute normalized degree centrality for each entity. Degree = (in_degree + out_degree) / (n - 1), or 0.0 if n <= 1.

pub fn betweenness_centrality( &self, ) -> Result<HashMap<EntityId, f32>, AgentRuntimeError>

Compute normalized betweenness centrality for each entity. Uses Brandes’ algorithm with hop-count BFS.

Complexity

O(V * E) time. Not suitable for very large graphs (>1000 nodes).

pub fn label_propagation_communities( &self, max_iterations: usize, ) -> Result<HashMap<EntityId, usize>, AgentRuntimeError>

Detect communities using label propagation. Each entity starts as its own community. In each iteration, each entity adopts the most frequent label among its neighbours. Returns a map of entity ID → community ID (usize).

pub fn detect_cycles(&self) -> Result<bool, AgentRuntimeError>

Detect whether the directed graph contains any cycles.

Uses iterative DFS with a three-color marking scheme. The result is cached until the next mutation (add_entity, add_relationship, or remove_entity).

Returns

• Ok(true) — at least one cycle exists
• Ok(false) — the graph is acyclic (a DAG)

pub fn topological_sort(&self) -> Result<Vec<EntityId>, AgentRuntimeError>

Compute a topological ordering of all entities.

Returns the entities sorted so that for every directed edge (A → B), A appears before B in the result. Uses iterative DFS (post-order).

Errors

Returns Err(AgentRuntimeError::Graph(...)) if the graph contains a cycle.

pub fn update_entity_property( &self, id: &EntityId, key: impl Into<String>, value: Value, ) -> Result<bool, AgentRuntimeError>

Update a single property on an existing entity.

Returns Ok(true) if the entity was found and updated, Ok(false) otherwise.

pub fn is_dag(&self) -> Result<bool, AgentRuntimeError>

Return true if the graph is a DAG (directed acyclic graph).

Equivalent to !detect_cycles() but reads more naturally in condition expressions.

pub fn connected_components(&self) -> Result<usize, AgentRuntimeError>

Count the number of weakly connected components in the graph.

Treats all edges as undirected for component assignment. Isolated nodes (no edges) each count as their own component. Uses Union-Find.

pub fn weakly_connected(&self) -> Result<bool, AgentRuntimeError>

Return true if the graph is weakly connected (i.e. has at most one connected component when all edges are treated as undirected).

An empty graph is considered weakly connected by convention.

Errors

Propagates any lock-poisoning error from [connected_components].

pub fn sink_nodes(&self) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities that have no outgoing edges (out-degree == 0).

In a DAG these are the leaf nodes. Useful for identifying terminal states in a workflow or dependency graph.

pub fn source_nodes(&self) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities that have no incoming edges (in-degree == 0).

In a DAG these are the root nodes. Useful for finding entry points in a workflow or dependency graph.

pub fn isolates(&self) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities that have no edges (neither incoming nor outgoing).

pub fn out_degree(&self, id: &EntityId) -> Result<usize, AgentRuntimeError>

Return the number of outgoing edges (out-degree) for id.

Returns 0 if the entity has no outgoing edges or does not exist.

pub fn in_degree(&self, id: &EntityId) -> Result<usize, AgentRuntimeError>

Return the number of incoming edges (in-degree) for id.

Uses the reverse adjacency index for O(in-degree) lookup.

pub fn path_exists( &self, from: &str, to: &str, ) -> Result<bool, AgentRuntimeError>

Return true if there is any path from from to to.

Both nodes must exist or returns Err. Uses BFS internally. Returns Ok(false) if nodes exist but are not connected.

pub fn shortest_path_length( &self, from: &EntityId, to: &EntityId, ) -> Result<Option<usize>, AgentRuntimeError>

Return the hop-count of the shortest path from from to to.

Returns Some(hops) if a path exists, None if the nodes are disconnected. Both node IDs must exist or returns Err.

pub fn bfs_bounded( &self, start: &str, max_depth: usize, max_nodes: usize, ) -> Result<Vec<EntityId>, AgentRuntimeError>

BFS limited by maximum depth and maximum node count.

Returns the subset of nodes visited within those limits (including start).

pub fn dfs_bounded( &self, start: &str, max_depth: usize, max_nodes: usize, ) -> Result<Vec<EntityId>, AgentRuntimeError>

DFS limited by maximum depth and maximum node count.

Returns the subset of nodes visited within those limits (including start).

pub fn all_entities(&self) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities in the graph.

pub fn all_relationships(&self) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all relationships in the graph.

pub fn find_relationships_by_kind( &self, kind: &str, ) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all relationships whose kind matches kind (case-sensitive).

pub fn count_relationships_by_kind( &self, kind: &str, ) -> Result<usize, AgentRuntimeError>

Return the number of relationships whose kind matches kind (case-sensitive).

pub fn find_entities_by_label( &self, label: &str, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities whose label matches label (case-sensitive).

pub fn find_entities_by_labels( &self, labels: &[&str], ) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities whose label is contained in labels.

Order of results is unspecified. An empty labels slice returns an empty result (never all entities).

pub fn remove_isolated(&self) -> Result<usize, AgentRuntimeError>

Remove all isolated entities (those with no incoming or outgoing edges).

Returns the number of entities removed.

pub fn get_relationships_for( &self, id: &EntityId, ) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all outgoing relationships from id (those where id is the source).

pub fn relationships_between( &self, from: &EntityId, to: &EntityId, ) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all relationships where both endpoints are from and to (any direction or kind).

pub fn find_entities_by_property( &self, key: &str, expected: &Value, ) -> Result<Vec<Entity>, AgentRuntimeError>

Find entities that have a property key whose value equals expected.

Uses serde_json::Value equality; for string properties pass serde_json::Value::String(...).

pub fn merge(&self, other: &GraphStore) -> Result<(), AgentRuntimeError>

Merge another GraphStore into this one.

Entities are inserted (or replaced if the same ID exists); relationships are inserted only if the (from, to, kind) triple does not already exist.

pub fn neighbor_entities( &self, id: &EntityId, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return the Entity objects for all direct out-neighbors of id.

Neighbors are the targets of all outgoing relationships from id. Entities that no longer exist (orphan edge targets) are silently skipped.

pub fn neighbor_ids( &self, id: &EntityId, ) -> Result<Vec<EntityId>, AgentRuntimeError>

Return the IDs of all directly reachable neighbours from id (i.e. the to end of every outgoing relationship).

Cheaper than neighbor_entities when only IDs are needed.

pub fn remove_all_relationships_for( &self, id: &EntityId, ) -> Result<usize, AgentRuntimeError>

Remove all relationships where id is the source (outgoing edges).

Also updates the adjacency index. Does not remove incoming edges from other nodes that point to id — use this before remove_entity to ensure consistent graph state.

Returns the number of relationships removed.

pub fn entity_exists(&self, id: &EntityId) -> Result<bool, AgentRuntimeError>

Check whether an entity with the given ID exists.

pub fn relationship_exists( &self, from: &EntityId, to: &EntityId, kind: &str, ) -> Result<bool, AgentRuntimeError>

Check whether a relationship (from, to, kind) exists.

Uses the adjacency index (O(out-degree of from)) rather than a full O(|E|) scan over all relationships.

pub fn subgraph( &self, node_ids: &[EntityId], ) -> Result<GraphStore, AgentRuntimeError>

Extract a subgraph containing only the specified entities and the relationships between them.

pub fn reverse(&self) -> Result<GraphStore, AgentRuntimeError>

Return a new graph with all edge directions reversed.

Every relationship A → B becomes B → A in the returned graph. All entities are copied; relationship weights and kinds are preserved.

pub fn common_neighbors( &self, a: &EntityId, b: &EntityId, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return entities that are out-neighbors of both a and b.

Useful for link-prediction and community detection heuristics. Returns an empty Vec if either node has no outgoing edges.

pub fn weight_of( &self, from: &EntityId, to: &EntityId, ) -> Result<Option<f32>, AgentRuntimeError>

Return the weight of the first relationship from from to to.

Returns None if no such edge exists.

pub fn neighbors_in( &self, id: &EntityId, ) -> Result<Vec<EntityId>, AgentRuntimeError>

Return the IDs of all entities that have an outgoing edge pointing to id.

This is the inverse of neighbor_entities, which returns out-neighbors. Returns an empty Vec if no incoming edges exist for id.

pub fn density(&self) -> Result<f64, AgentRuntimeError>

Return the graph density: edges / (nodes * (nodes − 1)) for a directed graph.

Returns 0.0 when the graph has fewer than 2 nodes (no directed edges are possible). Values range from 0.0 (sparse) to 1.0 (complete).

pub fn avg_degree(&self) -> Result<f64, AgentRuntimeError>

Return the average out-degree across all nodes.

Returns 0.0 for an empty graph.

pub fn total_weight(&self) -> Result<f32, AgentRuntimeError>

Return the sum of all edge weights in the graph.

Returns 0.0 for an empty graph or a graph with no relationships.

pub fn max_edge_weight(&self) -> Result<Option<f32>, AgentRuntimeError>

Return the maximum edge weight, or None if the graph has no edges.

pub fn min_edge_weight(&self) -> Result<Option<f32>, AgentRuntimeError>

Return the minimum edge weight, or None if the graph has no edges.

pub fn top_n_by_out_degree( &self, n: usize, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return the top-N entities by out-degree (most outgoing edges first).

If n == 0 or the graph is empty, returns an empty Vec. Ties are broken by arbitrary hash-map iteration order.

pub fn remove_entity_and_edges( &self, id: &EntityId, ) -> Result<(), AgentRuntimeError>

Remove id and all relationships where it is the source or target.

Equivalent to calling remove_entity and remove_all_relationships_for in a single lock acquisition, avoiding two separate look-ups.

Returns Ok(()) if the entity was found and removed. Returns Err(AgentRuntimeError::Graph) if no entity with that ID exists.

pub fn hub_nodes( &self, threshold: usize, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities whose out-degree is at or above threshold.

Useful for finding hub or gateway nodes in a knowledge graph.

pub fn incident_relationships( &self, entity_id: &EntityId, ) -> Result<Vec<Relationship>, AgentRuntimeError>

Return all relationships incident to entity_id (where the entity is either the source or the target).

pub fn max_out_degree_entity(&self) -> Result<Option<Entity>, AgentRuntimeError>

Return the entity with the highest out-degree (most outgoing edges), or None if the graph is empty.

If multiple entities share the maximum out-degree, the first one encountered (in arbitrary hash-map iteration order) is returned.

pub fn max_in_degree_entity(&self) -> Result<Option<Entity>, AgentRuntimeError>

Return the entity with the most incoming edges (highest in-degree).

Uses the reverse adjacency index for O(V) computation. Returns None for an empty graph or a graph with no edges.

pub fn leaf_nodes(&self) -> Result<Vec<Entity>, AgentRuntimeError>

Return all entities with out-degree = 0 (no outgoing edges).

Leaf nodes (also called sink nodes in directed graphs) are entities that have no outgoing relationships. See also sink_nodes which also counts nodes with no outgoing edges but filters differently.

pub fn top_nodes_by_out_degree( &self, n: usize, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return the top n entities sorted by out-degree (descending).

Uses the adjacency index for O(V log V) computation. Useful for finding hub nodes — entities with the most outgoing connections. Returns fewer than n entities if the graph has fewer nodes.

pub fn top_nodes_by_in_degree( &self, n: usize, ) -> Result<Vec<Entity>, AgentRuntimeError>

Return the top n entities sorted by in-degree (descending).

Uses the reverse adjacency index for O(V log V) computation. Useful for finding sink hubs — entities with the most incoming connections.

Trait Implementations

impl Clone for GraphStore

fn clone(&self) -> GraphStore

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for GraphStore

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for GraphStore

fn default() -> Self

Returns the “default value” for a type.