radiate_gp/collections/graphs/
chromosome.rs

1use crate::{Factory, GraphNode, NodeStore, node::Node};
2use radiate_core::{Chromosome, Gene, Valid};
3#[cfg(feature = "serde")]
4use serde::{Deserialize, Serialize};
5use std::{fmt::Debug, hash::Hash};
6
7/// A chromosome type that represents a directed graph structure for genetic programming.
8/// This chromosome is essentially just a graph, the only difference is the name of the struct.
9/// The graph and the [GraphChromosome] are interchangeable, the only difference is who holds
10/// the vector of nodes. For instance, to create a graph from the [GraphChromosome], just take
11/// the vector of nodes and give them to a new graph instance - boom, you have a graph.
12///
13/// [GraphChromosome] is a specialized chromosome type that maintains a collection of graph nodes
14/// and their connections. It's designed for genetic programming applications where the solution
15/// space can be represented as a directed graph.
16///
17/// # Type Parameters
18/// * `T` - The type of value stored in each node. Must implement `Clone` and `PartialEq`.
19///
20/// # Structure
21/// The chromosome consists of:
22/// * A vector of [`GraphNode<T>`] instances representing the graph structure
23/// * An optional [`NodeStore<T>`] for managing node creation and validation. This makes
24/// the creation of new nodes easier and more uniform across the genetic algorithm.
25///
26/// # Features
27/// * Maintains graph connectivity through node connections
28/// * Provides factory methods for creating new instances
29/// * Implements serialization when the "serde" feature is enabled
30/// * Allows the graph nodes, essentially the graph, to be evolved through the genetic algorithm
31///
32/// # Examples
33/// ```
34/// use radiate_gp::collections::graphs::{GraphChromosome, GraphNode, Graph};
35/// use radiate_gp::{NodeStore, node_store, NodeType};
36///
37/// // Create a new chromosome with some nodes
38///let store = node_store! {
39///     Input => vec![1, 2, 3],
40///     Output => vec![4, 5, 6],
41///     Edge => vec![7, 8, 9],
42///     Vertex => vec![10, 11, 12]
43/// };
44///
45/// let graph = Graph::directed(1, 1, store.clone());
46///
47/// let chromosome = GraphChromosome::from((graph, store));
48/// ```
49///
50/// # Genetic Operations
51/// The chromosome supports several genetic operations:
52/// * Crossover through `GraphCrossover`
53/// * Mutation through `GraphMutator`
54/// * Replacement through `GraphReplacement`
55///
56/// # Serialization
57/// When the "serde" feature is enabled, the chromosome can be serialized and deserialized.
58/// The serialization preserves the graph structure and node values, but not the node store.
59///
60/// # Performance
61/// * Node access is O(1) through vector indexing
62/// * Graph operations (adding/removing nodes/edges) are O(log n) due to BTreeSet usage
63/// * Memory usage is O(V + E) where V is the number of nodes and E is the number of edges
64#[derive(Clone)]
65#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
66pub struct GraphChromosome<T> {
67    nodes: Vec<GraphNode<T>>,
68    store: Option<NodeStore<T>>,
69    max_nodes: Option<usize>,
70}
71
72impl<T> GraphChromosome<T> {
73    pub fn new(nodes: Vec<GraphNode<T>>, factory: NodeStore<T>) -> Self {
74        GraphChromosome {
75            nodes,
76            store: Some(factory),
77            max_nodes: None,
78        }
79    }
80
81    pub fn with_max_nodes(mut self, max_nodes: usize) -> Self {
82        self.max_nodes = Some(max_nodes + self.nodes.len());
83        self
84    }
85
86    pub fn take_nodes(&mut self) -> Vec<GraphNode<T>> {
87        std::mem::take(&mut self.nodes)
88    }
89
90    pub fn set_nodes(&mut self, nodes: Vec<GraphNode<T>>) {
91        self.nodes = nodes;
92    }
93
94    pub fn store(&self) -> Option<&NodeStore<T>> {
95        self.store.as_ref()
96    }
97
98    pub fn max_nodes(&self) -> Option<usize> {
99        self.max_nodes
100    }
101}
102
103impl<T> Factory<Option<NodeStore<T>>, GraphChromosome<T>> for GraphChromosome<T>
104where
105    T: Clone + PartialEq + Default,
106{
107    fn new_instance(&self, input: Option<NodeStore<T>>) -> GraphChromosome<T> {
108        input
109            .or_else(|| self.store.clone())
110            .map(|store| GraphChromosome {
111                nodes: self
112                    .iter()
113                    .enumerate()
114                    .filter_map(|(index, node)| {
115                        store
116                            .new_instance((index, node.node_type()))
117                            .map(|new_node| {
118                                if new_node.arity() == node.arity() {
119                                    node.with_allele(new_node.allele())
120                                } else {
121                                    node.clone()
122                                }
123                            })
124                    })
125                    .collect(),
126                store: Some(store),
127                max_nodes: self.max_nodes,
128            })
129            .map(|chromosome| {
130                if chromosome.len() != self.len() {
131                    self.clone()
132                } else {
133                    chromosome
134                }
135            })
136            .unwrap_or_else(|| self.clone())
137    }
138}
139
140impl<T> Chromosome for GraphChromosome<T>
141where
142    T: Clone + PartialEq,
143{
144    type Gene = GraphNode<T>;
145
146    fn as_slice(&self) -> &[GraphNode<T>] {
147        &self.nodes
148    }
149
150    fn as_mut_slice(&mut self) -> &mut [GraphNode<T>] {
151        &mut self.nodes
152    }
153}
154
155impl<T> Valid for GraphChromosome<T> {
156    #[inline]
157    fn is_valid(&self) -> bool {
158        self.nodes.iter().all(|gene| gene.is_valid())
159    }
160}
161
162impl<T> AsRef<[GraphNode<T>]> for GraphChromosome<T> {
163    fn as_ref(&self) -> &[GraphNode<T>] {
164        &self.nodes
165    }
166}
167
168impl<T> AsMut<[GraphNode<T>]> for GraphChromosome<T> {
169    fn as_mut(&mut self) -> &mut [GraphNode<T>] {
170        &mut self.nodes
171    }
172}
173
174impl<T: PartialEq> PartialEq for GraphChromosome<T> {
175    fn eq(&self, other: &Self) -> bool {
176        self.nodes == other.nodes
177    }
178}
179
180impl<T: Hash> Hash for GraphChromosome<T> {
181    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
182        for node in self.as_ref() {
183            node.hash(state);
184        }
185    }
186}
187
188impl<T> From<Vec<GraphNode<T>>> for GraphChromosome<T> {
189    fn from(nodes: Vec<GraphNode<T>>) -> Self {
190        GraphChromosome {
191            nodes,
192            store: None,
193            max_nodes: None,
194        }
195    }
196}
197
198impl<T, I> From<(I, NodeStore<T>)> for GraphChromosome<T>
199where
200    I: IntoIterator<Item = GraphNode<T>>,
201{
202    fn from((iter, store): (I, NodeStore<T>)) -> Self {
203        GraphChromosome {
204            nodes: iter.into_iter().collect(),
205            store: Some(store),
206            max_nodes: None,
207        }
208    }
209}
210
211impl<T> FromIterator<GraphNode<T>> for GraphChromosome<T> {
212    fn from_iter<I: IntoIterator<Item = GraphNode<T>>>(iter: I) -> Self {
213        GraphChromosome {
214            nodes: iter.into_iter().collect(),
215            store: None,
216            max_nodes: None,
217        }
218    }
219}
220
221impl<T> IntoIterator for GraphChromosome<T> {
222    type Item = GraphNode<T>;
223    type IntoIter = std::vec::IntoIter<GraphNode<T>>;
224
225    fn into_iter(self) -> Self::IntoIter {
226        self.nodes.into_iter()
227    }
228}
229
230impl<T: Debug> Debug for GraphChromosome<T> {
231    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
232        write!(f, "Graph {{\n")?;
233        for node in self.as_ref() {
234            write!(f, "  {:?},\n", node)?;
235        }
236        write!(f, "}}")
237    }
238}
radiate_gp/collections/graphs/chromosome.rs

radiate_gp/collections/graphs/
chromosome.rs
