node-based graph editor
git clone https://git.lucas.co/cce-graph.git
src/linkgraph.rs (16.7K)
1 //! The vault as a link graph: one node per note (plus a ghost per link
2 //! target that does not exist yet, as Obsidian shows them), an edge per
3 //! pair of notes linked either way, and a force layout that cools and
4 //! stops so the app goes idle once the picture settles.
5 //!
6 //! Pure model, no drawing: positions are world units, the app owns the
7 //! camera. Kept apart from cce-ui's `Graph` widget on purpose — ports,
8 //! grid snapping and name-keyed wires are node-editor semantics, and a
9 //! vault of thousands of notes needs id-keyed edges and a spatial grid.
10
11 use std::collections::{HashMap, HashSet, VecDeque};
12
13 use cce_vault::index::stem;
14 use cce_vault::{FileKind, Index};
15
16 /// The rest length of a link's spring.
17 const LINK_LEN: f32 = 90.0;
18 const LINK_K: f32 = 0.08;
19 const REPULSE: f32 = 9000.0;
20 /// Repulsion only reaches this far; past it the centering pull dominates
21 /// anyway. It is also the spatial grid's cell size.
22 const REPULSE_RANGE: f32 = 300.0;
23 const CENTER_K: f32 = 0.006;
24 const DAMPING: f32 = 0.55;
25 const COOLING: f32 = 0.985;
26 /// Below this temperature the layout is settled and stops stepping.
27 const SETTLED: f32 = 0.004;
28
29 #[derive(Clone, Debug)]
30 pub struct Node {
31 /// The note's vault path; for a ghost, the link text that resolves
32 /// nowhere.
33 pub path: String,
34 pub name: String,
35 pub ghost: bool,
36 pub tags: Vec<String>,
37 pub pos: (f32, f32),
38 vel: (f32, f32),
39 /// Held where the user dropped it.
40 pub pinned: bool,
41 }
42
43 #[derive(Default)]
44 pub struct LinkGraph {
45 pub nodes: Vec<Node>,
46 pub edges: Vec<(usize, usize)>,
47 adj: Vec<Vec<usize>>,
48 by_path: HashMap<String, usize>,
49 /// The layout's temperature: forces scale with it, and it decays.
50 pub alpha: f32,
51 }
52
53 impl LinkGraph {
54 /// Build from the index. Nodes that were in `prev` keep their place;
55 /// new ones start next to a neighbour already placed, or on a spiral.
56 pub fn build(ix: &Index, prev: Option<&LinkGraph>) -> LinkGraph {
57 let mut g = LinkGraph::default();
58 let mut notes: Vec<&str> = ix.files().iter().filter(|(_, e)| e.kind == FileKind::Note).map(|(p, _)| p.as_str()).collect();
59 notes.sort();
60 for p in notes {
61 let tags = ix.note(p).map(|n| n.tags.iter().map(|t| t.name.to_lowercase()).collect()).unwrap_or_default();
62 g.add(Node { path: p.to_string(), name: stem(p).to_string(), ghost: false, tags, pos: (0.0, 0.0), vel: (0.0, 0.0), pinned: false });
63 }
64 let mut seen: HashSet<(usize, usize)> = HashSet::new();
65 let count = g.nodes.len();
66 for i in 0..count {
67 let from = g.nodes[i].path.clone();
68 for (link, target) in ix.outgoing(&from) {
69 let j = match target {
70 Some(t) => match g.by_path.get(t) {
71 Some(&j) => j,
72 // A link to an attachment or canvas: not drawn.
73 None => continue,
74 },
75 None => {
76 let key = format!("?{}", link.target.to_lowercase());
77 match g.by_path.get(&key) {
78 Some(&j) => j,
79 None => g.add(Node {
80 path: key,
81 name: link.target.clone(),
82 ghost: true,
83 tags: Vec::new(),
84 pos: (0.0, 0.0),
85 vel: (0.0, 0.0),
86 pinned: false,
87 }),
88 }
89 }
90 };
91 if i != j && seen.insert((i.min(j), i.max(j))) {
92 g.edges.push((i.min(j), i.max(j)));
93 }
94 }
95 }
96 g.adj = vec![Vec::new(); g.nodes.len()];
97 for &(a, b) in &g.edges {
98 g.adj[a].push(b);
99 g.adj[b].push(a);
100 }
101 g.place(prev);
102 g.alpha = 1.0;
103 g
104 }
105
106 fn add(&mut self, node: Node) -> usize {
107 let i = self.nodes.len();
108 self.by_path.insert(node.path.clone(), i);
109 self.nodes.push(node);
110 i
111 }
112
113 fn place(&mut self, prev: Option<&LinkGraph>) {
114 let mut placed = vec![false; self.nodes.len()];
115 if let Some(prev) = prev {
116 for (i, n) in self.nodes.iter_mut().enumerate() {
117 if let Some(&j) = prev.by_path.get(&n.path) {
118 n.pos = prev.nodes[j].pos;
119 n.pinned = prev.nodes[j].pinned;
120 placed[i] = true;
121 }
122 }
123 }
124 // A golden-angle spiral spreads the rest without overlaps; a new
125 // note with a placed neighbour starts beside it instead.
126 for i in 0..self.nodes.len() {
127 if placed[i] {
128 continue;
129 }
130 let near = self.adj[i].iter().find(|&&j| placed[j]).map(|&j| self.nodes[j].pos);
131 let t = i as f32 * 2.399_963;
132 self.nodes[i].pos = match near {
133 Some((x, y)) => (x + 20.0 * t.cos(), y + 20.0 * t.sin()),
134 None => {
135 let r = 18.0 * (i as f32 + 1.0).sqrt();
136 (r * t.cos(), r * t.sin())
137 }
138 };
139 placed[i] = true;
140 }
141 }
142
143 pub fn len(&self) -> usize {
144 self.nodes.len()
145 }
146
147 pub fn index_of(&self, path: &str) -> Option<usize> {
148 self.by_path.get(path).copied()
149 }
150
151 pub fn neighbors(&self, i: usize) -> &[usize] {
152 &self.adj[i]
153 }
154
155 pub fn degree(&self, i: usize) -> usize {
156 self.adj[i].len()
157 }
158
159 /// Draw radius: grows with the number of links, as Obsidian's does.
160 pub fn radius(&self, i: usize) -> f32 {
161 3.5 + (self.degree(i) as f32).sqrt() * 2.2
162 }
163
164 /// Every node within `hops` links of `center`.
165 pub fn within(&self, center: usize, hops: usize) -> Vec<bool> {
166 let mut seen = vec![false; self.nodes.len()];
167 let mut queue = VecDeque::from([(center, 0usize)]);
168 seen[center] = true;
169 while let Some((i, d)) = queue.pop_front() {
170 if d == hops {
171 continue;
172 }
173 for &j in &self.adj[i] {
174 if !seen[j] {
175 seen[j] = true;
176 queue.push_back((j, d + 1));
177 }
178 }
179 }
180 seen
181 }
182
183 pub fn reheat(&mut self, to: f32) {
184 self.alpha = self.alpha.max(to);
185 }
186
187 pub fn settled(&self) -> bool {
188 self.alpha < SETTLED
189 }
190
191 /// One step of the layout over the `visible` nodes (the others are
192 /// frozen and exert nothing). False once settled.
193 pub fn step(&mut self, visible: &[bool]) -> bool {
194 if self.settled() {
195 return false;
196 }
197 let n = self.nodes.len();
198 let mut force = vec![(0.0f32, 0.0f32); n];
199
200 // Repulsion between nodes sharing or neighbouring a grid cell.
201 let cell = |p: (f32, f32)| ((p.0 / REPULSE_RANGE).floor() as i32, (p.1 / REPULSE_RANGE).floor() as i32);
202 let mut grid: HashMap<(i32, i32), Vec<usize>> = HashMap::new();
203 for i in (0..n).filter(|&i| visible[i]) {
204 grid.entry(cell(self.nodes[i].pos)).or_default().push(i);
205 }
206 let range2 = REPULSE_RANGE * REPULSE_RANGE;
207 for (&(cx, cy), members) in &grid {
208 for dx in -1..=1 {
209 for dy in -1..=1 {
210 let Some(others) = grid.get(&(cx + dx, cy + dy)) else { continue };
211 for &i in members {
212 for &j in others {
213 if j <= i {
214 continue;
215 }
216 let (pi, pj) = (self.nodes[i].pos, self.nodes[j].pos);
217 let (mut ddx, mut ddy) = (pi.0 - pj.0, pi.1 - pj.1);
218 let mut d2 = ddx * ddx + ddy * ddy;
219 if d2 > range2 {
220 continue;
221 }
222 if d2 < 0.01 {
223 // Coincident: nudge apart deterministically.
224 ddx = 0.1 * ((i as f32).sin() + 0.5);
225 ddy = 0.1 * ((j as f32).cos() + 0.5);
226 d2 = ddx * ddx + ddy * ddy;
227 }
228 let f = REPULSE / d2.max(25.0);
229 let d = d2.sqrt();
230 let (fx, fy) = (ddx / d * f, ddy / d * f);
231 force[i].0 += fx;
232 force[i].1 += fy;
233 force[j].0 -= fx;
234 force[j].1 -= fy;
235 }
236 }
237 }
238 }
239 }
240 // Springs along the links.
241 for &(a, b) in &self.edges {
242 if !(visible[a] && visible[b]) {
243 continue;
244 }
245 let (pa, pb) = (self.nodes[a].pos, self.nodes[b].pos);
246 let (dx, dy) = (pb.0 - pa.0, pb.1 - pa.1);
247 let d = (dx * dx + dy * dy).sqrt().max(0.01);
248 let f = (d - LINK_LEN) * LINK_K;
249 let (fx, fy) = (dx / d * f, dy / d * f);
250 force[a].0 += fx;
251 force[a].1 += fy;
252 force[b].0 -= fx;
253 force[b].1 -= fy;
254 }
255 // A gentle pull to the middle keeps islands and orphans in view.
256 let mut moving = false;
257 for i in (0..n).filter(|&i| visible[i]) {
258 let node = &mut self.nodes[i];
259 if node.pinned {
260 node.vel = (0.0, 0.0);
261 continue;
262 }
263 let (fx, fy) = (force[i].0 - node.pos.0 * CENTER_K, force[i].1 - node.pos.1 * CENTER_K);
264 node.vel.0 = (node.vel.0 + fx * self.alpha) * DAMPING;
265 node.vel.1 = (node.vel.1 + fy * self.alpha) * DAMPING;
266 // Cap a step, so a cold start cannot fling a node away.
267 let speed = (node.vel.0 * node.vel.0 + node.vel.1 * node.vel.1).sqrt();
268 if speed > 40.0 {
269 node.vel.0 *= 40.0 / speed;
270 node.vel.1 *= 40.0 / speed;
271 }
272 node.pos.0 += node.vel.0;
273 node.pos.1 += node.vel.1;
274 moving |= speed > 0.05;
275 }
276 self.alpha *= COOLING;
277 if !moving {
278 self.alpha = 0.0;
279 }
280 !self.settled()
281 }
282
283 /// The topmost visible node within its radius (plus `slop`) of a world
284 /// point.
285 pub fn hit(&self, visible: &[bool], x: f32, y: f32, slop: f32) -> Option<usize> {
286 let mut best: Option<(usize, f32)> = None;
287 for i in (0..self.nodes.len()).filter(|&i| visible[i]) {
288 let (px, py) = self.nodes[i].pos;
289 let d2 = (px - x).powi(2) + (py - y).powi(2);
290 let r = self.radius(i) + slop;
291 if d2 <= r * r && best.is_none_or(|(_, b)| d2 < b) {
292 best = Some((i, d2));
293 }
294 }
295 best.map(|(i, _)| i)
296 }
297
298 /// The bounds of the visible nodes, as (min, max).
299 pub fn bounds(&self, visible: &[bool]) -> Option<((f32, f32), (f32, f32))> {
300 let mut it = (0..self.nodes.len()).filter(|&i| visible[i]).map(|i| self.nodes[i].pos);
301 let first = it.next()?;
302 Some(it.fold((first, first), |(lo, hi), p| ((lo.0.min(p.0), lo.1.min(p.1)), (hi.0.max(p.0), hi.1.max(p.1)))))
303 }
304 }
305
306 /// What the filter box asks for: every term must match. `#tag` matches a
307 /// note carrying the tag (or one nested under it), `path:x` a path
308 /// containing `x`, anything else a name containing it.
309 #[derive(Default, Debug, PartialEq)]
310 pub struct Filter {
311 tags: Vec<String>,
312 paths: Vec<String>,
313 words: Vec<String>,
314 }
315
316 impl Filter {
317 pub fn parse(q: &str) -> Filter {
318 let mut f = Filter::default();
319 for term in q.split_whitespace() {
320 let t = term.to_lowercase();
321 if let Some(tag) = t.strip_prefix('#').or_else(|| t.strip_prefix("tag:")) {
322 if !tag.is_empty() {
323 f.tags.push(tag.to_string());
324 }
325 } else if let Some(p) = t.strip_prefix("path:") {
326 if !p.is_empty() {
327 f.paths.push(p.to_string());
328 }
329 } else {
330 f.words.push(t);
331 }
332 }
333 f
334 }
335
336 pub fn is_empty(&self) -> bool {
337 self.tags.is_empty() && self.paths.is_empty() && self.words.is_empty()
338 }
339
340 pub fn matches(&self, n: &Node) -> bool {
341 let name = n.name.to_lowercase();
342 let path = n.path.to_lowercase();
343 self.words.iter().all(|w| name.contains(w.as_str()))
344 && self.paths.iter().all(|p| !n.ghost && path.contains(p.as_str()))
345 && self.tags.iter().all(|t| n.tags.iter().any(|nt| nt == t || nt.starts_with(&format!("{t}/"))))
346 }
347 }
348
349 #[cfg(test)]
350 mod tests {
351 use super::*;
352
353 fn vault(files: &[(&str, &str)]) -> (tempfile::TempDir, Index) {
354 let dir = tempfile::tempdir().unwrap();
355 for (p, t) in files {
356 let abs = dir.path().join(p);
357 std::fs::create_dir_all(abs.parent().unwrap()).unwrap();
358 std::fs::write(abs, t).unwrap();
359 }
360 let ix = Index::open(dir.path(), false).unwrap();
361 (dir, ix)
362 }
363
364 fn sample() -> (tempfile::TempDir, Index) {
365 vault(&[
366 ("A.md", "[[B]] [[C]] [[Nowhere]] #proj\n"),
367 ("B.md", "[[A]] back again\n"),
368 ("dir/C.md", "[[D]]\n"),
369 ("D.md", "end #proj/sub\n"),
370 ("Lone.md", "no links\n"),
371 ("pic.png", "x"),
372 ])
373 }
374
375 #[test]
376 fn nodes_edges_and_ghosts() {
377 let (_d, ix) = sample();
378 let g = LinkGraph::build(&ix, None);
379 let names: Vec<&str> = g.nodes.iter().map(|n| n.name.as_str()).collect();
380 assert_eq!(names, ["A", "B", "D", "Lone", "C", "Nowhere"]);
381 assert!(g.nodes[5].ghost);
382 // A–B once although linked both ways; A–C, A–Nowhere, C–D.
383 assert_eq!(g.edges.len(), 4);
384 let a = g.index_of("A.md").unwrap();
385 assert_eq!(g.degree(a), 3);
386 assert!(g.radius(a) > g.radius(g.index_of("Lone.md").unwrap()));
387 }
388
389 #[test]
390 fn hops_reach_the_neighbourhood() {
391 let (_d, ix) = sample();
392 let g = LinkGraph::build(&ix, None);
393 let d = g.index_of("D.md").unwrap();
394 let names = |v: Vec<bool>| -> Vec<String> {
395 v.iter().enumerate().filter(|(_, &s)| s).map(|(i, _)| g.nodes[i].name.clone()).collect()
396 };
397 assert_eq!(names(g.within(d, 1)), ["D", "C"]);
398 assert_eq!(names(g.within(d, 2)), ["A", "D", "C"]);
399 }
400
401 #[test]
402 fn layout_settles_and_keeps_links_short() {
403 let (_d, ix) = sample();
404 let mut g = LinkGraph::build(&ix, None);
405 let all = vec![true; g.len()];
406 let mut steps = 0;
407 while g.step(&all) {
408 steps += 1;
409 assert!(steps < 2000, "never settled");
410 }
411 let dist = |a: &str, b: &str| {
412 let (p, q) = (g.nodes[g.index_of(a).unwrap()].pos, g.nodes[g.index_of(b).unwrap()].pos);
413 ((p.0 - q.0).powi(2) + (p.1 - q.1).powi(2)).sqrt()
414 };
415 // Linked notes sit closer than an unlinked pair.
416 assert!(dist("A.md", "B.md") < dist("B.md", "D.md"), "{} vs {}", dist("A.md", "B.md"), dist("B.md", "D.md"));
417 assert!(g.nodes.iter().all(|n| n.pos.0.is_finite() && n.pos.1.is_finite()));
418 }
419
420 #[test]
421 fn rebuild_keeps_positions_and_pins() {
422 let (_d, ix) = sample();
423 let mut g = LinkGraph::build(&ix, None);
424 let a = g.index_of("A.md").unwrap();
425 g.nodes[a].pos = (500.0, -40.0);
426 g.nodes[a].pinned = true;
427 let g2 = LinkGraph::build(&ix, Some(&g));
428 let a2 = g2.index_of("A.md").unwrap();
429 assert_eq!(g2.nodes[a2].pos, (500.0, -40.0));
430 assert!(g2.nodes[a2].pinned);
431 }
432
433 #[test]
434 fn filters_by_name_path_and_tag() {
435 let (_d, ix) = sample();
436 let g = LinkGraph::build(&ix, None);
437 let hits = |q: &str| -> Vec<String> {
438 let f = Filter::parse(q);
439 g.nodes.iter().filter(|n| f.matches(n)).map(|n| n.name.clone()).collect()
440 };
441 assert_eq!(hits("a"), ["A"]);
442 assert_eq!(hits("path:dir/"), ["C"]);
443 assert_eq!(hits("#proj"), ["A", "D"]);
444 assert_eq!(hits("tag:proj/sub"), ["D"]);
445 assert!(Filter::parse(" ").is_empty());
446 }
447
448 #[test]
449 fn hit_finds_the_nearest_visible_node() {
450 let (_d, ix) = sample();
451 let mut g = LinkGraph::build(&ix, None);
452 for (i, n) in g.nodes.iter_mut().enumerate() {
453 n.pos = (i as f32 * 100.0, 0.0);
454 }
455 let mut vis = vec![true; g.len()];
456 assert_eq!(g.hit(&vis, 101.0, 2.0, 0.0), Some(1));
457 vis[1] = false;
458 assert_eq!(g.hit(&vis, 101.0, 2.0, 0.0), None);
459 }
460 }