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 std::collections::BTreeMap;
144
145    use crate::model::fields::{NodeType, Span};
146    use crate::model::file::{AgmFile, Header};
147    use crate::model::node::Node;
148
149    pub fn minimal_header() -> Header {
150        Header {
151            agm: "1.0".to_owned(),
152            package: "test.pkg".to_owned(),
153            version: "0.1.0".to_owned(),
154            title: None,
155            owner: None,
156            imports: None,
157            default_load: None,
158            description: None,
159            tags: None,
160            status: None,
161            load_profiles: None,
162            target_runtime: None,
163        }
164    }
165
166    pub fn make_node(id: &str) -> Node {
167        Node {
168            id: id.to_owned(),
169            node_type: NodeType::Facts,
170            summary: format!("test node {id}"),
171            priority: None,
172            stability: None,
173            confidence: None,
174            status: None,
175            depends: None,
176            related_to: None,
177            replaces: None,
178            conflicts: None,
179            see_also: None,
180            items: None,
181            steps: None,
182            fields: None,
183            input: None,
184            output: None,
185            detail: None,
186            rationale: None,
187            tradeoffs: None,
188            resolution: None,
189            examples: None,
190            notes: None,
191            code: None,
192            code_blocks: None,
193            verify: None,
194            agent_context: None,
195            target: None,
196            execution_status: None,
197            executed_by: None,
198            executed_at: None,
199            execution_log: None,
200            retry_count: None,
201            parallel_groups: None,
202            memory: None,
203            scope: None,
204            applies_when: None,
205            valid_from: None,
206            valid_until: None,
207            tags: None,
208            aliases: None,
209            keywords: None,
210            extra_fields: BTreeMap::new(),
211            span: Span::new(1, 1),
212        }
213    }
214
215    pub fn make_file(nodes: Vec<Node>) -> AgmFile {
216        AgmFile {
217            header: minimal_header(),
218            nodes,
219        }
220    }
221}
222
223// ---------------------------------------------------------------------------
224// Tests
225// ---------------------------------------------------------------------------
226
227#[cfg(test)]
228mod tests {
229    use super::*;
230    use test_helpers::*;
231
232    #[test]
233    fn test_relation_kind_debug_and_clone() {
234        let k = RelationKind::Depends;
235        let k2 = k;
236        assert_eq!(k, k2);
237        assert_eq!(format!("{k:?}"), "Depends");
238
239        let json = serde_json::to_string(&RelationKind::Conflicts).unwrap();
240        let back: RelationKind = serde_json::from_str(&json).unwrap();
241        assert_eq!(back, RelationKind::Conflicts);
242    }
243
244    #[test]
245    fn test_agm_graph_empty_returns_zero_counts() {
246        let graph = build_graph(&make_file(vec![]));
247        assert_eq!(graph.node_count(), 0);
248        assert_eq!(graph.edge_count(), 0);
249    }
250}
agm_core/graph/mod.rs

agm_core/graph/
mod.rs
