radiate_gp/collections/graphs/
node.rs

1use crate::node::Node;
2use crate::{Arity, NodeType};
3use radiate_core::{Gene, Valid, sentry_id};
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;
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
351/// Implementing the [Valid] trait for [GraphNode]
352/// This trait checks if the node is valid based on its type and connections.
353/// A valid node must have the correct number of incoming and outgoing connections
354/// according to its arity and node type.
355///
356/// A node is considered valid based on its type and connections:
357/// * `Input` nodes are valid when they have no incoming connections and at least one outgoing connection
358/// * `Output` nodes are valid when they have at least one incoming connection
359/// * `Vertex` nodes are valid when they have both incoming and outgoing connections
360/// * `Edge` nodes are valid when they have exactly one incoming and one outgoing connection
361impl<T> Valid for GraphNode<T> {
362    #[inline]
363    fn is_valid(&self) -> bool {
364        match self.node_type() {
365            NodeType::Input => self.incoming.is_empty() && !self.outgoing.is_empty(),
366            NodeType::Output => {
367                (!self.incoming.is_empty())
368                    && (self.incoming.len() == *self.arity() || self.arity() == Arity::Any)
369            }
370            NodeType::Vertex => {
371                if !self.incoming.is_empty() && !self.outgoing.is_empty() {
372                    if let Arity::Exact(n) = self.arity() {
373                        return self.incoming.len() == n;
374                    } else if self.arity() == Arity::Any {
375                        return true;
376                    }
377                }
378                false
379            }
380            NodeType::Edge => {
381                if self.arity() == Arity::Exact(1) {
382                    return self.incoming.len() == 1 && self.outgoing.len() == 1;
383                }
384
385                false
386            }
387            _ => false,
388        }
389    }
390}
391
392impl<T> From<(usize, NodeType, T)> for GraphNode<T> {
393    fn from((index, node_type, value): (usize, NodeType, T)) -> Self {
394        GraphNode::new(index, node_type, value)
395    }
396}
397
398impl<T: Default> From<(usize, T)> for GraphNode<T> {
399    fn from((index, value): (usize, T)) -> Self {
400        GraphNode {
401            index,
402            id: GraphNodeId::new(),
403            value,
404            direction: Direction::Forward,
405            node_type: None,
406            arity: None,
407            innovation: None,
408            incoming: SortedBuffer::new(),
409            outgoing: SortedBuffer::new(),
410        }
411    }
412}
413
414impl<T> From<(usize, NodeType, T, Arity)> for GraphNode<T> {
415    fn from((index, node_type, value, arity): (usize, NodeType, T, Arity)) -> Self {
416        GraphNode::with_arity(index, node_type, value, arity)
417    }
418}
419
420impl<T: Default> From<(usize, T, Arity)> for GraphNode<T> {
421    fn from((index, value, arity): (usize, T, Arity)) -> Self {
422        GraphNode {
423            index,
424            id: GraphNodeId::new(),
425            value,
426            direction: Direction::Forward,
427            node_type: None,
428            arity: Some(arity),
429            innovation: None,
430            incoming: SortedBuffer::new(),
431            outgoing: SortedBuffer::new(),
432        }
433    }
434}
435
436impl<T, I> From<(usize, NodeType, T, I, I)> for GraphNode<T>
437where
438    I: Into<SortedBuffer<usize>>,
439{
440    fn from((index, node_type, value, incoming, outgoing): (usize, NodeType, T, I, I)) -> Self {
441        let incoming = incoming.into();
442        let outgoing = outgoing.into();
443
444        GraphNode {
445            index,
446            id: GraphNodeId::new(),
447            value,
448            direction: Direction::Forward,
449            node_type: Some(node_type),
450            arity: None,
451            innovation: None,
452            incoming,
453            outgoing,
454        }
455    }
456}
457
458impl<T: Default> Default for GraphNode<T> {
459    fn default() -> Self {
460        GraphNode {
461            id: GraphNodeId::new(),
462            index: 0,
463            value: Default::default(),
464            direction: Direction::Forward,
465            node_type: None,
466            arity: None,
467            innovation: None,
468            incoming: SortedBuffer::new(),
469            outgoing: SortedBuffer::new(),
470        }
471    }
472}
473
474impl<T: Hash> Hash for GraphNode<T> {
475    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
476        self.id.hash(state);
477        self.index.hash(state);
478        self.direction.hash(state);
479        self.node_type.hash(state);
480        self.arity.hash(state);
481        self.incoming.hash(state);
482        self.outgoing.hash(state);
483        self.innovation.hash(state);
484        self.value.hash(state);
485    }
486
487    fn hash_slice<H: std::hash::Hasher>(data: &[Self], state: &mut H)
488    where
489        Self: Sized,
490    {
491        for item in data {
492            item.hash(state);
493        }
494    }
495}
496
497impl<T: Debug> Debug for GraphNode<T> {
498    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
499        let incoming = self
500            .incoming
501            .iter()
502            .map(|idx| idx.to_string())
503            .collect::<Vec<String>>()
504            .join(", ");
505
506        write!(
507            f,
508            "[{:<3}] [{:<7?}] [{:<5?}] {:>10?} :: {:<10} {:<20}  V:{:<5} R:{:<5} {:<2} {:<2} < [{}]",
509            self.index,
510            self.id.0,
511            self.innovation.map(|id| id.0).unwrap_or(0),
512            format!("{:?}", self.node_type())[..3].to_owned(),
513            self.arity(),
514            format!("{:.4?}", self.value), // pre-format with precision → String
515            self.is_valid(),
516            self.is_recurrent(),
517            self.incoming.len(),
518            self.outgoing.len(),
519            incoming,
520        )
521    }
522}
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527    use crate::NodeType;
528
529    #[test]
530    fn test_graph_node_default() {
531        let node = GraphNode::<usize>::default();
532
533        assert_eq!(node.index(), 0);
534        assert_eq!(node.node_type(), NodeType::Vertex);
535        assert_eq!(node.arity(), Arity::Any);
536        assert!(!node.is_valid());
537        assert!(!node.is_recurrent());
538        assert_eq!(node.incoming(), &[] as &[usize]);
539        assert_eq!(node.outgoing(), &[] as &[usize]);
540    }
541
542    #[test]
543    fn test_graph_node() {
544        let node = GraphNode::new(0, NodeType::Input, 0.0);
545
546        assert_eq!(node.index(), 0);
547        assert_eq!(node.node_type(), NodeType::Input);
548        assert_eq!(node.arity(), Arity::Zero);
549        assert!(!node.is_valid());
550        assert!(!node.is_recurrent());
551        assert_eq!(node.incoming(), &[] as &[usize]);
552        assert_eq!(node.outgoing(), &[] as &[usize]);
553    }
554
555    #[test]
556    fn test_graph_node_with_arity() {
557        let node = GraphNode::with_arity(0, NodeType::Input, 0.0, Arity::Zero);
558
559        assert_eq!(node.index(), 0);
560        assert_eq!(node.node_type(), NodeType::Input);
561        assert_eq!(node.arity(), Arity::Zero);
562        assert!(!node.is_valid());
563        assert!(!node.is_recurrent());
564        assert_eq!(node.incoming(), &[] as &[usize]);
565        assert_eq!(node.outgoing(), &[] as &[usize]);
566    }
567
568    #[test]
569    fn test_graph_node_with_allele() {
570        let node = GraphNode::new(0, NodeType::Input, 0.0);
571
572        let new_node = node.with_allele(&1.0);
573        assert_eq!(new_node.index(), 0);
574        assert_eq!(new_node.node_type(), NodeType::Input);
575        assert_eq!(new_node.arity(), Arity::Zero);
576        assert!(!new_node.is_valid());
577        assert!(!new_node.is_recurrent());
578        assert_eq!(new_node.incoming(), &[] as &[usize]);
579        assert_eq!(new_node.outgoing(), &[] as &[usize]);
580    }
581
582    #[test]
583    fn test_graph_node_with_direction() {
584        let mut node_one = GraphNode::new(0, NodeType::Input, 0.0);
585
586        assert!(!node_one.is_recurrent());
587        node_one.set_direction(Direction::Backward);
588        assert!(node_one.is_recurrent());
589
590        let mut node_two = GraphNode::new(0, NodeType::Input, 0.0);
591
592        assert!(!node_two.is_recurrent());
593        node_two.insert_incoming(0);
594        assert!(node_two.is_recurrent());
595    }
596
597    #[test]
598    fn graph_node_from_fns_produce_valid_arities() {
599        let node = GraphNode::from((0, NodeType::Input, 0.0));
600        assert_eq!(node.arity(), Arity::Zero);
601
602        let node = GraphNode::from((0, NodeType::Output, 0.0));
603        assert_eq!(node.arity(), Arity::Any);
604
605        let node = GraphNode::from((0, NodeType::Vertex, 0.0));
606        assert_eq!(node.arity(), Arity::Any);
607
608        let node = GraphNode::from((0, NodeType::Edge, 0.0));
609        assert_eq!(node.arity(), Arity::Exact(1));
610
611        let node = GraphNode::from((0, NodeType::Input, 0.0, Arity::Zero));
612        assert_eq!(node.arity(), Arity::Zero);
613
614        let node = GraphNode::from((0, NodeType::Output, 0.0, Arity::Any));
615        assert_eq!(node.arity(), Arity::Any);
616
617        let node = GraphNode::from((0, NodeType::Vertex, 0.0, Arity::Any));
618        assert_eq!(node.arity(), Arity::Any);
619
620        let node = GraphNode::from((0, NodeType::Edge, 0.0, Arity::Exact(1)));
621        assert_eq!(node.arity(), Arity::Exact(1));
622    }
623
624    #[test]
625    fn test_graph_node_validity() {
626        let mut input_node = GraphNode::new(0, NodeType::Input, 0.0);
627        assert!(!input_node.is_valid());
628
629        input_node.insert_outgoing(1);
630        assert!(input_node.is_valid());
631
632        let mut output_node = GraphNode::new(1, NodeType::Output, 0.0);
633        assert!(!output_node.is_valid());
634
635        output_node.insert_incoming(0);
636        assert!(output_node.is_valid());
637    }
638
639    #[test]
640    fn test_graph_node_connections_sorted() {
641        let mut node = GraphNode::new(0, NodeType::Vertex, 0.0);
642
643        node.insert_incoming(3);
644        node.insert_incoming(1);
645        node.insert_incoming(2);
646        node.insert_incoming(2); // Duplicate
647
648        assert_eq!(node.incoming(), &[1, 2, 3]);
649
650        node.insert_outgoing(5);
651        node.insert_outgoing(4);
652        node.insert_outgoing(6);
653        node.insert_outgoing(5); // Duplicate
654
655        assert_eq!(node.outgoing(), &[4, 5, 6]);
656
657        node.remove_incoming(&2);
658        assert_eq!(node.incoming(), &[1, 3]);
659
660        node.remove_outgoing(&5);
661        assert_eq!(node.outgoing(), &[4, 6]);
662    }
663
664    #[test]
665    #[cfg(feature = "serde")]
666    fn test_graph_node_serde() {
667        let node = GraphNode::new(0, NodeType::Input, 42.0);
668        let serialized = serde_json::to_string(&node).unwrap();
669        let deserialized = serde_json::from_str::<GraphNode<f32>>(&serialized).unwrap();
670
671        assert_eq!(node, deserialized);
672        assert_eq!(node.value(), &42.0);
673        assert_eq!(deserialized.value(), &42.0);
674    }
675}
radiate_gp/collections/graphs/node.rs

radiate_gp/collections/graphs/
node.rs
