radiate_gp/collections/graphs/
node.rs

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

radiate_gp/collections/graphs/
node.rs
