helix_graph_algorithms/
model.rs

1use std::cmp::Ordering;
2use std::collections::{BTreeMap, BTreeSet};
3use std::fmt;
4use std::ops::Deref;
5use std::slice;
6use std::sync::Arc;
7
8use serde::{Deserialize, Serialize};
9use serde_json::Value;
10use thiserror::Error;
11
12use crate::ExternalId;
13
14/// Opaque external node identifier returned to SDK callers.
15pub type NodeId = ExternalId;
16/// Selected immutable properties attached to a node, edge, or graph.
17pub type Attributes = BTreeMap<String, Value>;
18
19/// Collision-free identity for a stored edge or a synthesized reversal.
20///
21/// Generation zero is the original Helix edge. Positive generations identify
22/// synthesized reversals without modifying or reserving user-controlled IDs.
23#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
24pub struct EdgeId {
25    stored_id: String,
26    reverse_generation: u64,
27}
28
29impl EdgeId {
30    /// Construct an original stored-edge identity.
31    pub fn original(id: impl Into<String>) -> Self {
32        Self {
33            stored_id: id.into(),
34            reverse_generation: 0,
35        }
36    }
37
38    /// Construct a synthesized-reverse identity at a non-zero generation.
39    pub fn synthesized_reverse(id: impl Into<String>, generation: u64) -> Option<Self> {
40        (generation > 0).then(|| Self {
41            stored_id: id.into(),
42            reverse_generation: generation,
43        })
44    }
45
46    /// Derive the next structural reversal when its generation is representable.
47    pub fn reversed(&self) -> Option<Self> {
48        self.reverse_generation
49            .checked_add(1)
50            .and_then(|generation| Self::synthesized_reverse(self.stored_id.clone(), generation))
51    }
52
53    /// Return the underlying stored Helix edge identity.
54    pub fn stored_id(&self) -> &str {
55        &self.stored_id
56    }
57
58    /// Zero for stored edges; positive for synthesized reversals.
59    pub const fn reverse_generation(&self) -> u64 {
60        self.reverse_generation
61    }
62
63    fn is_valid(&self) -> bool {
64        !self.stored_id.is_empty()
65    }
66}
67
68impl From<String> for EdgeId {
69    fn from(id: String) -> Self {
70        Self::original(id)
71    }
72}
73
74impl From<&str> for EdgeId {
75    fn from(id: &str) -> Self {
76        Self::original(id)
77    }
78}
79
80impl fmt::Display for EdgeId {
81    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
82        if self.reverse_generation == 0 {
83            formatter.write_str(&self.stored_id)
84        } else {
85            write!(
86                formatter,
87                "reverse#{}({})",
88                self.reverse_generation, self.stored_id
89            )
90        }
91    }
92}
93
94/// Finite floating-point value strictly greater than zero.
95#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Serialize, Deserialize)]
96#[serde(try_from = "f64", into = "f64")]
97pub struct PositiveFiniteF64(f64);
98
99impl PositiveFiniteF64 {
100    /// Validate a positive finite value.
101    pub fn new(value: f64) -> Result<Self, GraphError> {
102        if value.is_finite() && value > 0.0 {
103            Ok(Self(value))
104        } else {
105            Err(GraphError::InvalidOption(
106                "value must be finite and positive".to_string(),
107            ))
108        }
109    }
110
111    /// Return the validated primitive value.
112    pub const fn get(self) -> f64 {
113        self.0
114    }
115}
116
117impl TryFrom<f64> for PositiveFiniteF64 {
118    type Error = GraphError;
119
120    fn try_from(value: f64) -> Result<Self, Self::Error> {
121        Self::new(value)
122    }
123}
124
125impl From<PositiveFiniteF64> for f64 {
126    fn from(value: PositiveFiniteF64) -> Self {
127        value.get()
128    }
129}
130
131/// Finite floating-point value greater than or equal to zero.
132#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Serialize, Deserialize)]
133#[serde(try_from = "f64", into = "f64")]
134pub struct NonNegativeFiniteF64(f64);
135
136impl NonNegativeFiniteF64 {
137    /// Validate a non-negative finite value.
138    pub fn new(value: f64) -> Result<Self, GraphError> {
139        if value.is_finite() && value >= 0.0 {
140            Ok(Self(value))
141        } else {
142            Err(GraphError::InvalidOption(
143                "value must be finite and non-negative".to_string(),
144            ))
145        }
146    }
147
148    /// Return the validated primitive value.
149    pub const fn get(self) -> f64 {
150        self.0
151    }
152}
153
154impl TryFrom<f64> for NonNegativeFiniteF64 {
155    type Error = GraphError;
156
157    fn try_from(value: f64) -> Result<Self, Self::Error> {
158        Self::new(value)
159    }
160}
161
162impl From<NonNegativeFiniteF64> for f64 {
163    fn from(value: NonNegativeFiniteF64) -> Self {
164        value.get()
165    }
166}
167
168/// Declared graph topology contract.
169#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
170#[serde(rename_all = "snake_case")]
171pub enum GraphKind {
172    /// Undirected simple graph.
173    Graph,
174    /// Directed simple graph.
175    DiGraph,
176    /// Undirected graph permitting parallel endpoint pairs.
177    MultiGraph,
178    /// Directed graph permitting parallel endpoint pairs.
179    MultiDiGraph,
180}
181
182impl GraphKind {
183    /// Whether algorithms observe stored edge direction.
184    pub const fn is_directed(self) -> bool {
185        matches!(self, Self::DiGraph | Self::MultiDiGraph)
186    }
187
188    /// Whether parallel endpoint pairs are permitted.
189    pub const fn is_multigraph(self) -> bool {
190        matches!(self, Self::MultiGraph | Self::MultiDiGraph)
191    }
192}
193
194/// Immutable node input and public node record.
195#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
196pub struct Node {
197    /// Opaque external identity.
198    pub id: NodeId,
199    /// Optional Helix node label.
200    pub label: Option<String>,
201    /// Selected immutable properties.
202    pub attributes: Attributes,
203}
204
205impl Node {
206    /// Construct a node with no label or selected properties.
207    pub fn new(id: impl Into<NodeId>) -> Self {
208        Self {
209            id: id.into(),
210            label: None,
211            attributes: Attributes::new(),
212        }
213    }
214
215    /// Attach a label.
216    pub fn with_label(mut self, label: impl Into<String>) -> Self {
217        self.label = Some(label.into());
218        self
219    }
220
221    /// Attach selected properties.
222    pub fn with_attributes(mut self, attributes: Attributes) -> Self {
223        self.attributes = attributes;
224        self
225    }
226}
227
228/// Immutable edge input and public edge record.
229#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
230pub struct Edge {
231    /// Stable unique edge identity.
232    pub id: EdgeId,
233    /// Optional Graphify multigraph key.
234    pub graphify_key: Option<ExternalId>,
235    /// Stored source node external ID.
236    pub source: NodeId,
237    /// Stored target node external ID.
238    pub target: NodeId,
239    /// Optional Helix edge label.
240    pub label: Option<String>,
241    /// Optional validated non-negative finite weight.
242    pub weight: Option<f64>,
243    /// Selected immutable properties.
244    pub attributes: Attributes,
245}
246
247impl Edge {
248    /// Construct an unweighted edge without a label or selected properties.
249    pub fn new(
250        id: impl Into<EdgeId>,
251        source: impl Into<NodeId>,
252        target: impl Into<NodeId>,
253    ) -> Self {
254        Self {
255            id: id.into(),
256            graphify_key: None,
257            source: source.into(),
258            target: target.into(),
259            label: None,
260            weight: None,
261            attributes: Attributes::new(),
262        }
263    }
264
265    /// Attach a Graphify multigraph key.
266    pub fn with_graphify_key(mut self, key: impl Into<ExternalId>) -> Self {
267        self.graphify_key = Some(key.into());
268        self
269    }
270
271    /// Attach a label.
272    pub fn with_label(mut self, label: impl Into<String>) -> Self {
273        self.label = Some(label.into());
274        self
275    }
276
277    /// Attach an algorithm weight.
278    pub fn with_weight(mut self, weight: f64) -> Self {
279        self.weight = Some(weight);
280        self
281    }
282
283    /// Attach selected properties.
284    pub fn with_attributes(mut self, attributes: Attributes) -> Self {
285        self.attributes = attributes;
286        self
287    }
288}
289
290/// Graph construction or lookup failure.
291#[derive(Debug, Clone, PartialEq, Error)]
292pub enum GraphError {
293    /// An edge identifier is empty.
294    #[error("edge ID must not be empty")]
295    EmptyEdgeId,
296    /// The input contains the same node identity more than once.
297    #[error("duplicate node ID: {0}")]
298    DuplicateNode(NodeId),
299    /// The input contains the same edge identity more than once.
300    #[error("duplicate edge ID: {0}")]
301    DuplicateEdge(EdgeId),
302    /// An edge endpoint is absent from the selected node set.
303    #[error("edge {edge_id} references missing {endpoint} node {node_id}")]
304    MissingEndpoint {
305        /// Edge containing the invalid endpoint.
306        edge_id: EdgeId,
307        /// `source` or `target`.
308        endpoint: &'static str,
309        /// Missing node identity.
310        node_id: NodeId,
311    },
312    /// The graph contains an invalid weight.
313    #[error("edge {edge_id} weight must be finite and non-negative, got {weight}")]
314    InvalidWeight {
315        /// Edge containing the invalid weight.
316        edge_id: EdgeId,
317        /// Rejected weight.
318        weight: f64,
319    },
320    /// An external identity is malformed or exceeds its resource bounds.
321    #[error("invalid external identity: {0}")]
322    InvalidExternalId(String),
323    /// A requested node does not exist.
324    #[error("unknown node ID: {0}")]
325    UnknownNode(NodeId),
326    /// A requested edge does not exist.
327    #[error("unknown edge ID: {0}")]
328    UnknownEdge(EdgeId),
329    /// A relabel operation would merge distinct nodes.
330    #[error("relabel target {target} is produced by both {first} and {second}")]
331    RelabelCollision {
332        /// Colliding output identity.
333        target: NodeId,
334        /// First source identity.
335        first: NodeId,
336        /// Second source identity.
337        second: NodeId,
338    },
339    /// A simple graph contains parallel endpoint pairs.
340    #[error("{kind:?} does not permit parallel edges between {pair_source} and {pair_target}")]
341    ParallelEdge {
342        /// Declared simple graph kind.
343        kind: GraphKind,
344        /// Canonical pair source.
345        pair_source: NodeId,
346        /// Canonical pair target.
347        pair_target: NodeId,
348    },
349    /// Compose requires exactly equal graph kinds.
350    #[error("cannot compose graphs with different kinds")]
351    KindMismatch,
352    /// Two graphs disagree about one stable edge identity.
353    #[error("edge {edge_id} has conflicting endpoints across composed graphs")]
354    ConflictingEdge {
355        /// Conflicting stable edge identity.
356        edge_id: EdgeId,
357    },
358    /// No further structural reverse generation can be represented.
359    #[error("edge {stored_id} exhausted synthesized reverse generations")]
360    EdgeIdentityExhausted {
361        /// Underlying stored Helix edge identity.
362        stored_id: String,
363    },
364    /// An algorithm option violates its typed runtime contract.
365    #[error("invalid algorithm option: {0}")]
366    InvalidOption(String),
367}
368
369#[derive(Debug, Clone, Copy, PartialEq, Eq)]
370pub(crate) struct ArcRef {
371    pub(crate) neighbor: usize,
372    pub(crate) edge: usize,
373}
374
375#[derive(Debug, Clone, PartialEq)]
376struct Csr {
377    offsets: Vec<usize>,
378    arcs: Vec<ArcRef>,
379}
380
381impl Csr {
382    fn from_rows(rows: Vec<Vec<ArcRef>>) -> Self {
383        let mut offsets = Vec::with_capacity(rows.len() + 1);
384        let mut arcs = Vec::with_capacity(rows.iter().map(Vec::len).sum());
385        offsets.push(0);
386        for row in rows {
387            arcs.extend(row);
388            offsets.push(arcs.len());
389        }
390        Self { offsets, arcs }
391    }
392
393    fn row(&self, node: usize) -> &[ArcRef] {
394        &self.arcs[self.offsets[node]..self.offsets[node + 1]]
395    }
396}
397
398/// Validated immutable graph used by every native algorithm.
399#[derive(Debug, Clone, PartialEq)]
400pub struct Graph {
401    inner: Arc<GraphInner>,
402}
403
404/// Shared graph allocation. Its fields remain private; this type is public
405/// only so [`Graph`]'s read-only dereference implementation can share storage.
406#[doc(hidden)]
407#[derive(Debug, PartialEq)]
408pub struct GraphInner {
409    kind: GraphKind,
410    graph_attributes: Attributes,
411    nodes: Vec<Node>,
412    edges: Vec<Edge>,
413    node_indexes: BTreeMap<NodeId, usize>,
414    edge_indexes: BTreeMap<EdgeId, usize>,
415    outgoing: Csr,
416    incoming: Csr,
417}
418
419impl Deref for Graph {
420    type Target = GraphInner;
421
422    fn deref(&self) -> &Self::Target {
423        &self.inner
424    }
425}
426
427impl Graph {
428    /// Validate and construct a graph.
429    pub fn new(
430        kind: GraphKind,
431        nodes: impl IntoIterator<Item = Node>,
432        edges: impl IntoIterator<Item = Edge>,
433    ) -> Result<Self, GraphError> {
434        Self::with_attributes(kind, Attributes::new(), nodes, edges)
435    }
436
437    /// Validate and construct a graph with graph-level metadata.
438    pub fn with_attributes(
439        kind: GraphKind,
440        graph_attributes: Attributes,
441        nodes: impl IntoIterator<Item = Node>,
442        edges: impl IntoIterator<Item = Edge>,
443    ) -> Result<Self, GraphError> {
444        let mut node_map = BTreeMap::new();
445        for node in nodes {
446            node.id.validate()?;
447            let node_id = node.id.clone();
448            if node_map.insert(node_id.clone(), node).is_some() {
449                return Err(GraphError::DuplicateNode(node_id));
450            }
451        }
452        let nodes = node_map.into_values().collect::<Vec<_>>();
453        let node_indexes = nodes
454            .iter()
455            .enumerate()
456            .map(|(index, node)| (node.id.clone(), index))
457            .collect::<BTreeMap<_, _>>();
458
459        let mut edge_map = BTreeMap::new();
460        for edge in edges {
461            if !edge.id.is_valid() {
462                return Err(GraphError::EmptyEdgeId);
463            }
464            if !node_indexes.contains_key(&edge.source) {
465                return Err(GraphError::MissingEndpoint {
466                    edge_id: edge.id,
467                    endpoint: "source",
468                    node_id: edge.source,
469                });
470            }
471            if !node_indexes.contains_key(&edge.target) {
472                return Err(GraphError::MissingEndpoint {
473                    edge_id: edge.id,
474                    endpoint: "target",
475                    node_id: edge.target,
476                });
477            }
478            if let Some(weight) = edge.weight
479                && (!weight.is_finite() || weight < 0.0)
480            {
481                return Err(GraphError::InvalidWeight {
482                    edge_id: edge.id,
483                    weight,
484                });
485            }
486            let edge_id = edge.id.clone();
487            if edge_map.insert(edge_id.clone(), edge).is_some() {
488                return Err(GraphError::DuplicateEdge(edge_id));
489            }
490        }
491        let edges = edge_map.into_values().collect::<Vec<_>>();
492        if !kind.is_multigraph() {
493            let mut endpoint_pairs = BTreeSet::new();
494            for edge in &edges {
495                let pair = if kind.is_directed() || edge.source <= edge.target {
496                    (edge.source.clone(), edge.target.clone())
497                } else {
498                    (edge.target.clone(), edge.source.clone())
499                };
500                if !endpoint_pairs.insert(pair.clone()) {
501                    return Err(GraphError::ParallelEdge {
502                        kind,
503                        pair_source: pair.0,
504                        pair_target: pair.1,
505                    });
506                }
507            }
508        }
509        let edge_indexes = edges
510            .iter()
511            .enumerate()
512            .map(|(index, edge)| (edge.id.clone(), index))
513            .collect::<BTreeMap<_, _>>();
514
515        let mut outgoing_rows = vec![Vec::new(); nodes.len()];
516        let mut incoming_rows = vec![Vec::new(); nodes.len()];
517        for (edge_index, edge) in edges.iter().enumerate() {
518            let source = node_indexes[&edge.source];
519            let target = node_indexes[&edge.target];
520            outgoing_rows[source].push(ArcRef {
521                neighbor: target,
522                edge: edge_index,
523            });
524            incoming_rows[target].push(ArcRef {
525                neighbor: source,
526                edge: edge_index,
527            });
528        }
529        for row in outgoing_rows.iter_mut().chain(incoming_rows.iter_mut()) {
530            row.sort_by(|left, right| compare_arcs(&nodes, &edges, left, right));
531        }
532
533        Ok(Self {
534            inner: Arc::new(GraphInner {
535                kind,
536                graph_attributes,
537                nodes,
538                edges,
539                node_indexes,
540                edge_indexes,
541                outgoing: Csr::from_rows(outgoing_rows),
542                incoming: Csr::from_rows(incoming_rows),
543            }),
544        })
545    }
546
547    /// Declared graph topology contract.
548    pub fn kind(&self) -> GraphKind {
549        self.kind
550    }
551
552    /// Whether the graph is directed.
553    pub fn is_directed(&self) -> bool {
554        self.kind.is_directed()
555    }
556
557    /// Whether the graph declares support for parallel endpoint-pair edges.
558    pub fn is_multigraph(&self) -> bool {
559        self.kind.is_multigraph()
560    }
561
562    /// Graph-level immutable attributes.
563    pub fn attributes(&self) -> &Attributes {
564        &self.graph_attributes
565    }
566
567    /// Number of nodes.
568    pub fn node_count(&self) -> usize {
569        self.nodes.len()
570    }
571
572    /// Number of stored edges. Undirected adjacency does not duplicate this
573    /// public edge count.
574    pub fn edge_count(&self) -> usize {
575        self.edges.len()
576    }
577
578    /// Nodes in deterministic external-ID order.
579    pub fn nodes(&self) -> &[Node] {
580        &self.nodes
581    }
582
583    /// Edges in deterministic stable-ID order.
584    pub fn edges(&self) -> &[Edge] {
585        &self.edges
586    }
587
588    /// Look up a node.
589    pub fn node(&self, id: impl Into<NodeId>) -> Option<&Node> {
590        let id = id.into();
591        self.node_indexes.get(&id).map(|index| &self.nodes[*index])
592    }
593
594    /// Look up an edge.
595    pub fn edge(&self, id: impl Into<EdgeId>) -> Option<&Edge> {
596        self.edge_indexes
597            .get(&id.into())
598            .map(|index| &self.edges[*index])
599    }
600
601    /// Whether the graph contains a node.
602    pub fn contains_node(&self, id: impl Into<NodeId>) -> bool {
603        self.node_indexes.contains_key(&id.into())
604    }
605
606    /// Whether the graph contains an edge.
607    pub fn contains_edge(&self, id: impl Into<EdgeId>) -> bool {
608        self.edge_indexes.contains_key(&id.into())
609    }
610
611    pub(crate) fn node_index(&self, id: impl Into<NodeId>) -> Result<usize, GraphError> {
612        let id = id.into();
613        self.node_indexes
614            .get(&id)
615            .copied()
616            .ok_or(GraphError::UnknownNode(id))
617    }
618
619    pub(crate) fn node_id(&self, index: usize) -> &NodeId {
620        &self.nodes[index].id
621    }
622
623    pub(crate) fn edge_at(&self, index: usize) -> &Edge {
624        &self.edges[index]
625    }
626
627    pub(crate) fn outgoing(&self, node: usize) -> &[ArcRef] {
628        self.outgoing.row(node)
629    }
630
631    pub(crate) fn incoming(&self, node: usize) -> &[ArcRef] {
632        self.incoming.row(node)
633    }
634
635    pub(crate) fn arcs(&self, node: usize, direction: super::TraversalDirection) -> ArcIter<'_> {
636        let direction = if self.kind.is_directed() {
637            direction
638        } else {
639            super::TraversalDirection::Both
640        };
641        match direction {
642            super::TraversalDirection::Out => ArcIter::One(self.outgoing(node).iter()),
643            super::TraversalDirection::In => ArcIter::One(self.incoming(node).iter()),
644            super::TraversalDirection::Both => ArcIter::Both {
645                graph: self,
646                node,
647                outgoing: self.outgoing(node),
648                incoming: self.incoming(node),
649                outgoing_index: 0,
650                incoming_index: 0,
651            },
652        }
653    }
654}
655
656fn compare_arcs(nodes: &[Node], edges: &[Edge], left: &ArcRef, right: &ArcRef) -> Ordering {
657    nodes[left.neighbor]
658        .id
659        .cmp(&nodes[right.neighbor].id)
660        .then_with(|| {
661            edges[left.edge]
662                .graphify_key
663                .cmp(&edges[right.edge].graphify_key)
664        })
665        .then_with(|| edges[left.edge].id.cmp(&edges[right.edge].id))
666}
667
668pub(crate) enum ArcIter<'a> {
669    One(slice::Iter<'a, ArcRef>),
670    Both {
671        graph: &'a Graph,
672        node: usize,
673        outgoing: &'a [ArcRef],
674        incoming: &'a [ArcRef],
675        outgoing_index: usize,
676        incoming_index: usize,
677    },
678}
679
680impl Iterator for ArcIter<'_> {
681    type Item = ArcRef;
682
683    fn next(&mut self) -> Option<Self::Item> {
684        match self {
685            Self::One(arcs) => arcs.next().copied(),
686            Self::Both {
687                graph,
688                node,
689                outgoing,
690                incoming,
691                outgoing_index,
692                incoming_index,
693            } => {
694                while incoming
695                    .get(*incoming_index)
696                    .is_some_and(|arc| arc.neighbor == *node)
697                {
698                    *incoming_index += 1;
699                }
700                match (outgoing.get(*outgoing_index), incoming.get(*incoming_index)) {
701                    (Some(left), Some(right))
702                        if compare_arcs(&graph.nodes, &graph.edges, left, right)
703                            != Ordering::Greater =>
704                    {
705                        *outgoing_index += 1;
706                        Some(*left)
707                    }
708                    (Some(_), Some(right)) => {
709                        *incoming_index += 1;
710                        Some(*right)
711                    }
712                    (Some(left), None) => {
713                        *outgoing_index += 1;
714                        Some(*left)
715                    }
716                    (None, Some(right)) => {
717                        *incoming_index += 1;
718                        Some(*right)
719                    }
720                    (None, None) => None,
721                }
722            }
723        }
724    }
725}
726
727#[cfg(test)]
728mod tests {
729    use super::*;
730    use crate::TraversalDirection;
731
732    #[test]
733    fn construction_sorts_records_and_builds_directional_adjacency() {
734        let graph = Graph::new(
735            GraphKind::DiGraph,
736            [Node::new("b"), Node::new("a")],
737            [Edge::new("edge", "a", "b")],
738        )
739        .unwrap();
740
741        assert_eq!(
742            graph
743                .nodes()
744                .iter()
745                .map(|node| node.id.clone())
746                .collect::<Vec<_>>(),
747            ["a", "b"]
748        );
749        assert_eq!(graph.outgoing(graph.node_index("a").unwrap()).len(), 1);
750        assert_eq!(graph.incoming(graph.node_index("b").unwrap()).len(), 1);
751    }
752
753    #[test]
754    fn construction_rejects_invalid_identity_endpoint_and_weight_states() {
755        assert!(Graph::new(GraphKind::DiGraph, [Node::new("")], []).is_ok());
756        assert!(matches!(
757            Graph::new(
758                GraphKind::DiGraph,
759                [Node::new("a"), Node::new("a")],
760                []
761            ),
762            Err(GraphError::DuplicateNode(id)) if id == "a"
763        ));
764        assert!(matches!(
765            Graph::new(
766                GraphKind::DiGraph,
767                [Node::new("a")],
768                [Edge::new("ab", "a", "b")]
769            ),
770            Err(GraphError::MissingEndpoint { endpoint: "target", node_id, .. }) if node_id == "b"
771        ));
772        assert!(matches!(
773            Graph::new(
774                GraphKind::DiGraph,
775                [Node::new("a")],
776                [Edge::new("aa", "a", "a").with_weight(f64::NAN)]
777            ),
778            Err(GraphError::InvalidWeight { .. })
779        ));
780        assert_eq!(
781            Graph::new(
782                GraphKind::DiGraph,
783                [Node::new("a")],
784                [Edge::new("", "a", "a")]
785            )
786            .unwrap_err(),
787            GraphError::EmptyEdgeId
788        );
789        assert!(matches!(
790            Graph::new(
791                GraphKind::DiGraph,
792                [Node::new("a")],
793                [Edge::new("aa", "missing", "a")]
794            ),
795            Err(GraphError::MissingEndpoint {
796                endpoint: "source",
797                ..
798            })
799        ));
800        assert!(matches!(
801            Graph::new(
802                GraphKind::DiGraph,
803                [Node::new("a")],
804                [Edge::new("aa", "a", "a"), Edge::new("aa", "a", "a")]
805            ),
806            Err(GraphError::DuplicateEdge(id)) if id == EdgeId::from("aa")
807        ));
808    }
809
810    #[test]
811    fn undirected_arc_iteration_does_not_duplicate_self_loops() {
812        let graph = Graph::new(
813            GraphKind::Graph,
814            [Node::new("a"), Node::new("b")],
815            [Edge::new("aa", "a", "a"), Edge::new("ab", "a", "b")],
816        )
817        .unwrap();
818        let a = graph.node_index("a").unwrap();
819        assert_eq!(
820            graph
821                .arcs(a, super::super::TraversalDirection::Both)
822                .count(),
823            2
824        );
825    }
826
827    #[test]
828    fn bidirectional_arc_iteration_merges_incoming_and_outgoing_stably() {
829        let graph = Graph::new(
830            GraphKind::DiGraph,
831            [
832                Node::new("a"),
833                Node::new("b"),
834                Node::new("c"),
835                Node::new("d"),
836            ],
837            [
838                Edge::new("ca", "c", "a"),
839                Edge::new("ab", "a", "b"),
840                Edge::new("da", "d", "a"),
841            ],
842        )
843        .unwrap();
844        let neighbors = graph
845            .arcs(graph.node_index("a").unwrap(), TraversalDirection::Both)
846            .map(|arc| graph.node_id(arc.neighbor).clone())
847            .collect::<Vec<_>>();
848        assert_eq!(neighbors, ["b", "c", "d"]);
849    }
850
851    #[test]
852    fn constrained_float_types_reject_invalid_states_during_decode() {
853        assert!(PositiveFiniteF64::new(1.0).is_ok());
854        assert!(PositiveFiniteF64::new(0.0).is_err());
855        assert!(NonNegativeFiniteF64::new(0.0).is_ok());
856        assert!(NonNegativeFiniteF64::new(-1.0).is_err());
857        assert!(serde_json::from_str::<PositiveFiniteF64>("null").is_err());
858        assert_eq!(f64::from(PositiveFiniteF64::try_from(2.0).unwrap()), 2.0);
859        assert_eq!(f64::from(NonNegativeFiniteF64::try_from(0.5).unwrap()), 0.5);
860    }
861
862    #[test]
863    fn structural_edge_ids_round_trip_and_keep_user_strings_distinct() {
864        let original = EdgeId::original("reverse#1(edge)");
865        let reverse = EdgeId::original("edge").reversed().unwrap();
866        assert_ne!(original, reverse);
867        assert_eq!(reverse.to_string(), "reverse#1(edge)");
868        assert_eq!(
869            EdgeId::synthesized_reverse("edge", u64::MAX)
870                .unwrap()
871                .reversed(),
872            None
873        );
874        assert!(EdgeId::synthesized_reverse("edge", 0).is_none());
875        for edge_id in [
876            original,
877            reverse,
878            EdgeId::synthesized_reverse("edge", 42).unwrap(),
879        ] {
880            let encoded = serde_json::to_vec(&edge_id).unwrap();
881            assert_eq!(serde_json::from_slice::<EdgeId>(&encoded).unwrap(), edge_id);
882        }
883    }
884
885    #[test]
886    fn graph_kind_is_declared_and_simple_kinds_reject_parallel_edges() {
887        for (kind, directed, multigraph) in [
888            (GraphKind::Graph, false, false),
889            (GraphKind::DiGraph, true, false),
890            (GraphKind::MultiGraph, false, true),
891            (GraphKind::MultiDiGraph, true, true),
892        ] {
893            let encoded = serde_json::to_vec(&kind).unwrap();
894            assert_eq!(serde_json::from_slice::<GraphKind>(&encoded).unwrap(), kind);
895            assert_eq!(kind.is_directed(), directed);
896            assert_eq!(kind.is_multigraph(), multigraph);
897        }
898        let directed = Graph::new(
899            GraphKind::DiGraph,
900            [Node::new("a"), Node::new("b")],
901            [Edge::new("ab", "a", "b"), Edge::new("ba", "b", "a")],
902        )
903        .unwrap();
904        assert!(!directed.is_multigraph());
905        assert!(matches!(
906            Graph::new(
907                GraphKind::DiGraph,
908                [Node::new("a"), Node::new("b")],
909                [Edge::new("ab", "a", "b"), Edge::new("ab2", "a", "b")]
910            ),
911            Err(GraphError::ParallelEdge { .. })
912        ));
913        let multigraph = Graph::new(GraphKind::MultiGraph, [Node::new("a")], []).unwrap();
914        assert!(multigraph.is_multigraph());
915        assert!(!multigraph.is_directed());
916    }
917}
helix_graph_algorithms/model.rs

helix_graph_algorithms/
model.rs
