okf_studio/graph/
model.rs

1//! Extraction of the graph model from a loaded bundle: the same edges the
2//! `okf graph` command prints, kept as typed nodes and edges so the canvas
3//! can style them distinctly.
4
5use okf_core::{Bundle, ConceptId, ResourceKind};
6use std::collections::HashMap;
7
8/// What a node represents.
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum NodeKind {
11    /// An ordinary concept.
12    Concept,
13    /// An Attested Computation concept.
14    Computation,
15    /// A phantom node: the target of a broken link, not present on disk.
16    Phantom,
17    /// An external source (URL or scope descriptor from `sources`).
18    Source,
19}
20
21/// One node in the graph.
22#[derive(Clone, Debug)]
23pub struct GraphNode {
24    /// A stable string key (the concept id, raw link target, or source
25    /// label). Layout positions persist across snapshots under this key.
26    pub key: String,
27    /// The display label.
28    pub label: String,
29    /// The node's kind.
30    pub kind: NodeKind,
31    /// The concept id, when the node is a concept.
32    pub id: Option<ConceptId>,
33    /// Total degree, used for label prioritization and hub repulsion.
34    pub degree: usize,
35}
36
37/// The kind of an edge.
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub enum EdgeKind {
40    /// A markdown cross-link.
41    Link,
42    /// A derivation edge (`sources[].resource` naming another concept).
43    Derivation,
44    /// A link whose target does not exist.
45    Broken,
46    /// An edge from a concept to one of its external sources.
47    Source,
48}
49
50/// One directed edge, as indices into [`GraphModel::nodes`].
51#[derive(Clone, Copy, Debug)]
52pub struct GraphEdge {
53    /// Index of the source node.
54    pub from: usize,
55    /// Index of the target node.
56    pub to: usize,
57    /// The edge's kind.
58    pub kind: EdgeKind,
59}
60
61/// The extracted graph.
62#[derive(Clone, Debug, Default)]
63pub struct GraphModel {
64    /// All nodes. Concepts first, then phantom targets, then sources.
65    pub nodes: Vec<GraphNode>,
66    /// All edges.
67    pub edges: Vec<GraphEdge>,
68}
69
70impl GraphModel {
71    /// Builds the model from a bundle.
72    #[must_use]
73    pub fn build(bundle: &Bundle) -> Self {
74        let mut nodes: Vec<GraphNode> = Vec::new();
75        let mut index: HashMap<String, usize> = HashMap::new();
76
77        for concept in bundle.concepts() {
78            let key = concept.id.to_string();
79            let kind = if concept.attested_computation().is_some() {
80                NodeKind::Computation
81            } else {
82                NodeKind::Concept
83            };
84            index.insert(key.clone(), nodes.len());
85            nodes.push(GraphNode {
86                label: key.clone(),
87                key,
88                kind,
89                id: Some(concept.id.clone()),
90                degree: 0,
91            });
92        }
93
94        let mut edges: Vec<GraphEdge> = Vec::new();
95        for concept in bundle.concepts() {
96            let from = index[&concept.id.to_string()];
97            for link in bundle.links_from(&concept.id) {
98                if link.exists {
99                    if let Some(&to) = index.get(&link.target.to_string()) {
100                        edges.push(GraphEdge {
101                            from,
102                            to,
103                            kind: EdgeKind::Link,
104                        });
105                    }
106                } else {
107                    let key = format!("✗{}", link.target);
108                    let to = *index.entry(key.clone()).or_insert_with(|| {
109                        nodes.push(GraphNode {
110                            label: link.target.to_string(),
111                            key,
112                            kind: NodeKind::Phantom,
113                            id: None,
114                            degree: 0,
115                        });
116                        nodes.len() - 1
117                    });
118                    edges.push(GraphEdge {
119                        from,
120                        to,
121                        kind: EdgeKind::Broken,
122                    });
123                }
124            }
125            for source in bundle.sources_of(&concept.id) {
126                if let Some(target) = &source.concept {
127                    if let Some(&to) = index.get(&target.to_string()) {
128                        edges.push(GraphEdge {
129                            from,
130                            to,
131                            kind: EdgeKind::Derivation,
132                        });
133                    }
134                } else if matches!(
135                    source.source.resource_kind(),
136                    ResourceKind::Url | ResourceKind::Scope | ResourceKind::Path
137                ) {
138                    let label = source.source.label().to_string();
139                    let key = format!("src:{label}");
140                    let to = *index.entry(key.clone()).or_insert_with(|| {
141                        nodes.push(GraphNode {
142                            label,
143                            key,
144                            kind: NodeKind::Source,
145                            id: None,
146                            degree: 0,
147                        });
148                        nodes.len() - 1
149                    });
150                    edges.push(GraphEdge {
151                        from,
152                        to,
153                        kind: EdgeKind::Source,
154                    });
155                }
156            }
157        }
158
159        for edge in &edges {
160            nodes[edge.from].degree += 1;
161            nodes[edge.to].degree += 1;
162        }
163
164        Self { nodes, edges }
165    }
166
167    /// The node index for a concept id, if present.
168    #[must_use]
169    pub fn node_of(&self, id: &ConceptId) -> Option<usize> {
170        self.nodes.iter().position(|n| n.id.as_ref() == Some(id))
171    }
172
173    /// The set of node indices within `k` hops of `center` (undirected),
174    /// including `center` itself.
175    #[must_use]
176    pub fn neighborhood(&self, center: usize, k: usize) -> Vec<bool> {
177        let mut included = vec![false; self.nodes.len()];
178        if center >= self.nodes.len() {
179            return included;
180        }
181        included[center] = true;
182        let mut frontier = vec![center];
183        for _ in 0..k {
184            let mut next = Vec::new();
185            for edge in &self.edges {
186                for (a, b) in [(edge.from, edge.to), (edge.to, edge.from)] {
187                    if frontier.contains(&a) && !included[b] {
188                        included[b] = true;
189                        next.push(b);
190                    }
191                }
192            }
193            frontier = next;
194        }
195        included
196    }
197}
okf_studio/graph/model.rs

okf_studio/graph/
model.rs
