Struct Graph 

pub struct Graph<T> { /* private fields */ }

A graph structure that represents a collection of interconnected nodes.

The Graph struct is a fundamental data structure in Radiate’s genetic programming system. Unlike traditional graphs that separate edges and vertices, this graph is a collection of nodes where each node maintains its own connections. Each node has a unique index that corresponds to its position in the internal vector, and connections are represented by these indices.

Type Parameters

• T - The type of value stored in each node. This type must implement Clone, PartialEq, and other traits required by the genetic programming operations.

Structure

A Graph is simply a ‘Vec’ of GraphNode’s.

It’s important to note that this graph differs from a traditional graph in that it is not a collection of edges and vertices. Instead, it is a collection of nodes that are connected to one another. Each node has a unique index that is used to reference it in the graph and must be identical to its position in the ‘Vec’. Each GraphNode has a set of ordered incoming and outgoing connections. These connections are represented by the index of the connected node in the graph. Because of this representation, an edge is not a separate entity, it’s just a node. The ‘NodeType’ enum is used to distinguish different types of nodes. This allows for a more flexible representation of the graph while still maintaining the ability to represent traditional graphs.

By default, a Graph is a directed acyclic graph (DAG). However, it is possible to create cycles in the graph by setting the ‘direction’ field of a GraphNode to Direction::Backward. The Graph struct provides methods for attaching and detaching nodes from one another. It also provides methods for iterating over the nodes in the graph in a pseudo-topological order.

Each node:

• Has a unique index matching its position in the vector
• Maintains sets of incoming and outgoing connections
• Can be of different types (Input, Output, Vertex, Edge) as defined by NodeType
• Can have a direction (Forward or Backward) for handling cycles

Examples

use radiate_gp::{Graph, NodeType, Op};

// Create a simple graph with one input and one output node
let mut graph = Graph::<Op<f32>>::default();
let input_idx = graph.insert(NodeType::Input, Op::var(0));
let output_idx = graph.insert(NodeType::Output, Op::linear());
graph.attach(input_idx, output_idx);

// Create a directed graph with 2 inputs and 2 outputs
let values: Vec<(NodeType, Vec<Op<f32>>)> = vec![
    (NodeType::Input, vec![Op::var(0), Op::var(1)]),
    (NodeType::Output, vec![Op::sigmoid(), Op::tanh()]),
];
let graph = Graph::directed(2, 2, values);

Graph Types

The struct provides several factory methods for creating different types of graphs:

• directed() - Creates a directed acyclic graph (DAG) with specified input and output nodes
• recurrent() - Creates a graph with recurrent connections
• weighted_directed() - Creates a directed graph with weighted edges
• weighted_recurrent() - Creates a recurrent graph with weighted edges

Node Operations

The struct provides methods for manipulating nodes:

• insert() - Adds a new node and returns its index
• push() - Adds a node to the end of the graph
• pop() - Removes and returns the last node
• get() - Returns a reference to a node by index
• get_mut() - Returns a mutable reference to a node by index

Connection Management

The struct provides methods for managing node connections:

• attach() - Creates a connection between two nodes
• detach() - Removes a connection between two nodes
• set_cycles() - Configures nodes to support cyclic connections

Graph Traversal

The struct implements the GraphIterator trait, providing:

• iter_topological() - Traverses the graph in a pseudo-topological order
• iter() - Iterates over all nodes
• iter_mut() - Iterates over all nodes with mutable references

Node Type Queries

The struct provides methods to get nodes by type:

• inputs() - Returns all input nodes
• outputs() - Returns all output nodes
• vertices() - Returns all vertex nodes
• edges() - Returns all edge nodes

Graph Properties

The struct provides methods to query graph properties:

• len() - Returns the number of nodes
• is_empty() - Checks if the graph is empty
• is_valid() - Checks if all nodes in the graph are valid

Implementation Details

The struct implements several traits:

• Clone - Allows cloning of the entire graph
• PartialEq - Enables equality comparison between graphs
• Default - Provides a way to create an empty graph
• Debug - Provides debug formatting
• AsRef<[GraphNode<T>]> - Allows treating the graph as a slice of nodes
• AsMut<[GraphNode<T>]> - Allows treating the graph as a mutable slice of nodes
• Index<usize> - Enables indexing with graph[index]
• IndexMut<usize> - Enables mutable indexing with graph[index]
• IntoIterator - Allows iterating over nodes
• FromIterator<GraphNode<T>> - Allows creating a graph from an iterator of nodes

Genetic Programming

The Graph struct is particularly useful in genetic programming as it can represent:

• Neural networks (using Op<f32> or Op<bool> for values)
• Decision graphs
• Program flow graphs
• Other interconnected structures

It supports genetic operations through the GraphChromosome type, including:

Serialization

When the “serde” feature is enabled, the struct implements Serialize and Deserialize traits.

Performance Considerations

• All nodes (vertices, edges, inputs, outputs) are represented as GraphNode instances
• Node lookups are O(1) due to vector indexing
• Connection operations (attach/detach) are O(log n) due to BTreeSet usage for incoming/outgoing connections
• Graph traversal is O(V + E) where V is the number of nodes and E is the total number of connections
• Memory usage is O(V + E) for storing nodes and their connections
• The distinction between node types (Vertex, Edge, Input, Output) is purely semantic and does not affect the underlying data structure or performance characteristics

Implementations

impl<T: Clone + Default> Graph<T>

pub fn directed( input_size: usize, output_size: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a directed graph with the given input, output sizes and values. The values are used to initialize the nodes in the graph with the given values.

Example

use radiate_gp::*;

let values: Vec<(NodeType, Vec<Op<f32>>)> = vec![
    (NodeType::Input, vec![Op::var(0), Op::var(1), Op::var(2)]),
    (NodeType::Output, vec![Op::sigmoid()]),
];

let graph = Graph::directed(3, 3, values);

assert_eq!(graph.len(), 6);

The graph will have 6 nodes, 3 input nodes and 3 output nodes where each input node is connected to each output node. Such as:

[0, 1, 2] -> [3, 4, 5]

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.
• values - The values to initialize the nodes with.

Returns

A new directed graph.

pub fn recurrent( input_size: usize, output_size: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a recurrent graph with the given input and output sizes. The values are used to initialize the nodes in the graph with the given values. The graph will have a recurrent connection from each hidden vertex to itself. The graph will have a one-to-one connection from each input node to each hidden vertex. The graph will have an all-to-all connection from each hidden vertex to each output node.

Example

use radiate_gp::*;

let values: Vec<(NodeType, Vec<Op<f32>>)> = vec![
  (NodeType::Input, vec![Op::var(0), Op::var(1), Op::var(2)]),
  (NodeType::Vertex, vec![Op::linear()]),
  (NodeType::Output, vec![Op::sigmoid()]),
];

let graph = Graph::recurrent(3, 3, values);

assert_eq!(graph.len(), 9);

The graph will have 9 nodes, 3 input nodes, 3 hidden nodes with recurrent connections to themselves, and 3 output nodes. Such as:

[0, 1, 2] -> [3, 4, 5]
    [3, 4, 5] -> [6, 7, 8]
        [6, 7, 8] -> [3, 4, 5]
[3, 4, 5] -> [9, 10, 11]

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.
• values - The values to initialize the nodes with.

Returns

A new recurrent graph.

pub fn weighted_directed( input_size: usize, output_size: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a weighted directed graph with the given input and output sizes.

This will result in the same graph as Graph::directed but with an additional edge connecting each input node to each output node.

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.

Returns

A new weighted directed graph.

pub fn weighted_recurrent( input_size: usize, output_size: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a weighted recurrent graph with the given input and output sizes. This will result in the same graph as Graph::recurrent but with an additional edge connecting each hidden vertex to each output node.

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.

Returns

A new weighted recurrent graph.

pub fn lstm( input_size: usize, output_size: usize, store: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a Long Short-Term Memory (LSTM) graph with the given input and output sizes. The graph will have the following structure:

• Input nodes connected to forget, input, candidate, and output gates.
• Hidden state connected to forget, input, candidate, and output gates.
• Forget gate connected to cell state.
• Input gate connected to candidate and cell state.
• Candidate connected to cell state.
• Cell state connected to hidden state.
• Output gate connected to hidden state.
• Hidden state connected to output nodes.

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.
• store - The node store.

Returns

A new LSTM graph.

pub fn gru( input_size: usize, output_size: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a Gated Recurrent Unit (GRU) graph with the given input and output sizes. The graph will have the following structure:

• Input nodes connected to reset, update, and candidate gates.
• Hidden state connected to reset, update, and candidate gates.
• Reset gate connected to hidden state.
• Update gate connected to blend and gate flip.
• Candidate connected to blend.
• Blend connected to hidden state.
• Gate flip connected to hidden state.
• Hidden state connected to output nodes.

Arguments

• input_size - The number of input nodes.
• output_size - The number of output nodes.
• store - The node store.

Returns

A new GRU graph.

pub fn mesh( input_size: usize, output_size: usize, width: usize, height: usize, values: impl Into<NodeStore<T>>, ) -> Graph<T>

Creates a 2D mesh graph with bidirectional connections between neighboring nodes. The graph will have the following structure:

• Input nodes connected to the first row of mesh nodes.
• Each mesh node connected to its neighbors (up, down, left, right).
• Last row of mesh nodes connected to output nodes.

Arguments

• width - The number of nodes in the horizontal dimension.
• height - The number of nodes in the vertical dimension.
• values - The values to initialize the nodes with.

Returns

A new 2D mesh graph.

impl<T> Graph<T>

pub fn new(nodes: Vec<GraphNode<T>>) -> Self

Create a new ‘Graph’ from a ‘Vec’ of GraphNodes.

Arguments

• nodes: A ‘Vec’ of GraphNodes.

pub fn take_nodes(&mut self) -> Vec<GraphNode<T>>

pub fn push(&mut self, node: impl Into<GraphNode<T>>)

pub fn insert(&mut self, node_type: NodeType, val: T) -> usize

pub fn pop(&mut self) -> Option<GraphNode<T>>

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn get_mut(&mut self, index: usize) -> Option<&mut GraphNode<T>>

pub fn get(&self, index: usize) -> Option<&GraphNode<T>>

pub fn iter(&self) -> impl Iterator<Item = &GraphNode<T>>

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut GraphNode<T>>

pub fn inputs(&self) -> impl Iterator<Item = &GraphNode<T>>

pub fn outputs(&self) -> impl Iterator<Item = &GraphNode<T>>

pub fn vertices(&self) -> impl Iterator<Item = &GraphNode<T>>

pub fn edges(&self) -> impl Iterator<Item = &GraphNode<T>>

pub fn attach(&mut self, incoming: usize, outgoing: usize) -> &mut Self

Attach and detach nodes from one another. This is the primary way to modify the graph. Note that this method does not check if the nodes are already connected. This is because the connections are represented by ’BTreeSet’s which do not allow duplicates. Its also important to note that the ‘incoming’ and ‘outgoing’ indices are the indices of the nodes in the graph, not the indices of the connections in the ‘incoming’ and ‘outgoing’ ’BTreeSet’s. We must also remember that the GraphNode cares about the ‘Arity’ of the ‘Operation’ it contains, so if we add a connection that would violate the ‘Arity’ of the ‘Operation’, the connection will result in a GraphNode that is not ‘Valid’.

Attaches the node at the ‘incoming’ index to the node at the ‘outgoing’ index. This means that the node at the ‘incoming’ index will have an outgoing connection to the node at the ‘outgoing’ index, and the node at the ‘outgoing’ index will have an incoming connection from the node at the ‘incoming’ index.

Arguments

• incoming: The index of the node that will have an outgoing connection to the node at the ‘outgoing’ index.
• outgoing: The index of the node that will have an incoming connection from the node at the ‘incoming’ index.

pub fn detach(&mut self, incoming: usize, outgoing: usize) -> &mut Self

Detaches the node at the ‘incoming’ index from the node at the ‘outgoing’ index. This means that the node at the ‘incoming’ index will no longer have an outgoing connection to the node at the ‘outgoing’ index, and the node at the ‘outgoing’ index will no longer have an incoming connection from the node at the ‘incoming’ index.

Arguments

• incoming: The index of the node that will no longer have an outgoing connection to the node at the ‘outgoing’ index.
• outgoing: The index of the node that will no longer have an incoming connection from the node at the ‘incoming’ index.

pub fn try_modify<F>(&mut self, mutation: F) -> TransactionResult<T>

where F: FnOnce(GraphTransaction<'_, T>) -> TransactionResult<T>, T: Clone,

tries to modify the graph using a GraphTransaction. If the transaction is successful, we return true and do nothing. If the transaction is not successful, we roll back the transaction by undoing all the changes made by the transaction and return false.

Arguments

• mutation: A closure that takes a mutable reference to a GraphTransaction and returns a ‘bool’.

pub fn set_cycles(&mut self, indecies: Vec<usize>)

Given a list of node indices, this function will set the ‘direction’ field of the nodes at those indices to Direction::Backward if they are part of a cycle. If they are not part of a cycle, the ‘direction’ field will be set to Direction::Forward. If no indices are provided, the function will set the ‘direction’ field of all nodes in the graph.

pub fn get_cycles(&self, from: usize) -> HashSet<usize>

Get the cycles in the graph that include the node at the specified index.

Arguments

• index: The index of the node to get the cycles for.

Trait Implementations

impl<T> AsMut<[GraphNode<T>]> for Graph<T>

fn as_mut(&mut self) -> &mut [GraphNode<T>]

Converts this type into a mutable reference of the (usually inferred) input type.

impl<T, V> AsRef<Graph<T>> for StatefulGraph<T, V>

fn as_ref(&self) -> &Graph<T>

Converts this type into a shared reference of the (usually inferred) input type.

impl<T> AsRef<[GraphNode<T>]> for Graph<T>

fn as_ref(&self) -> &[GraphNode<T>]

Converts this type into a shared reference of the (usually inferred) input type.

impl<F> BatchFitnessFunction<Graph<Op<F>>, F> for Regression<F>

where F: OpFloat + Into<Score>,

fn evaluate(&self, inputs: Vec<Graph<Op<F>>>) -> Vec<F>

impl<T: Clone> Clone for Graph<T>

fn clone(&self) -> Graph<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Codec<GraphChromosome<T>, Graph<T>> for GraphCodec<T>

where T: Clone + PartialEq + Default,

fn encode(&self) -> Genotype<GraphChromosome<T>>

fn decode(&self, genotype: &Genotype<GraphChromosome<T>>) -> Graph<T>

impl<T: Debug> Debug for Graph<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for Graph<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: OpFloat> Eval<Graph<Op<T>>, Option<AccuracyResult>> for Accuracy<'_, T>

fn eval(&self, graph: &Graph<Op<T>>) -> Option<AccuracyResult>

impl<T, V> Eval<[Vec<V>], Vec<Vec<V>>> for Graph<T>

where T: Eval<[V], V>, V: Copy + Default,

fn eval(&self, input: &[Vec<V>]) -> Vec<Vec<V>>

Evaluates the Graph with the given input Vec<Vec<T>>. Returns the output of the Graph as Vec<Vec<T>>. This is intended to be used when evaluating a batch of inputs.

Arguments

• input - A Vec<Vec<T>> to evaluate the Graph with.

Returns

• A Vec<Vec<T>> which is the output of the Graph.

impl<T, V> EvalInto<[Vec<V>], Vec<Vec<V>>> for Graph<T>

where T: Eval<[V], V>, V: Copy + Default,

fn eval_into(&self, input: &[Vec<V>], buffer: &mut Vec<Vec<V>>)

Evaluates the Graph with the given input Vec<Vec<T>>. Returns the output of the Graph as Vec<Vec<T>>.

Arguments

• input - A Vec<Vec<T>> to evaluate the Graph with.

Returns

• A Vec<Vec<T>> which is the output of the Graph.

impl<F> FitnessFunction<Graph<Op<F>>, F> for Regression<F>

where F: OpFloat + Into<Score>,

fn evaluate(&self, input: Graph<Op<F>>) -> F

impl<'a, T, V> From<&'a Graph<T>> for GraphEvaluator<'a, T, V>

where T: Eval<[V], V>, V: Default + Clone,

fn from(graph: &'a Graph<T>) -> Self

Converts to this type from the input type.

impl<T, V> From<Graph<T>> for StatefulGraph<T, V>

where T: Eval<[V], V>,

fn from(inner: Graph<T>) -> Self

Converts to this type from the input type.

impl<T> FromIterator<GraphNode<T>> for Graph<T>

fn from_iter<I: IntoIterator<Item = GraphNode<T>>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Hash> Hash for Graph<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for Graph<T>

type Output = GraphNode<T>

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for Graph<T>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<T> IntoIterator for Graph<T>

type Item = GraphNode<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<GraphNode<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for Graph<T>

fn eq(&self, other: &Graph<T>) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<T: PartialEq> StructuralPartialEq for Graph<T>

impl<T> ToDot for Graph<T>

where T: Debug,

fn to_dot(&self) -> String

impl<T> Valid for Graph<T>

fn is_valid(&self) -> bool