antecedent_graph/
types.rs

1//! Dense ids and edge endpoints.
2//!
3//! [`NodeRef`] lives in `antecedent-core` so sample planning can use it without
4//! depending on this crate.
5//!
6//! SPDX-License-Identifier: MIT OR Apache-2.0
7
8pub use antecedent_core::NodeRef;
9
10use crate::error::GraphError;
11
12/// Compact dense node index used in algorithmic paths.
13#[repr(transparent)]
14#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
15pub struct DenseNodeId(u32);
16
17impl DenseNodeId {
18    /// From raw index.
19    #[must_use]
20    pub const fn from_raw(raw: u32) -> Self {
21        Self(raw)
22    }
23
24    /// Fallible index → dense id.
25    pub fn try_from_usize(i: usize) -> Result<Self, GraphError> {
26        let raw = u32::try_from(i).map_err(|_| GraphError::TooManyNodes)?;
27        Ok(Self::from_raw(raw))
28    }
29
30    /// Raw index.
31    #[must_use]
32    pub const fn raw(self) -> u32 {
33        self.0
34    }
35
36    /// As usize.
37    #[must_use]
38    pub const fn as_usize(self) -> usize {
39        self.0 as usize
40    }
41}
42
43/// Edge endpoint mark.
44#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
45pub enum Endpoint {
46    /// Tail (undirected / directed origin).
47    Tail,
48    /// Arrow head.
49    Arrow,
50    /// Circle (PAG; not used in DAG constructors).
51    Circle,
52    /// Conflict (`x` in pinned baseline). Orientation rules proposed incompatible marks.
53    ///
54    /// CPDAG / PCMCI+ contemporaneous conflicts use Conflict–Conflict (`x-x`).
55    /// PAG / LPCMCI may also use asymmetric forms (`x→`, `←x`).
56    Conflict,
57}
58
59/// LPCMCI middle mark on an edge (Gerhardus & Runge 2020).
60///
61/// Intermediate search state; a converged PAG has only [`MiddleMark::Empty`].
62#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)]
63pub enum MiddleMark {
64    /// Unknown (`?`) — no adjacency claim yet.
65    Unknown,
66    /// Left (`L`) — search among parents of the later/ordered endpoint exhausted.
67    Left,
68    /// Right (`R`) — search among parents of the earlier/ordered endpoint exhausted.
69    Right,
70    /// Both (`!`) — `Left` and `Right` both hold.
71    Both,
72    /// Empty (`-`) — definite adjacency in the MAG / final PAG.
73    #[default]
74    Empty,
75}
76
77impl MiddleMark {
78    /// Whether this is a definite adjacency mark (empty middle).
79    #[must_use]
80    pub const fn is_definite(self) -> bool {
81        matches!(self, Self::Empty)
82    }
83
84    /// Merge an existing middle mark with an update (pinned baseline `_apply_middle_mark`).
85    #[must_use]
86    pub const fn apply(self, update: Self) -> Self {
87        use MiddleMark::{Both, Empty, Left, Right, Unknown};
88        match (self, update) {
89            (Empty, _) | (_, Empty) => Empty,
90            (Both, _) | (_, Both) | (Left, Right) | (Right, Left) => Both,
91            (Unknown, other) | (other, Unknown) => other,
92            (Left, Left) => Left,
93            (Right, Right) => Right,
94        }
95    }
96}
97
98/// Directed marked edge between dense nodes.
99#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
100pub struct MarkedEdge {
101    /// Endpoint A node.
102    pub a: DenseNodeId,
103    /// Endpoint B node.
104    pub b: DenseNodeId,
105    /// Mark at A.
106    pub at_a: Endpoint,
107    /// Mark at B.
108    pub at_b: Endpoint,
109    /// LPCMCI middle mark (default [`MiddleMark::Empty`] outside LPCMCI search).
110    pub middle: MiddleMark,
111}
112
113impl MarkedEdge {
114    /// Directed edge `from -> to` (tail at from, arrow at to).
115    #[must_use]
116    pub const fn directed(from: DenseNodeId, to: DenseNodeId) -> Self {
117        Self {
118            a: from,
119            b: to,
120            at_a: Endpoint::Tail,
121            at_b: Endpoint::Arrow,
122            middle: MiddleMark::Empty,
123        }
124    }
125
126    /// Undirected edge `a — b` (tail–tail). Canonicalizes so `a.raw() <= b.raw()`.
127    #[must_use]
128    pub fn undirected(a: DenseNodeId, b: DenseNodeId) -> Self {
129        if a.raw() <= b.raw() {
130            Self { a, b, at_a: Endpoint::Tail, at_b: Endpoint::Tail, middle: MiddleMark::Empty }
131        } else {
132            Self {
133                a: b,
134                b: a,
135                at_a: Endpoint::Tail,
136                at_b: Endpoint::Tail,
137                middle: MiddleMark::Empty,
138            }
139        }
140    }
141
142    /// Whether this is a DAG-legal directed edge.
143    #[must_use]
144    pub const fn is_dag_directed(self) -> bool {
145        matches!(
146            (self.at_a, self.at_b),
147            (Endpoint::Tail, Endpoint::Arrow) | (Endpoint::Arrow, Endpoint::Tail)
148        )
149    }
150
151    /// Whether this is an undirected CPDAG edge (tail–tail).
152    #[must_use]
153    pub const fn is_undirected(self) -> bool {
154        matches!((self.at_a, self.at_b), (Endpoint::Tail, Endpoint::Tail))
155    }
156
157    /// Whether this is a bidirected ADMG edge (arrow–arrow).
158    #[must_use]
159    pub const fn is_bidirected(self) -> bool {
160        matches!((self.at_a, self.at_b), (Endpoint::Arrow, Endpoint::Arrow))
161    }
162
163    /// Whether this is a conflict edge (`x-x`, both endpoints [`Endpoint::Conflict`]).
164    #[must_use]
165    pub const fn is_conflict(self) -> bool {
166        matches!((self.at_a, self.at_b), (Endpoint::Conflict, Endpoint::Conflict))
167    }
168
169    /// Bidirected edge `a ↔ b`. Canonicalizes so `a.raw() <= b.raw()`.
170    #[must_use]
171    pub fn bidirected(a: DenseNodeId, b: DenseNodeId) -> Self {
172        if a.raw() <= b.raw() {
173            Self { a, b, at_a: Endpoint::Arrow, at_b: Endpoint::Arrow, middle: MiddleMark::Empty }
174        } else {
175            Self {
176                a: b,
177                b: a,
178                at_a: Endpoint::Arrow,
179                at_b: Endpoint::Arrow,
180                middle: MiddleMark::Empty,
181            }
182        }
183    }
184
185    /// Conflict edge `a x-x b` (pinned baseline). Canonicalizes so `a.raw() <= b.raw()`.
186    #[must_use]
187    pub fn conflict(a: DenseNodeId, b: DenseNodeId) -> Self {
188        if a.raw() <= b.raw() {
189            Self {
190                a,
191                b,
192                at_a: Endpoint::Conflict,
193                at_b: Endpoint::Conflict,
194                middle: MiddleMark::Empty,
195            }
196        } else {
197            Self {
198                a: b,
199                b: a,
200                at_a: Endpoint::Conflict,
201                at_b: Endpoint::Conflict,
202                middle: MiddleMark::Empty,
203            }
204        }
205    }
206
207    /// Same endpoints with a different middle mark.
208    #[must_use]
209    pub const fn with_middle(mut self, middle: MiddleMark) -> Self {
210        self.middle = middle;
211        self
212    }
213
214    /// Whether marks are legal for a CPDAG (directed, undirected, or `x-x`; no Circle).
215    #[must_use]
216    pub const fn is_cpdag_legal(self) -> bool {
217        matches!(
218            (self.at_a, self.at_b),
219            (Endpoint::Tail, Endpoint::Arrow | Endpoint::Tail)
220                | (Endpoint::Arrow, Endpoint::Tail)
221                | (Endpoint::Conflict, Endpoint::Conflict)
222        )
223    }
224
225    /// Whether marks are legal for an ADMG (directed or bidirected; no Circle/Conflict).
226    #[must_use]
227    pub const fn is_admg_legal(self) -> bool {
228        matches!(
229            (self.at_a, self.at_b),
230            (Endpoint::Tail | Endpoint::Arrow, Endpoint::Arrow) | (Endpoint::Arrow, Endpoint::Tail)
231        )
232    }
233
234    /// Oriented parent -> child for a DAG directed edge.
235    #[must_use]
236    pub fn parent_child(self) -> Option<(DenseNodeId, DenseNodeId)> {
237        match (self.at_a, self.at_b) {
238            (Endpoint::Tail, Endpoint::Arrow) => Some((self.a, self.b)),
239            (Endpoint::Arrow, Endpoint::Tail) => Some((self.b, self.a)),
240            _ => None,
241        }
242    }
243}
antecedent_graph/types.rs

antecedent_graph/
types.rs
