radiate_gp/collections/graphs/
node.rs

1use crate::node::Node;
2use crate::{Arity, NodeType};
3use radiate_core::{Gene, Valid};
4use radiate_utils::SortedBuffer;
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7use std::fmt::Debug;
8use std::hash::Hash;
9use std::sync::atomic::{AtomicU64, Ordering};
10
11/// A unique identifier for nodes in a graph structure.
12///
13/// `GraphNodeId` is a newtype wrapper around a `u64` that provides a unique identifier
14/// for each node in a graph. The ID is automatically generated using an atomic counter,
15/// ensuring thread-safe unique ID generation across the application.
16///
17/// # Examples
18/// ```
19/// use radiate_gp::collections::GraphNodeId;
20///
21/// let id1 = GraphNodeId::new();
22/// let id2 = GraphNodeId::new();
23/// assert_ne!(id1, id2); // Each ID is unique
24/// ```
25///
26/// # Implementation Details
27/// * Uses an atomic counter (`AtomicU64`) to ensure thread-safe ID generation
28/// * Implements `Debug`, `Clone`, `Copy`, `PartialEq`, `Eq`, `Hash`, `PartialOrd`, and `Ord`
29/// * When the "serde" feature is enabled, implements `Serialize` and `Deserialize`
30/// * Uses `#[repr(transparent)]` to ensure the same memory layout as `u64`
31#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
32#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
33#[repr(transparent)]
34pub struct GraphNodeId(u64);
35
36impl GraphNodeId {
37    pub fn new() -> Self {
38        static GRAPH_NODE_ID: AtomicU64 = AtomicU64::new(0);
39        GraphNodeId(GRAPH_NODE_ID.fetch_add(1, Ordering::Relaxed))
40    }
41}
42
43/// Represents the direction of connections in a graph node.
44///
45/// The [Direction] enum is used to specify whether a node's connections follow the
46/// normal forward direction or create a backward (recurrent) connection. This is
47/// particularly important for creating cyclic graphs and recurrent neural networks.
48///
49/// # Variants
50/// * `Forward` - The default direction for normal graph connections. In a forward
51///   connection, data flows from input nodes through intermediate nodes to output nodes.
52/// * `Backward` - Indicates a recurrent connection where data can flow backwards,
53///   creating cycles in the graph. This is used to implement recurrent neural networks
54///   and other cyclic graph structures.
55///
56/// # Examples
57/// ```
58/// use radiate_gp::collections::{graphs::Direction, GraphNode, NodeType};
59///
60/// let mut node = GraphNode::new(0, NodeType::Vertex, 42);
61/// assert_eq!(node.direction(), Direction::Forward);
62///
63/// // Create a recurrent connection
64/// node.set_direction(Direction::Backward);
65/// assert!(node.is_recurrent());
66/// ```
67///
68/// # Usage in Graphs
69/// * By default, graphs are directed acyclic graphs (DAGs) with all connections in the
70///   `Forward` direction
71/// * Setting a node's direction to `Backward` allows for cyclic connections
72/// * The `Graph::set_cycles` method automatically sets appropriate nodes to `Backward`
73///   direction when cycles are detected
74///
75/// # Implementation Details
76/// * Implements `Debug`, `Clone`, `Copy`, `PartialEq`, `Eq`, and `Hash`
77/// * When the "serde" feature is enabled, implements `Serialize` and `Deserialize`
78#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
79#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
80pub enum Direction {
81    Forward,
82    Backward,
83}
84
85/// A node in a graph structure that represents a single element with connections to other nodes.
86///
87/// The [GraphNode] struct is a fundamental building block for graph-based genetic programming in Radiate.
88/// It represents a node in a directed graph that can have both incoming and outgoing connections to other nodes.
89/// Each node has a unique identifier, an index in the graph, a value of type T, and maintains sets of incoming
90/// and outgoing connections.
91///
92/// # Type Parameters
93/// * `T` - The type of value stored in the node. This type must implement `Clone`, `PartialEq`, and other traits
94///         required by the genetic programming operations.
95///
96/// # Fields
97/// * `value` - The actual value stored in the node
98/// * `id` - A unique identifier for the node ([GraphNodeId])
99/// * `index` - The position of the node in the graph's node collection
100/// * `direction` - The direction of the node's connections (Forward or Backward)
101/// * `node_type` - Optional [NodeType] that specifies the role of the node (Input, Output, Vertex, Edge, etc.)
102/// * `arity` - Optional [Arity] that specifies how many incoming connections the node can have. If
103/// the arity is not supplied, the node will try it's best to determine it based on the node type and
104/// the number of connections.
105/// * `incoming` - Set of indices of nodes that have connections to this node
106/// * `outgoing` - Set of indices of nodes that this node has connections to
107///
108/// # Examples
109/// ```
110/// use radiate_gp::{collections::{GraphNode, NodeType}, Arity};
111///
112/// // Create a new input node with value 42
113/// let node = GraphNode::new(0, NodeType::Input, 42);
114///
115/// // Create a node with specific arity
116/// // This node will be invalid if it has a number of incoming connections other than 2
117/// let node_with_arity = GraphNode::with_arity(1, NodeType::Vertex, 42, Arity::Exact(2));
118/// ```
119///
120/// # Node Types and Arity
121/// The node's type and arity determine its behavior and validity:
122/// * `Input` nodes should have no incoming connections and at least one outgoing connection
123/// * `Output` nodes should have at least one incoming connection
124/// * `Vertex` nodes can have both incoming and outgoing connections
125/// * `Edge` nodes should have exactly one incoming and one outgoing connection
126///
127/// # Recurrent Connections
128/// Nodes can form recurrent connections (cycles) in the graph by:
129/// * Setting the node's direction to `Direction::Backward`
130/// * Having a connection to itself (index in incoming/outgoing sets)
131///
132/// # Validity
133/// A node is considered valid based on its type and connections:
134/// * `Input` nodes are valid when they have no incoming connections and at least one outgoing connection
135/// * `Output` nodes are valid when they have at least one incoming connection
136/// * `Vertex` nodes are valid when they have both incoming and outgoing connections
137/// * `Edge` nodes are valid when they have exactly one incoming and one outgoing connection
138///
139/// # Implementation Details
140/// The struct implements several traits:
141/// * `Node` - Provides common node behavior and access to value and type information
142/// * `Gene` - Enables genetic operations for the node making it compatible with genetic algorithms
143/// * `Valid` - Defines validity rules for the node
144/// * `Debug` - Provides debug formatting
145/// * `Clone`, `PartialEq` - Required for genetic programming operations
146///
147/// # Serialization
148/// When the "serde" feature is enabled, the struct implements `Serialize` and `Deserialize` traits.
149#[derive(Clone, PartialEq)]
150#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
151pub struct GraphNode<T> {
152    value: T,
153    id: GraphNodeId,
154    index: usize,
155    direction: Direction,
156    node_type: Option<NodeType>,
157    arity: Option<Arity>,
158    incoming: SortedBuffer<usize>,
159    outgoing: SortedBuffer<usize>,
160}
161
162impl<T> GraphNode<T> {
163    /// Creates a new [GraphNode] with the specified index, node type, and value.
164    ///
165    /// This is the most basic constructor for a graph node, initializing it with
166    /// default direction (Forward) and no specific arity or node type.
167    pub fn new(index: usize, node_type: NodeType, value: T) -> Self {
168        GraphNode {
169            id: GraphNodeId::new(),
170            index,
171            value,
172            direction: Direction::Forward,
173            node_type: Some(node_type),
174            arity: None,
175            incoming: SortedBuffer::new(),
176            outgoing: SortedBuffer::new(),
177        }
178    }
179
180    /// Creates a new [GraphNode] with the specified index, node type, value, and arity.
181    ///
182    /// This constructor allows for more control over the node's behavior by specifying
183    /// the arity, which defines how many incoming connections the node can accept - if the
184    /// number of connections does not match the arity, the node will be considered invalid.
185    pub fn with_arity(index: usize, node_type: NodeType, value: T, arity: Arity) -> Self {
186        GraphNode {
187            id: GraphNodeId::new(),
188            index,
189            value,
190            direction: Direction::Forward,
191            node_type: Some(node_type),
192            arity: Some(arity),
193            incoming: SortedBuffer::new(),
194            outgoing: SortedBuffer::new(),
195        }
196    }
197
198    pub fn with_incoming<I: IntoIterator<Item = usize>>(mut self, incoming: I) -> Self {
199        SortedBuffer::set_sorted_unique(&mut self.incoming, incoming);
200        self
201    }
202
203    pub fn with_outgoing<O: IntoIterator<Item = usize>>(mut self, outgoing: O) -> Self {
204        SortedBuffer::set_sorted_unique(&mut self.outgoing, outgoing);
205        self
206    }
207
208    pub fn direction(&self) -> Direction {
209        self.direction
210    }
211
212    pub fn set_direction(&mut self, direction: Direction) {
213        self.direction = direction;
214    }
215
216    pub fn index(&self) -> usize {
217        self.index
218    }
219
220    pub fn id(&self) -> &GraphNodeId {
221        &self.id
222    }
223
224    pub fn is_recurrent(&self) -> bool {
225        self.direction == Direction::Backward
226            || self.incoming.contains(&self.index)
227            || self.outgoing.contains(&self.index)
228    }
229
230    pub fn incoming(&self) -> &[usize] {
231        self.incoming.as_slice()
232    }
233
234    pub fn outgoing(&self) -> &[usize] {
235        self.outgoing.as_slice()
236    }
237
238    pub fn incoming_mut(&mut self) -> &mut [usize] {
239        self.incoming.as_mut_slice()
240    }
241
242    pub fn outgoing_mut(&mut self) -> &mut [usize] {
243        self.outgoing.as_mut_slice()
244    }
245
246    pub fn is_locked(&self) -> bool {
247        match self.arity() {
248            Arity::Any => false,
249            _ => self.incoming.len() == *self.arity(),
250        }
251    }
252
253    pub fn insert_incoming(&mut self, value: usize) {
254        SortedBuffer::insert_sorted_unique(&mut self.incoming, value);
255    }
256
257    pub fn remove_incoming(&mut self, value: &usize) {
258        SortedBuffer::remove_sorted(&mut self.incoming, value);
259    }
260
261    pub fn insert_outgoing(&mut self, value: usize) {
262        SortedBuffer::insert_sorted_unique(&mut self.outgoing, value);
263    }
264
265    pub fn remove_outgoing(&mut self, value: &usize) {
266        SortedBuffer::remove_sorted(&mut self.outgoing, value);
267    }
268}
269
270/// Implementing the [Node] trait for [GraphNode]
271/// This joins common functionality for nodes in a graph structure together.
272impl<T> Node for GraphNode<T> {
273    type Value = T;
274
275    fn value(&self) -> &Self::Value {
276        &self.value
277    }
278
279    fn value_mut(&mut self) -> &mut Self::Value {
280        &mut self.value
281    }
282
283    fn node_type(&self) -> NodeType {
284        if let Some(node_type) = self.node_type {
285            return node_type;
286        }
287
288        let arity = self.arity();
289
290        if let Arity::Any = arity {
291            if self.outgoing.is_empty() && self.incoming.is_empty() {
292                NodeType::Vertex
293            } else if self.outgoing.is_empty() {
294                NodeType::Output
295            } else {
296                NodeType::Vertex
297            }
298        } else if let Arity::Exact(1) = arity {
299            if self.incoming.len() == 1 && self.outgoing.len() == 1 {
300                NodeType::Edge
301            } else {
302                NodeType::Vertex
303            }
304        } else if let Arity::Zero = arity {
305            NodeType::Input
306        } else {
307            NodeType::Vertex
308        }
309    }
310
311    fn arity(&self) -> Arity {
312        if let Some(node_type) = self.node_type {
313            return self.arity.unwrap_or(match node_type {
314                NodeType::Input => Arity::Zero,
315                NodeType::Output => Arity::Any,
316                NodeType::Vertex => Arity::Any,
317                NodeType::Edge => Arity::Exact(1),
318                NodeType::Leaf => Arity::Zero,
319                NodeType::Root => Arity::Any,
320            });
321        }
322
323        self.arity.unwrap_or(Arity::Any)
324    }
325}
326
327impl<T> Gene for GraphNode<T>
328where
329    T: Clone + PartialEq,
330{
331    type Allele = T;
332
333    fn allele(&self) -> &Self::Allele {
334        self.value()
335    }
336
337    fn allele_mut(&mut self) -> &mut Self::Allele {
338        &mut self.value
339    }
340
341    fn new_instance(&self) -> GraphNode<T> {
342        GraphNode {
343            id: GraphNodeId::new(),
344            index: self.index,
345            value: self.value.clone(),
346            direction: self.direction,
347            node_type: self.node_type,
348            arity: self.arity,
349            incoming: self.incoming.clone(),
350            outgoing: self.outgoing.clone(),
351        }
352    }
353
354    fn with_allele(&self, allele: &Self::Allele) -> GraphNode<T> {
355        GraphNode {
356            id: GraphNodeId::new(),
357            index: self.index,
358            value: allele.clone(),
359            direction: self.direction,
360            node_type: self.node_type,
361            arity: self.arity,
362            incoming: self.incoming.clone(),
363            outgoing: self.outgoing.clone(),
364        }
365    }
366}
367
368/// Implementing the [Valid] trait for [GraphNode]
369/// This trait checks if the node is valid based on its type and connections.
370/// A valid node must have the correct number of incoming and outgoing connections
371/// according to its arity and node type.
372///
373/// A node is considered valid based on its type and connections:
374/// * `Input` nodes are valid when they have no incoming connections and at least one outgoing connection
375/// * `Output` nodes are valid when they have at least one incoming connection
376/// * `Vertex` nodes are valid when they have both incoming and outgoing connections
377/// * `Edge` nodes are valid when they have exactly one incoming and one outgoing connection
378impl<T> Valid for GraphNode<T> {
379    #[inline]
380    fn is_valid(&self) -> bool {
381        match self.node_type() {
382            NodeType::Input => self.incoming.is_empty() && !self.outgoing.is_empty(),
383            NodeType::Output => {
384                (!self.incoming.is_empty())
385                    && (self.incoming.len() == *self.arity() || self.arity() == Arity::Any)
386            }
387            NodeType::Vertex => {
388                if !self.incoming.is_empty() && !self.outgoing.is_empty() {
389                    if let Arity::Exact(n) = self.arity() {
390                        return self.incoming.len() == n;
391                    } else if self.arity() == Arity::Any {
392                        return true;
393                    }
394                }
395                false
396            }
397            NodeType::Edge => {
398                if self.arity() == Arity::Exact(1) {
399                    return self.incoming.len() == 1 && self.outgoing.len() == 1;
400                }
401
402                false
403            }
404            _ => false,
405        }
406    }
407}
408
409impl<T> From<(usize, NodeType, T)> for GraphNode<T> {
410    fn from((index, node_type, value): (usize, NodeType, T)) -> Self {
411        GraphNode::new(index, node_type, value)
412    }
413}
414
415impl<T: Default> From<(usize, T)> for GraphNode<T> {
416    fn from((index, value): (usize, T)) -> Self {
417        GraphNode {
418            index,
419            id: GraphNodeId::new(),
420            value,
421            direction: Direction::Forward,
422            node_type: None,
423            arity: None,
424            incoming: SortedBuffer::new(),
425            outgoing: SortedBuffer::new(),
426        }
427    }
428}
429
430impl<T> From<(usize, NodeType, T, Arity)> for GraphNode<T> {
431    fn from((index, node_type, value, arity): (usize, NodeType, T, Arity)) -> Self {
432        GraphNode::with_arity(index, node_type, value, arity)
433    }
434}
435
436impl<T: Default> From<(usize, T, Arity)> for GraphNode<T> {
437    fn from((index, value, arity): (usize, T, Arity)) -> Self {
438        GraphNode {
439            index,
440            id: GraphNodeId::new(),
441            value,
442            direction: Direction::Forward,
443            node_type: None,
444            arity: Some(arity),
445            incoming: SortedBuffer::new(),
446            outgoing: SortedBuffer::new(),
447        }
448    }
449}
450
451impl<T, I> From<(usize, NodeType, T, I, I)> for GraphNode<T>
452where
453    I: Into<SortedBuffer<usize>>,
454{
455    fn from((index, node_type, value, incoming, outgoing): (usize, NodeType, T, I, I)) -> Self {
456        let incoming = incoming.into();
457        let outgoing = outgoing.into();
458
459        GraphNode {
460            index,
461            id: GraphNodeId::new(),
462            value,
463            direction: Direction::Forward,
464            node_type: Some(node_type),
465            arity: None,
466            incoming,
467            outgoing,
468        }
469    }
470}
471
472impl<T: Default> Default for GraphNode<T> {
473    fn default() -> Self {
474        GraphNode {
475            id: GraphNodeId::new(),
476            index: 0,
477            value: Default::default(),
478            direction: Direction::Forward,
479            node_type: None,
480            arity: None,
481            incoming: SortedBuffer::new(),
482            outgoing: SortedBuffer::new(),
483        }
484    }
485}
486
487impl<T: Hash> Hash for GraphNode<T> {
488    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
489        self.id.hash(state);
490        self.index.hash(state);
491        self.direction.hash(state);
492        self.node_type.hash(state);
493        self.arity.hash(state);
494        self.incoming.hash(state);
495        self.outgoing.hash(state);
496        self.value.hash(state);
497    }
498
499    fn hash_slice<H: std::hash::Hasher>(data: &[Self], state: &mut H)
500    where
501        Self: Sized,
502    {
503        for item in data {
504            item.hash(state);
505        }
506    }
507}
508
509impl<T: Debug> Debug for GraphNode<T> {
510    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
511        let incoming = self
512            .incoming
513            .iter()
514            .map(|idx| idx.to_string())
515            .collect::<Vec<String>>()
516            .join(", ");
517
518        write!(
519            f,
520            "[{:<3}] [{:<7?}] {:>10?} :: {:<10} {:<12} V:{:<5} R:{:<5} {:<2} {:<2} < [{}]",
521            self.index,
522            self.id.0,
523            format!("{:?}", self.node_type())[..3].to_owned(),
524            self.arity(),
525            format!("{:?}", self.value).to_owned(),
526            self.is_valid(),
527            self.is_recurrent(),
528            self.incoming.len(),
529            self.outgoing.len(),
530            incoming,
531        )
532    }
533}
534
535#[cfg(test)]
536mod tests {
537    use super::*;
538    use crate::NodeType;
539
540    #[test]
541    fn test_graph_node_default() {
542        let node = GraphNode::<usize>::default();
543
544        assert_eq!(node.index(), 0);
545        assert_eq!(node.node_type(), NodeType::Vertex);
546        assert_eq!(node.arity(), Arity::Any);
547        assert!(!node.is_valid());
548        assert!(!node.is_recurrent());
549        assert_eq!(node.incoming(), &[] as &[usize]);
550        assert_eq!(node.outgoing(), &[] as &[usize]);
551    }
552
553    #[test]
554    fn test_graph_node() {
555        let node = GraphNode::new(0, NodeType::Input, 0.0);
556
557        assert_eq!(node.index(), 0);
558        assert_eq!(node.node_type(), NodeType::Input);
559        assert_eq!(node.arity(), Arity::Zero);
560        assert!(!node.is_valid());
561        assert!(!node.is_recurrent());
562        assert_eq!(node.incoming(), &[] as &[usize]);
563        assert_eq!(node.outgoing(), &[] as &[usize]);
564    }
565
566    #[test]
567    fn test_graph_node_with_arity() {
568        let node = GraphNode::with_arity(0, NodeType::Input, 0.0, Arity::Zero);
569
570        assert_eq!(node.index(), 0);
571        assert_eq!(node.node_type(), NodeType::Input);
572        assert_eq!(node.arity(), Arity::Zero);
573        assert!(!node.is_valid());
574        assert!(!node.is_recurrent());
575        assert_eq!(node.incoming(), &[] as &[usize]);
576        assert_eq!(node.outgoing(), &[] as &[usize]);
577    }
578
579    #[test]
580    fn test_graph_node_with_allele() {
581        let node = GraphNode::new(0, NodeType::Input, 0.0);
582
583        let new_node = node.with_allele(&1.0);
584        assert_eq!(new_node.index(), 0);
585        assert_eq!(new_node.node_type(), NodeType::Input);
586        assert_eq!(new_node.arity(), Arity::Zero);
587        assert!(!new_node.is_valid());
588        assert!(!new_node.is_recurrent());
589        assert_eq!(new_node.incoming(), &[] as &[usize]);
590        assert_eq!(new_node.outgoing(), &[] as &[usize]);
591    }
592
593    #[test]
594    fn test_graph_node_with_direction() {
595        let mut node_one = GraphNode::new(0, NodeType::Input, 0.0);
596
597        assert!(!node_one.is_recurrent());
598        node_one.set_direction(Direction::Backward);
599        assert!(node_one.is_recurrent());
600
601        let mut node_two = GraphNode::new(0, NodeType::Input, 0.0);
602
603        assert!(!node_two.is_recurrent());
604        node_two.insert_incoming(0);
605        assert!(node_two.is_recurrent());
606    }
607
608    #[test]
609    fn graph_node_from_fns_produce_valid_arities() {
610        let node = GraphNode::from((0, NodeType::Input, 0.0));
611        assert_eq!(node.arity(), Arity::Zero);
612
613        let node = GraphNode::from((0, NodeType::Output, 0.0));
614        assert_eq!(node.arity(), Arity::Any);
615
616        let node = GraphNode::from((0, NodeType::Vertex, 0.0));
617        assert_eq!(node.arity(), Arity::Any);
618
619        let node = GraphNode::from((0, NodeType::Edge, 0.0));
620        assert_eq!(node.arity(), Arity::Exact(1));
621
622        let node = GraphNode::from((0, NodeType::Input, 0.0, Arity::Zero));
623        assert_eq!(node.arity(), Arity::Zero);
624
625        let node = GraphNode::from((0, NodeType::Output, 0.0, Arity::Any));
626        assert_eq!(node.arity(), Arity::Any);
627
628        let node = GraphNode::from((0, NodeType::Vertex, 0.0, Arity::Any));
629        assert_eq!(node.arity(), Arity::Any);
630
631        let node = GraphNode::from((0, NodeType::Edge, 0.0, Arity::Exact(1)));
632        assert_eq!(node.arity(), Arity::Exact(1));
633    }
634
635    #[test]
636    fn test_graph_node_validity() {
637        let mut input_node = GraphNode::new(0, NodeType::Input, 0.0);
638        assert!(!input_node.is_valid());
639
640        input_node.insert_outgoing(1);
641        assert!(input_node.is_valid());
642
643        let mut output_node = GraphNode::new(1, NodeType::Output, 0.0);
644        assert!(!output_node.is_valid());
645
646        output_node.insert_incoming(0);
647        assert!(output_node.is_valid());
648    }
649
650    #[test]
651    fn test_graph_node_connections_sorted() {
652        let mut node = GraphNode::new(0, NodeType::Vertex, 0.0);
653
654        node.insert_incoming(3);
655        node.insert_incoming(1);
656        node.insert_incoming(2);
657        node.insert_incoming(2); // Duplicate
658
659        assert_eq!(node.incoming(), &[1, 2, 3]);
660
661        node.insert_outgoing(5);
662        node.insert_outgoing(4);
663        node.insert_outgoing(6);
664        node.insert_outgoing(5); // Duplicate
665
666        assert_eq!(node.outgoing(), &[4, 5, 6]);
667
668        node.remove_incoming(&2);
669        assert_eq!(node.incoming(), &[1, 3]);
670
671        node.remove_outgoing(&5);
672        assert_eq!(node.outgoing(), &[4, 6]);
673    }
674
675    #[test]
676    #[cfg(feature = "serde")]
677    fn test_graph_node_serde() {
678        let node = GraphNode::new(0, NodeType::Input, 42.0);
679        let serialized = serde_json::to_string(&node).unwrap();
680        let deserialized = serde_json::from_str::<GraphNode<f32>>(&serialized).unwrap();
681
682        assert_eq!(node, deserialized);
683        assert_eq!(node.value(), &42.0);
684        assert_eq!(deserialized.value(), &42.0);
685    }
686}
radiate_gp/collections/graphs/node.rs

radiate_gp/collections/graphs/
node.rs
