vibe_graph_layout_gpu/
lib.rs

1//! GPU-accelerated force-directed graph layout using WebGPU.
2//!
3//! This crate provides a high-performance Barnes-Hut force-directed layout
4//! algorithm that runs on the GPU via wgpu, supporting both native (Vulkan/Metal/DX12)
5//! and web (WebGPU) platforms.
6//!
7//! ## Architecture
8//!
9//! ```text
10//! ┌─────────────────────────────────────────────────────────────┐
11//! │                        CPU Side                             │
12//! │  ┌─────────────┐    ┌─────────────┐    ┌─────────────┐     │
13//! │  │ Graph Data  │───▶│  Quadtree   │───▶│ GPU Buffers │     │
14//! │  │ (positions) │    │ (Barnes-Hut)│    │  (upload)   │     │
15//! │  └─────────────┘    └─────────────┘    └─────────────┘     │
16//! └─────────────────────────────────────────────────────────────┘
17//!                              │
18//!                              ▼
19//! ┌─────────────────────────────────────────────────────────────┐
20//! │                        GPU Side                             │
21//! │  ┌─────────────┐    ┌─────────────┐    ┌─────────────┐     │
22//! │  │  Repulsive  │───▶│  Attractive │───▶│  Integrate  │     │
23//! │  │   Forces    │    │   Forces    │    │  Positions  │     │
24//! │  │ (BH approx) │    │  (edges)    │    │             │     │
25//! │  └─────────────┘    └─────────────┘    └─────────────┘     │
26//! └─────────────────────────────────────────────────────────────┘
27//!                              │
28//!                              ▼
29//! ┌─────────────────────────────────────────────────────────────┐
30//! │                      Read Back                              │
31//! │  Updated positions copied back to CPU for rendering         │
32//! └─────────────────────────────────────────────────────────────┘
33//! ```
34//!
35//! ## Performance
36//!
37//! - Traditional Fruchterman-Reingold: O(n²) per iteration
38//! - Barnes-Hut approximation: O(n log n) per iteration
39//! - GPU parallelization: ~100x speedup for large graphs
40//!
41//! For a 10,000 node graph:
42//! - CPU O(n²): ~100M operations → ~10 FPS
43//! - GPU Barnes-Hut: ~100K operations, parallelized → 60+ FPS
44
45mod error;
46mod gpu;
47mod layout;
48mod quadtree;
49mod shaders;
50
51pub use error::LayoutError;
52pub use layout::{GpuLayout, LayoutConfig, LayoutState};
53pub use quadtree::QuadTree;
54
55/// Result type for layout operations.
56pub type Result<T> = std::result::Result<T, LayoutError>;
57
58/// A 2D position.
59#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
60#[repr(C)]
61pub struct Position {
62    pub x: f32,
63    pub y: f32,
64}
65
66impl Position {
67    pub fn new(x: f32, y: f32) -> Self {
68        Self { x, y }
69    }
70}
71
72/// A 2D velocity.
73#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
74#[repr(C)]
75pub struct Velocity {
76    pub x: f32,
77    pub y: f32,
78}
79
80/// An edge between two nodes.
81#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
82#[repr(C)]
83pub struct Edge {
84    pub source: u32,
85    pub target: u32,
86}
87
88impl Edge {
89    pub fn new(source: u32, target: u32) -> Self {
90        Self { source, target }
91    }
92}
93
94/// Barnes-Hut quadtree node for GPU upload.
95/// This is a flattened representation suitable for GPU processing.
96#[derive(Debug, Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
97#[repr(C)]
98pub struct QuadTreeNode {
99    /// Center of mass X
100    pub center_x: f32,
101    /// Center of mass Y
102    pub center_y: f32,
103    /// Total mass (number of nodes in this cell)
104    pub mass: f32,
105    /// Cell width (for Barnes-Hut theta criterion)
106    pub width: f32,
107    /// Index of first child (-1 if leaf or empty)
108    pub child_nw: i32,
109    pub child_ne: i32,
110    pub child_sw: i32,
111    pub child_se: i32,
112}
113
114/// Layout parameters for the force-directed algorithm.
115#[derive(Debug, Clone, Copy)]
116#[repr(C)]
117pub struct LayoutParams {
118    /// Number of nodes
119    pub node_count: u32,
120    /// Number of edges
121    pub edge_count: u32,
122    /// Number of quadtree nodes
123    pub tree_size: u32,
124    /// Time step
125    pub dt: f32,
126    /// Damping factor (0-1, higher = more damping)
127    pub damping: f32,
128    /// Repulsion strength
129    pub repulsion: f32,
130    /// Attraction strength
131    pub attraction: f32,
132    /// Barnes-Hut theta (0.5-1.0, higher = faster but less accurate)
133    pub theta: f32,
134    /// Center gravity strength
135    pub gravity: f32,
136    /// Ideal edge length
137    pub ideal_length: f32,
138}
139
140impl Default for LayoutParams {
141    fn default() -> Self {
142        Self {
143            node_count: 0,
144            edge_count: 0,
145            tree_size: 0,
146            dt: 0.016, // ~60 FPS
147            damping: 0.9,
148            repulsion: 1000.0,
149            attraction: 0.01,
150            theta: 0.8, // Good balance of speed/accuracy
151            gravity: 0.1,
152            ideal_length: 50.0,
153        }
154    }
155}
156
157// Ensure LayoutParams is Pod-compatible by implementing manually
158unsafe impl bytemuck::Pod for LayoutParams {}
159unsafe impl bytemuck::Zeroable for LayoutParams {}
vibe_graph_layout_gpu/lib.rs

vibe_graph_layout_gpu/
lib.rs
