ucm_core/
edge.rs

1//! Edge types and relationships between blocks.
2//!
3//! Edges represent explicit relationships between blocks, such as
4//! derivation, references, and semantic connections.
5
6use crate::id::BlockId;
7use chrono::{DateTime, Utc};
8use serde::{Deserialize, Serialize};
9use std::collections::HashMap;
10use std::error::Error as StdError;
11use std::fmt;
12use std::str::FromStr;
13
14/// An edge represents an explicit relationship between blocks
15#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
16pub struct Edge {
17    /// Type of relationship
18    pub edge_type: EdgeType,
19    /// Target block
20    pub target: BlockId,
21    /// Edge-specific metadata
22    #[serde(default, skip_serializing_if = "EdgeMetadata::is_empty")]
23    pub metadata: EdgeMetadata,
24    /// When the edge was created
25    pub created_at: DateTime<Utc>,
26}
27
28impl Edge {
29    /// Create a new edge
30    pub fn new(edge_type: EdgeType, target: BlockId) -> Self {
31        Self {
32            edge_type,
33            target,
34            metadata: EdgeMetadata::default(),
35            created_at: Utc::now(),
36        }
37    }
38
39    /// Add metadata to the edge
40    pub fn with_metadata(mut self, metadata: EdgeMetadata) -> Self {
41        self.metadata = metadata;
42        self
43    }
44
45    /// Add confidence score
46    pub fn with_confidence(mut self, confidence: f32) -> Self {
47        self.metadata.confidence = Some(confidence);
48        self
49    }
50
51    /// Add description
52    pub fn with_description(mut self, description: impl Into<String>) -> Self {
53        self.metadata.description = Some(description.into());
54        self
55    }
56}
57
58/// Types of relationships between blocks
59#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
60#[serde(rename_all = "snake_case")]
61pub enum EdgeType {
62    // Derivation relationships
63    /// This block was created from another
64    DerivedFrom,
65    /// This block replaces another
66    Supersedes,
67    /// This block is a transformation of another
68    TransformedFrom,
69
70    // Reference relationships
71    /// This block references another
72    References,
73    /// Inverse of References (auto-maintained)
74    CitedBy,
75    /// Hyperlink relationship
76    LinksTo,
77
78    // Semantic relationships
79    /// This block provides evidence for another
80    Supports,
81    /// This block contradicts another
82    Contradicts,
83    /// This block elaborates on another
84    Elaborates,
85    /// This block summarizes another
86    Summarizes,
87
88    // Structural relationships (auto-maintained from document structure)
89    /// Structural parent
90    ParentOf,
91    /// Structural child
92    ChildOf,
93    /// Same parent
94    SiblingOf,
95    /// Immediate previous sibling
96    PreviousSibling,
97    /// Immediate next sibling
98    NextSibling,
99
100    // Version relationships
101    /// Different version of same logical content
102    VersionOf,
103    /// Alternative representation
104    AlternativeOf,
105    /// Translation to different language
106    TranslationOf,
107
108    // Custom relationship
109    Custom(String),
110}
111
112impl EdgeType {
113    /// Get the inverse edge type (if applicable)
114    pub fn inverse(&self) -> Option<EdgeType> {
115        match self {
116            EdgeType::References => Some(EdgeType::CitedBy),
117            EdgeType::CitedBy => Some(EdgeType::References),
118            EdgeType::DerivedFrom => None, // No automatic inverse
119            EdgeType::Supersedes => None,
120            EdgeType::ParentOf => Some(EdgeType::ChildOf),
121            EdgeType::ChildOf => Some(EdgeType::ParentOf),
122            EdgeType::PreviousSibling => Some(EdgeType::NextSibling),
123            EdgeType::NextSibling => Some(EdgeType::PreviousSibling),
124            EdgeType::Supports => None,
125            EdgeType::Contradicts => Some(EdgeType::Contradicts), // Symmetric
126            EdgeType::SiblingOf => Some(EdgeType::SiblingOf),     // Symmetric
127            _ => None,
128        }
129    }
130
131    /// Check if this edge type is symmetric
132    pub fn is_symmetric(&self) -> bool {
133        matches!(self, EdgeType::Contradicts | EdgeType::SiblingOf)
134    }
135
136    /// Check if this is a structural edge (auto-maintained)
137    pub fn is_structural(&self) -> bool {
138        matches!(
139            self,
140            EdgeType::ParentOf
141                | EdgeType::ChildOf
142                | EdgeType::SiblingOf
143                | EdgeType::PreviousSibling
144                | EdgeType::NextSibling
145        )
146    }
147}
148
149#[derive(Debug, Clone, PartialEq, Eq)]
150pub struct EdgeTypeParseError(pub String);
151
152impl fmt::Display for EdgeTypeParseError {
153    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
154        write!(f, "unknown edge type '{}'", self.0)
155    }
156}
157
158impl StdError for EdgeTypeParseError {}
159
160impl FromStr for EdgeType {
161    type Err = EdgeTypeParseError;
162
163    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
164        match s.to_lowercase().as_str() {
165            "derived_from" => Ok(EdgeType::DerivedFrom),
166            "supersedes" => Ok(EdgeType::Supersedes),
167            "transformed_from" => Ok(EdgeType::TransformedFrom),
168            "references" => Ok(EdgeType::References),
169            "cited_by" => Ok(EdgeType::CitedBy),
170            "links_to" => Ok(EdgeType::LinksTo),
171            "supports" => Ok(EdgeType::Supports),
172            "contradicts" => Ok(EdgeType::Contradicts),
173            "elaborates" => Ok(EdgeType::Elaborates),
174            "summarizes" => Ok(EdgeType::Summarizes),
175            "parent_of" => Ok(EdgeType::ParentOf),
176            "child_of" => Ok(EdgeType::ChildOf),
177            "sibling_of" => Ok(EdgeType::SiblingOf),
178            "previous_sibling" => Ok(EdgeType::PreviousSibling),
179            "next_sibling" => Ok(EdgeType::NextSibling),
180            "version_of" => Ok(EdgeType::VersionOf),
181            "alternative_of" => Ok(EdgeType::AlternativeOf),
182            "translation_of" => Ok(EdgeType::TranslationOf),
183            s if s.starts_with("custom:") => Ok(EdgeType::Custom(
184                s.strip_prefix("custom:").unwrap().to_string(),
185            )),
186            _ => Err(EdgeTypeParseError(s.to_string())),
187        }
188    }
189}
190
191impl EdgeType {
192    /// Convert to string
193    pub fn as_str(&self) -> String {
194        match self {
195            EdgeType::DerivedFrom => "derived_from".to_string(),
196            EdgeType::Supersedes => "supersedes".to_string(),
197            EdgeType::TransformedFrom => "transformed_from".to_string(),
198            EdgeType::References => "references".to_string(),
199            EdgeType::CitedBy => "cited_by".to_string(),
200            EdgeType::LinksTo => "links_to".to_string(),
201            EdgeType::Supports => "supports".to_string(),
202            EdgeType::Contradicts => "contradicts".to_string(),
203            EdgeType::Elaborates => "elaborates".to_string(),
204            EdgeType::Summarizes => "summarizes".to_string(),
205            EdgeType::ParentOf => "parent_of".to_string(),
206            EdgeType::ChildOf => "child_of".to_string(),
207            EdgeType::SiblingOf => "sibling_of".to_string(),
208            EdgeType::PreviousSibling => "previous_sibling".to_string(),
209            EdgeType::NextSibling => "next_sibling".to_string(),
210            EdgeType::VersionOf => "version_of".to_string(),
211            EdgeType::AlternativeOf => "alternative_of".to_string(),
212            EdgeType::TranslationOf => "translation_of".to_string(),
213            EdgeType::Custom(name) => format!("custom:{}", name),
214        }
215    }
216}
217
218/// Edge metadata
219#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
220pub struct EdgeMetadata {
221    /// Confidence score (0.0 - 1.0) for inferred relationships
222    #[serde(skip_serializing_if = "Option::is_none")]
223    pub confidence: Option<f32>,
224    /// Human-readable description
225    #[serde(skip_serializing_if = "Option::is_none")]
226    pub description: Option<String>,
227    /// Custom key-value pairs
228    #[serde(default, skip_serializing_if = "HashMap::is_empty")]
229    pub custom: HashMap<String, serde_json::Value>,
230}
231
232impl EdgeMetadata {
233    pub fn new() -> Self {
234        Self::default()
235    }
236
237    pub fn is_empty(&self) -> bool {
238        self.confidence.is_none() && self.description.is_none() && self.custom.is_empty()
239    }
240
241    pub fn with_confidence(mut self, confidence: f32) -> Self {
242        self.confidence = Some(confidence.clamp(0.0, 1.0));
243        self
244    }
245
246    pub fn with_description(mut self, description: impl Into<String>) -> Self {
247        self.description = Some(description.into());
248        self
249    }
250
251    pub fn with_custom(mut self, key: impl Into<String>, value: serde_json::Value) -> Self {
252        self.custom.insert(key.into(), value);
253        self
254    }
255}
256
257/// Bidirectional edge index for efficient traversal
258#[derive(Debug, Clone, Default)]
259pub struct EdgeIndex {
260    /// Outgoing edges: source -> [(type, target)]
261    outgoing: HashMap<BlockId, Vec<(EdgeType, BlockId)>>,
262    /// Incoming edges: target -> [(type, source)]
263    incoming: HashMap<BlockId, Vec<(EdgeType, BlockId)>>,
264}
265
266impl EdgeIndex {
267    pub fn new() -> Self {
268        Self::default()
269    }
270
271    /// Add an edge to the index
272    pub fn add_edge(&mut self, source: &BlockId, edge: &Edge) {
273        // Add to outgoing
274        self.outgoing
275            .entry(*source)
276            .or_default()
277            .push((edge.edge_type.clone(), edge.target));
278
279        // Auto-maintain inverse edge in incoming index
280        if let Some(inv) = edge.edge_type.inverse() {
281            self.incoming
282                .entry(edge.target)
283                .or_default()
284                .push((inv, *source));
285        } else {
286            // Even without inverse, track in incoming for traversal
287            self.incoming
288                .entry(edge.target)
289                .or_default()
290                .push((edge.edge_type.clone(), *source));
291        }
292    }
293
294    /// Remove an edge from the index
295    pub fn remove_edge(&mut self, source: &BlockId, target: &BlockId, edge_type: &EdgeType) {
296        if let Some(edges) = self.outgoing.get_mut(source) {
297            edges.retain(|(t, tgt)| !(t == edge_type && tgt == target));
298            if edges.is_empty() {
299                self.outgoing.remove(source);
300            }
301        }
302
303        let incoming_type = edge_type.inverse().unwrap_or_else(|| edge_type.clone());
304        if let Some(edges) = self.incoming.get_mut(target) {
305            edges.retain(|(t, src)| !(t == &incoming_type && src == source));
306            if edges.is_empty() {
307                self.incoming.remove(target);
308            }
309        }
310    }
311
312    /// Remove all edges involving a block
313    pub fn remove_block(&mut self, block_id: &BlockId) {
314        // Remove outgoing edges
315        if let Some(edges) = self.outgoing.remove(block_id) {
316            for (edge_type, target) in edges {
317                let _incoming_type = edge_type.inverse().unwrap_or(edge_type);
318                if let Some(incoming) = self.incoming.get_mut(&target) {
319                    incoming.retain(|(_, src)| src != block_id);
320                }
321            }
322        }
323
324        // Remove incoming edges
325        if let Some(edges) = self.incoming.remove(block_id) {
326            for (_, source) in edges {
327                if let Some(outgoing) = self.outgoing.get_mut(&source) {
328                    outgoing.retain(|(_, tgt)| tgt != block_id);
329                }
330            }
331        }
332    }
333
334    /// Get all outgoing edges from a block
335    pub fn outgoing_from(&self, source: &BlockId) -> &[(EdgeType, BlockId)] {
336        self.outgoing
337            .get(source)
338            .map(|v| v.as_slice())
339            .unwrap_or(&[])
340    }
341
342    /// Get all incoming edges to a block
343    pub fn incoming_to(&self, target: &BlockId) -> &[(EdgeType, BlockId)] {
344        self.incoming
345            .get(target)
346            .map(|v| v.as_slice())
347            .unwrap_or(&[])
348    }
349
350    /// Get all edges of a specific type from a source
351    pub fn outgoing_of_type(&self, source: &BlockId, edge_type: &EdgeType) -> Vec<BlockId> {
352        self.outgoing
353            .get(source)
354            .map(|edges| {
355                edges
356                    .iter()
357                    .filter(|(t, _)| t == edge_type)
358                    .map(|(_, tgt)| *tgt)
359                    .collect()
360            })
361            .unwrap_or_default()
362    }
363
364    /// Get all edges of a specific type to a target
365    pub fn incoming_of_type(&self, target: &BlockId, edge_type: &EdgeType) -> Vec<BlockId> {
366        self.incoming
367            .get(target)
368            .map(|edges| {
369                edges
370                    .iter()
371                    .filter(|(t, _)| t == edge_type)
372                    .map(|(_, src)| *src)
373                    .collect()
374            })
375            .unwrap_or_default()
376    }
377
378    /// Check if an edge exists
379    pub fn has_edge(&self, source: &BlockId, target: &BlockId, edge_type: &EdgeType) -> bool {
380        self.outgoing
381            .get(source)
382            .map(|edges| edges.iter().any(|(t, tgt)| t == edge_type && tgt == target))
383            .unwrap_or(false)
384    }
385
386    /// Get total edge count
387    pub fn edge_count(&self) -> usize {
388        self.outgoing.values().map(|v| v.len()).sum()
389    }
390
391    /// Clear all edges
392    pub fn clear(&mut self) {
393        self.outgoing.clear();
394        self.incoming.clear();
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401
402    fn make_id(n: u8) -> BlockId {
403        BlockId::from_bytes([n; 12])
404    }
405
406    #[test]
407    fn test_edge_creation() {
408        let edge = Edge::new(EdgeType::References, make_id(2))
409            .with_confidence(0.95)
410            .with_description("Important reference");
411
412        assert_eq!(edge.edge_type, EdgeType::References);
413        assert_eq!(edge.metadata.confidence, Some(0.95));
414    }
415
416    #[test]
417    fn test_edge_type_inverse() {
418        assert_eq!(EdgeType::References.inverse(), Some(EdgeType::CitedBy));
419        assert_eq!(EdgeType::ParentOf.inverse(), Some(EdgeType::ChildOf));
420        assert_eq!(EdgeType::DerivedFrom.inverse(), None);
421    }
422
423    #[test]
424    fn test_edge_type_parse() {
425        assert_eq!(
426            EdgeType::from_str("references").unwrap(),
427            EdgeType::References
428        );
429        assert_eq!(
430            EdgeType::from_str("custom:my_type").unwrap(),
431            EdgeType::Custom("my_type".to_string())
432        );
433    }
434
435    #[test]
436    fn test_edge_index_add_remove() {
437        let mut index = EdgeIndex::new();
438        let source = make_id(1);
439        let target = make_id(2);
440        let edge = Edge::new(EdgeType::References, target);
441
442        index.add_edge(&source, &edge);
443        assert!(index.has_edge(&source, &target, &EdgeType::References));
444        assert_eq!(index.edge_count(), 1);
445
446        index.remove_edge(&source, &target, &EdgeType::References);
447        assert!(!index.has_edge(&source, &target, &EdgeType::References));
448    }
449
450    #[test]
451    fn test_edge_index_traversal() {
452        let mut index = EdgeIndex::new();
453        let a = make_id(1);
454        let b = make_id(2);
455        let c = make_id(3);
456
457        index.add_edge(&a, &Edge::new(EdgeType::References, b));
458        index.add_edge(&a, &Edge::new(EdgeType::References, c));
459        index.add_edge(&b, &Edge::new(EdgeType::Supports, c));
460
461        let refs = index.outgoing_of_type(&a, &EdgeType::References);
462        assert_eq!(refs.len(), 2);
463
464        let incoming = index.incoming_to(&c);
465        assert_eq!(incoming.len(), 2);
466    }
467
468    #[test]
469    fn test_edge_index_remove_block() {
470        let mut index = EdgeIndex::new();
471        let a = make_id(1);
472        let b = make_id(2);
473        let c = make_id(3);
474
475        index.add_edge(&a, &Edge::new(EdgeType::References, b));
476        index.add_edge(&b, &Edge::new(EdgeType::References, c));
477
478        index.remove_block(&b);
479
480        assert!(!index.has_edge(&a, &b, &EdgeType::References));
481        assert!(!index.has_edge(&b, &c, &EdgeType::References));
482    }
483}
ucm_core/edge.rs

ucm_core/
edge.rs
