HeliosDB Graph Query Support

HeliosDB Graph Query Support

Advanced graph query capabilities for HeliosDB including recursive CTEs, graph traversal algorithms, and path-finding.

Features

• Recursive Common Table Expressions (CTEs): Execute complex hierarchical queries with cycle detection
• Graph Traversal: BFS (Breadth-First Search) and DFS (Depth-First Search) algorithms
• Path-Finding: Dijkstra’s shortest path, A* algorithm, and all-paths enumeration
• Cycle Detection: Identify cycles using DFS and Tarjan’s strongly connected components
• Graph Algorithms: Connected components, transitive closure, topological sort
• Centrality Measures: PageRank, betweenness centrality, degree centrality
• Graph-Specific Indexes: Adjacency lists for efficient neighbor lookup

Installation

Add this to your Cargo.toml:

[dependencies]
heliosdb-graph = "3.0"

Quick Start

use heliosdb_graph::*;

#[tokio::main]
async fn main() -> anyhow::Result<()> {
    // Create graph engine
    let config = GraphConfig::default();
    let engine = GraphEngine::new(config).await?;

    // Register a graph
    engine.register_graph("my_graph".to_string()).await?;

    // Add nodes
    let node1 = Node {
        id: 1,
        label: "Alice".to_string(),
        properties: HashMap::new(),
    };
    engine.add_node("my_graph", node1).await?;

    // Add edges
    let edge = Edge {
        id: 1,
        source: 1,
        target: 2,
        label: "follows".to_string(),
        weight: 1.0,
        properties: HashMap::new(),
    };
    engine.add_edge("my_graph", edge).await?;

    // Traverse the graph
    let nodes = engine.traverse_graph(
        "my_graph",
        1,
        TraversalMode::BreadthFirst,
        10
    ).await?;

    Ok(())
}

Graph Traversal

Breadth-First Search (BFS)

let nodes = engine.traverse_graph(
    "social_network",
    start_node,
    TraversalMode::BreadthFirst,
    max_depth
).await?;

Depth-First Search (DFS)

let nodes = engine.traverse_graph(
    "social_network",
    start_node,
    TraversalMode::DepthFirst,
    max_depth
).await?;

Path-Finding

Shortest Path (Dijkstra’s Algorithm)

let path = engine.shortest_path(
    "road_network",
    source_city,
    target_city
).await?;

if let Some(p) = path {
    println!("Shortest path cost: {}", p.cost);
    println!("Path: {:?}", p.nodes);
}

All Paths

Find all paths up to a maximum length:

let paths = engine.all_paths(
    "social_network",
    source,
    target,
    max_length,
    max_paths
).await?;

for path in paths {
    println!("Path: {:?} (cost: {})", path.nodes, path.cost);
}

Recursive CTEs

Build recursive queries for hierarchical data:

use heliosdb_graph::cte::*;

let cte = RecursiveCTEBuilder::new("descendants")
    .columns(vec!["id".to_string(), "parent_id".to_string(), "depth".to_string()])
    .max_depth(10)
    .detect_cycles(true)
    .build();

let results = engine.execute_recursive_cte(&cte).await?;

SQL-Style Recursive CTE Example

WITH RECURSIVE descendants AS (
    -- Anchor: Start with the root employee
    SELECT id, name, parent_id, 0 AS depth
    FROM employees
    WHERE id = 1

    UNION ALL

    -- Recursive: Find children
    SELECT e.id, e.name, e.parent_id, d.depth + 1
    FROM employees e
    JOIN descendants d ON e.parent_id = d.id
    WHERE d.depth < 10
)
SELECT * FROM descendants;

Cycle Detection

Detect cycles in directed graphs:

let cycles = engine.detect_cycles("graph_name").await?;

if !cycles.is_empty() {
    println!("Found {} cycles", cycles.len());
    for cycle in cycles {
        println!("Cycle: {:?}", cycle);
    }
}

Graph Algorithms

Connected Components

let components = engine.connected_components("graph_name").await?;
println!("Found {} components", components.len());

PageRank

use heliosdb_graph::algorithms::pagerank;

let ranks = pagerank(&graph, damping_factor, iterations)?;
for (node_id, rank) in ranks {
    println!("Node {} has PageRank: {:.4}", node_id, rank);
}

Topological Sort

use heliosdb_graph::algorithms::topological_sort;

let sorted = topological_sort(&graph)?;
println!("Topological order: {:?}", sorted);

Configuration

Customize the graph engine behavior:

let config = GraphConfig {
    max_depth: 100,              // Maximum traversal depth
    max_paths: 1000,             // Maximum paths to return
    enable_cycle_detection: true, // Enable cycle detection
    max_iterations: 10000,       // Max iterations for recursive CTEs
    cache_size: 10000,           // Path query cache size
    enable_optimization: true,   // Enable query optimization
};

let engine = GraphEngine::new(config).await?;

Examples

Social Network Analysis

See examples/social_network.rs for a complete example of:

• Finding shortest paths between users
• Discovering mutual connections
• Computing influence with PageRank
• Detecting social circles (cycles)

Run the example:

cargo run --example social_network

Organization Chart

See examples/org_chart.rs for:

• Employee hierarchy traversal
• Finding all reports (direct and indirect)
• Computing management chains
• Span of control analysis

Run the example:

cargo run --example org_chart

Performance

• Adjacency List Indexes: O(1) neighbor lookup
• BFS/DFS Traversal: O(V + E) time complexity
• Dijkstra’s Algorithm: O((V + E) log V) with binary heap
• Cycle Detection: O(V + E) using DFS
• Connected Components: O(V + E)

Testing

Run the test suite:

# All tests
cargo test

# Integration tests only
cargo test --test integration_test

# With output
cargo test -- --nocapture

Test coverage: >80%

Use Cases

1. Social Networks

   • Friend recommendations
   • Influence analysis
   • Community detection

2. Organization Charts

   • Reporting structure
   • Management chains
   • Span of control

3. Road Networks

   • Route planning
   • Traffic analysis
   • Distance calculations

4. Dependency Graphs

   • Package dependencies
   • Build order
   • Circular dependency detection

5. Knowledge Graphs

   • Concept relationships
   • Inference chains
   • Semantic search

Architecture

See ARCHITECTURE.md for detailed architecture documentation.

Contributing

Contributions are welcome! Please ensure:

• All tests pass
• Code coverage remains >80%
• Documentation is updated
• Examples work correctly

License

MIT OR Apache-2.0