agm_core/graph/
mod.rs

1//! Graph engine: dependency graph operations on AGM nodes.
2//!
3//! Builds a `petgraph`-backed directed graph from AGM node relationships
4//! and provides topological sort, cycle detection, and transitive dependency
5//! queries.
6
7use std::collections::HashMap;
8
9use petgraph::graph::{DiGraph, NodeIndex};
10use petgraph::visit::EdgeRef;
11use serde::{Deserialize, Serialize};
12
13pub mod build;
14pub mod cycles;
15pub mod query;
16pub mod topo;
17
18pub use build::{build_graph, build_graph_with_imports};
19pub use cycles::{CycleError, detect_cycles};
20pub use query::{find_conflicts, transitive_dependents, transitive_deps};
21pub use topo::topological_sort;
22
23// ---------------------------------------------------------------------------
24// RelationKind
25// ---------------------------------------------------------------------------
26
27/// The kind of relationship between two AGM nodes.
28///
29/// Maps 1:1 to the five relationship fields in the AGM spec (S15).
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
31pub enum RelationKind {
32    /// Strong ordering dependency (`depends` field).
33    Depends,
34    /// Informational relationship (`related_to` field).
35    RelatedTo,
36    /// This node supersedes the target (`replaces` field).
37    Replaces,
38    /// Mutual exclusion (`conflicts` field).
39    Conflicts,
40    /// Cross-reference for context (`see_also` field).
41    SeeAlso,
42}
43
44// ---------------------------------------------------------------------------
45// AgmGraph
46// ---------------------------------------------------------------------------
47
48/// Directed graph of AGM nodes and their relationships.
49///
50/// Node weights are node ID strings. Edge weights are `RelationKind`.
51/// Provides an internal index for O(1) ID-to-`NodeIndex` lookup.
52#[derive(Debug, Clone)]
53pub struct AgmGraph {
54    /// The underlying petgraph directed graph.
55    pub(crate) inner: DiGraph<String, RelationKind>,
56    /// Maps node ID strings to their petgraph `NodeIndex` for O(1) lookup.
57    pub(crate) index: HashMap<String, NodeIndex>,
58}
59
60impl AgmGraph {
61    /// Returns the number of nodes in the graph.
62    #[must_use]
63    pub fn node_count(&self) -> usize {
64        self.inner.node_count()
65    }
66
67    /// Returns the number of edges in the graph.
68    #[must_use]
69    pub fn edge_count(&self) -> usize {
70        self.inner.edge_count()
71    }
72
73    /// Returns `true` if a node with the given ID exists in the graph.
74    #[must_use]
75    pub fn contains_node(&self, node_id: &str) -> bool {
76        self.index.contains_key(node_id)
77    }
78
79    /// Returns the `NodeIndex` for the given node ID, if it exists.
80    #[must_use]
81    pub fn node_index(&self, node_id: &str) -> Option<NodeIndex> {
82        self.index.get(node_id).copied()
83    }
84
85    /// Returns all node IDs in the graph (unordered).
86    #[must_use]
87    pub fn node_ids(&self) -> Vec<&str> {
88        self.index.keys().map(String::as_str).collect()
89    }
90
91    /// Returns the target node IDs of edges of a specific kind originating
92    /// from the given node.
93    #[must_use]
94    pub fn edges_of_kind(&self, node_id: &str, kind: RelationKind) -> Vec<&str> {
95        let Some(&idx) = self.index.get(node_id) else {
96            return vec![];
97        };
98        self.inner
99            .edges(idx)
100            .filter(|e| *e.weight() == kind)
101            .map(|e| self.inner[e.target()].as_str())
102            .collect()
103    }
104}
105
106// ---------------------------------------------------------------------------
107// depends_subgraph
108// ---------------------------------------------------------------------------
109
110/// Creates a subgraph containing only `Depends` edges.
111///
112/// All nodes are preserved. Only edges with weight `RelationKind::Depends`
113/// are copied. Returns the filtered graph and a mapping from new `NodeIndex`
114/// to original node ID string.
115pub(crate) fn depends_subgraph(graph: &AgmGraph) -> DiGraph<String, ()> {
116    let mut sub: DiGraph<String, ()> = DiGraph::new();
117    // Map original NodeIndex -> new NodeIndex in sub
118    let mut old_to_new: HashMap<NodeIndex, NodeIndex> = HashMap::new();
119
120    for node_idx in graph.inner.node_indices() {
121        let id = graph.inner[node_idx].clone();
122        let new_idx = sub.add_node(id);
123        old_to_new.insert(node_idx, new_idx);
124    }
125
126    for edge in graph.inner.edge_references() {
127        if *edge.weight() == RelationKind::Depends {
128            let src = old_to_new[&edge.source()];
129            let tgt = old_to_new[&edge.target()];
130            sub.add_edge(src, tgt, ());
131        }
132    }
133
134    sub
135}
136
137// ---------------------------------------------------------------------------
138// Test helpers
139// ---------------------------------------------------------------------------
140
141#[cfg(test)]
142pub(crate) mod test_helpers {
143    use crate::model::fields::{NodeType, Span};
144    use crate::model::file::{AgmFile, Header};
145    use crate::model::node::Node;
146
147    pub fn minimal_header() -> Header {
148        Header {
149            agm: "1.0".to_owned(),
150            package: "test.pkg".to_owned(),
151            version: "0.1.0".to_owned(),
152            title: None,
153            owner: None,
154            imports: None,
155            default_load: None,
156            description: None,
157            tags: None,
158            status: None,
159            load_profiles: None,
160            target_runtime: None,
161        }
162    }
163
164    pub fn make_node(id: &str) -> Node {
165        Node {
166            id: id.to_owned(),
167            node_type: NodeType::Facts,
168            summary: format!("test node {id}"),
169            span: Span::new(1, 1),
170            ..Default::default()
171        }
172    }
173
174    pub fn make_file(nodes: Vec<Node>) -> AgmFile {
175        AgmFile {
176            header: minimal_header(),
177            nodes,
178        }
179    }
180}
181
182// ---------------------------------------------------------------------------
183// Tests
184// ---------------------------------------------------------------------------
185
186#[cfg(test)]
187mod tests {
188    use super::*;
189    use test_helpers::*;
190
191    #[test]
192    fn test_relation_kind_debug_and_clone() {
193        let k = RelationKind::Depends;
194        let k2 = k;
195        assert_eq!(k, k2);
196        assert_eq!(format!("{k:?}"), "Depends");
197
198        let json = serde_json::to_string(&RelationKind::Conflicts).unwrap();
199        let back: RelationKind = serde_json::from_str(&json).unwrap();
200        assert_eq!(back, RelationKind::Conflicts);
201    }
202
203    #[test]
204    fn test_agm_graph_empty_returns_zero_counts() {
205        let graph = build_graph(&make_file(vec![]));
206        assert_eq!(graph.node_count(), 0);
207        assert_eq!(graph.edge_count(), 0);
208    }
209}
agm_core/graph/mod.rs

agm_core/graph/
mod.rs
