use fastrand::Rng;
use log::debug;
use serde::{Deserialize, Serialize};
use crate::utils::error::TopologyError;
use crate::graph::node::{Activation, Node, NodeKind};
pub use crate::graph::node::CombineOp;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct KindCounts {
pub input: usize,
pub hidden: usize,
pub output: usize,
}
#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
pub struct TopologyOptions {
pub seed: usize,
pub min_hidden_num_nodes: usize,
pub max_hidden_num_nodes: usize,
pub min_hidden_inputs_per_node: usize,
pub max_hidden_inputs_per_node: usize,
pub min_hidden_outputs_per_node: usize,
pub max_hidden_outputs_per_node: usize,
pub input_dim: usize,
pub hidden_dim: usize,
pub output_dim: usize,
#[serde(default)]
pub dropout_prob: f32,
}
impl PartialEq for TopologyOptions {
fn eq(&self, other: &Self) -> bool {
self.seed == other.seed
&& self.min_hidden_num_nodes == other.min_hidden_num_nodes
&& self.max_hidden_num_nodes == other.max_hidden_num_nodes
&& self.min_hidden_inputs_per_node == other.min_hidden_inputs_per_node
&& self.max_hidden_inputs_per_node == other.max_hidden_inputs_per_node
&& self.min_hidden_outputs_per_node == other.min_hidden_outputs_per_node
&& self.max_hidden_outputs_per_node == other.max_hidden_outputs_per_node
&& self.input_dim == other.input_dim
&& self.hidden_dim == other.hidden_dim
&& self.output_dim == other.output_dim
&& self.dropout_prob.to_bits() == other.dropout_prob.to_bits()
}
}
impl Eq for TopologyOptions {}
impl std::hash::Hash for TopologyOptions {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.seed.hash(state);
self.min_hidden_num_nodes.hash(state);
self.max_hidden_num_nodes.hash(state);
self.min_hidden_inputs_per_node.hash(state);
self.max_hidden_inputs_per_node.hash(state);
self.min_hidden_outputs_per_node.hash(state);
self.max_hidden_outputs_per_node.hash(state);
self.input_dim.hash(state);
self.hidden_dim.hash(state);
self.output_dim.hash(state);
self.dropout_prob.to_bits().hash(state);
}
}
impl Default for TopologyOptions {
fn default() -> Self {
TopologyOptions {
seed: 55,
min_hidden_num_nodes: 2,
max_hidden_num_nodes: 5,
min_hidden_inputs_per_node: 2,
max_hidden_inputs_per_node: 5,
min_hidden_outputs_per_node: 2,
max_hidden_outputs_per_node: 5,
input_dim: 1,
hidden_dim: 8,
output_dim: 1,
dropout_prob: 0.0,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Port {
pub node: usize, pub index: usize, }
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Connection {
pub from: Port,
pub to: Port,
}
impl Connection {
pub fn from_label(&self) -> String {
format!("n{}_o{}", self.from.node, self.from.index)
}
pub fn to_label(&self) -> String {
format!("n{}_i{}", self.to.node, self.to.index)
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Topology {
pub id: usize,
pub nodes: Vec<Node>,
pub options: TopologyOptions,
pub(crate) graph_inputs: Vec<String>,
pub(crate) graph_outputs: Vec<String>,
pub connections: Vec<Connection>,
pub(crate) rng: Rng,
}
impl Topology {
pub fn new(id: usize, options: Option<TopologyOptions>) -> Topology {
let opts = options.unwrap_or_default();
Topology {
id,
nodes: Vec::new(),
options: opts,
graph_inputs: Vec::new(),
graph_outputs: Vec::new(),
connections: Vec::new(),
rng: Rng::with_seed(opts.seed as u64),
}
}
pub fn create_random_hidden_node(&mut self) {
let num_inputs = self.rng.usize(
self.options.min_hidden_inputs_per_node..=self.options.max_hidden_inputs_per_node,
);
let num_outputs = self.rng.usize(
self.options.min_hidden_outputs_per_node..=self.options.max_hidden_outputs_per_node,
);
let node = Node::new_hidden(self.nodes.len(), num_inputs, num_outputs);
self.nodes.push(node);
}
pub fn create_random_hidden_nodes(&mut self, num_nodes: usize) {
for _ in 0..num_nodes {
self.create_random_hidden_node();
}
}
pub fn renumber_ids(&mut self) {
for (i, node) in self.nodes.iter_mut().enumerate() {
node.id = i;
}
}
pub fn refresh_labels(&mut self) {
self.graph_inputs.clear();
self.graph_outputs.clear();
for node in &self.nodes {
for i in 0..node.num_inputs {
self.graph_inputs.push(format!("n{}_i{}", node.id, i));
}
for i in 0..node.num_outputs {
self.graph_outputs.push(format!("n{}_o{}", node.id, i));
}
}
}
pub fn finalize(&mut self) {
self.connections.clear();
self.ensure_scaffold();
self.resolve_dims();
self.refresh_labels();
self.wire_ports();
self.set_input_fanout();
self.rewire_orphaned_inputs();
self.dedup_input_connections();
self.rewire_orphaned_outputs();
self.trim_orphaned_ports();
if let Err(e) = self.validate() {
panic!("finalize validation failed: {e}\n{self:?}");
}
}
fn resolve_dims(&mut self) {
let eff = self.effective_hidden_dim();
for node in &mut self.nodes {
if node.hidden_dim.is_none() {
node.hidden_dim = Some(match node.kind {
NodeKind::Output => self.options.output_dim,
_ => eff,
});
}
}
}
fn wire_ports(&mut self) {
let mut input_ports: Vec<Port> = Vec::new();
let mut output_ports: Vec<Port> = Vec::new();
for node in &self.nodes {
for i in 0..node.num_inputs {
input_ports.push(Port {
node: node.id,
index: i,
});
}
for i in 0..node.num_outputs {
output_ports.push(Port {
node: node.id,
index: i,
});
}
}
self.rng.shuffle(&mut input_ports);
self.rng.shuffle(&mut output_ports);
let mut used = vec![false; output_ports.len()];
for target in input_ports {
let already_used: Vec<usize> = self
.connections
.iter()
.filter(|c| c.to.node == target.node)
.map(|c| c.from.node)
.collect();
let source = output_ports
.iter()
.enumerate()
.find(|(i, p)| !used[*i] && p.node < target.node && !already_used.contains(&p.node))
.map(|(i, p)| (i, *p));
if let Some((i, source)) = source {
used[i] = true;
self.connections.push(Connection {
from: source,
to: target,
});
}
}
}
fn set_input_fanout(&mut self) {
let n_hidden = self
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Hidden)
.count();
let input_node = self
.nodes
.iter_mut()
.find(|n| n.kind == NodeKind::Input)
.unwrap();
input_node.num_outputs = input_node.num_outputs.max(n_hidden).max(1);
}
fn rewire_orphaned_inputs(&mut self) {
let input_id = self
.nodes
.iter()
.find(|n| n.kind == NodeKind::Input)
.unwrap()
.id;
let n_ports = self
.nodes
.iter()
.find(|n| n.id == input_id)
.unwrap()
.num_outputs;
let mut output_idx = 0usize;
for node in &self.nodes {
for i in 0..node.num_inputs {
let port = Port {
node: node.id,
index: i,
};
if !self.connections.iter().any(|c| c.to == port) {
self.connections.push(Connection {
from: Port {
node: input_id,
index: output_idx % n_ports,
},
to: port,
});
output_idx += 1;
}
}
}
}
fn dedup_input_connections(&mut self) {
let input_id = self
.nodes
.iter()
.find(|n| n.kind == NodeKind::Input)
.map(|n| n.id);
if let Some(id) = input_id {
let mut seen: Vec<(usize, usize)> = Vec::new();
self.connections.retain(|c| {
if c.from.node != id {
return true;
}
let key = (c.from.index, c.to.node);
if seen.contains(&key) {
false
} else {
seen.push(key);
true
}
});
}
}
pub fn connection_labels(&self) -> Vec<(String, String)> {
self.connections
.iter()
.map(|c| (c.from_label(), c.to_label()))
.collect()
}
pub fn validate(&self) -> Result<(), TopologyError> {
if self.options.input_dim == 0
|| self.options.hidden_dim == 0
|| self.options.output_dim == 0
{
return Err(TopologyError::InvalidOptions(
"input_dim, hidden_dim, and output_dim must be > 0".to_string(),
));
}
if self.options.min_hidden_inputs_per_node > self.options.max_hidden_inputs_per_node
|| self.options.min_hidden_outputs_per_node > self.options.max_hidden_outputs_per_node
{
return Err(TopologyError::InvalidOptions(
"min/max inputs or outputs per node ranges are inverted".to_string(),
));
}
if self.nodes.is_empty() {
return Err(TopologyError::EmptyTopology);
}
for (i, node) in self.nodes.iter().enumerate() {
if node.id != i {
return Err(TopologyError::NonContiguousNodeIds);
}
if node.hidden_dim == Some(0) {
return Err(TopologyError::InvalidOptions(format!(
"node n{i} has hidden_dim 0"
)));
}
}
let n_outputs = self
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Output)
.count();
if n_outputs > 1 {
return Err(TopologyError::InvalidOptions(
"multiple Output nodes are not supported (use exactly one)".to_string(),
));
}
let mut used_sources: Vec<Port> = Vec::new();
for conn in &self.connections {
if conn.from.node >= conn.to.node {
return Err(TopologyError::BackwardConnection(conn.clone()));
}
if conn.from.node >= self.nodes.len() || conn.to.node >= self.nodes.len() {
return Err(TopologyError::UnknownNode(conn.from.node));
}
let src = &self.nodes[conn.from.node];
let dst = &self.nodes[conn.to.node];
if conn.from.index >= src.num_outputs {
return Err(TopologyError::PortOutOfBounds {
port: conn.from,
num_ports: src.num_outputs,
});
}
if conn.to.index >= dst.num_inputs {
return Err(TopologyError::PortOutOfBounds {
port: conn.to,
num_ports: dst.num_inputs,
});
}
let is_input_node = self.nodes[conn.from.node].kind == NodeKind::Input;
if !is_input_node && used_sources.contains(&conn.from) {
return Err(TopologyError::DoubleUsedOutput(conn.from));
}
used_sources.push(conn.from);
}
Ok(())
}
pub fn orphan_counts(&self) -> (usize, usize) {
node_orphan_counts(&self.nodes, &self.connections, self.nodes.len() - 1)
}
fn out_dim_of(&self, node: &Node) -> usize {
node.hidden_dim.unwrap_or(self.options.hidden_dim)
}
fn effective_hidden_dim(&self) -> usize {
self.nodes
.iter()
.map(|n| self.out_dim_of(n))
.max()
.unwrap_or(self.options.hidden_dim)
}
pub fn node_dims(&self) -> Vec<(usize, usize)> {
let num_inputs: Vec<usize> = self.nodes.iter().map(|n| n.num_inputs).collect();
let sources = build_node_sources(&self.connections, &num_inputs);
self.nodes
.iter()
.map(|node| {
let in_dim = if node.kind == NodeKind::Input {
self.options.input_dim
} else {
sources[node.id]
.iter()
.flatten()
.map(|p| self.out_dim_of(&self.nodes[p.node]))
.max()
.unwrap_or_else(|| self.effective_hidden_dim())
};
(in_dim, self.out_dim_of(node))
})
.collect()
}
pub fn orphan_ports(&self, node: usize) -> (Vec<usize>, Vec<usize>) {
let mut ins = Vec::new();
let mut outs = Vec::new();
for i in 0..self.nodes[node].num_inputs {
let port = Port { node, index: i };
if !self.connections.iter().any(|c| c.to == port) {
ins.push(i);
}
}
for o in 0..self.nodes[node].num_outputs {
let port = Port { node, index: o };
if !self.connections.iter().any(|c| c.from == port) {
outs.push(o);
}
}
(ins, outs)
}
pub fn degrees(&self) -> Vec<(usize, usize)> {
node_degrees(&self.nodes, &self.connections)
}
pub fn depths(&self) -> Vec<usize> {
node_depths(&self.nodes, &self.connections)
}
pub fn param_estimate(&self) -> usize {
let dims = self.node_dims();
let mut total = 0;
for &(in_dim, out_dim) in &dims {
total += in_dim * out_dim + out_dim;
}
total
}
pub fn kind_counts(&self) -> KindCounts {
node_kind_counts(&self.nodes)
}
pub fn activation_counts(&self) -> Vec<(Activation, usize)> {
node_activation_counts(&self.nodes)
}
pub fn ensure_scaffold(&mut self) {
if !self.nodes.iter().any(|n| n.kind == NodeKind::Input) {
self.nodes.insert(0, Node::new_input(0, 1));
for node in self.nodes.iter_mut().skip(1) {
node.id += 1;
}
for conn in &mut self.connections {
conn.from.node += 1;
conn.to.node += 1;
}
}
let has_output = self.nodes.iter().any(|n| n.kind == NodeKind::Output);
if !has_output {
let mut out = Node::new_output(self.nodes.len(), 1, 1);
out.hidden_dim = Some(self.options.output_dim);
self.nodes.push(out);
}
}
pub fn rewire_orphaned_outputs(&mut self) -> usize {
let output_node = self.nodes.len() - 1;
let mut orphans: Vec<Port> = Vec::new();
for node in &self.nodes {
if node.id == output_node {
continue;
}
for o in 0..node.num_outputs {
let port = Port {
node: node.id,
index: o,
};
if !self.connections.iter().any(|c| c.from == port) {
orphans.push(port);
}
}
}
let mut added = 0usize;
for src in orphans {
let targets: Vec<usize> = self
.nodes
.iter()
.filter(|n| {
n.id > src.node
&& n.num_inputs > 0
&& !self
.connections
.iter()
.any(|c| c.from.node == src.node && c.to.node == n.id)
})
.map(|n| n.id)
.collect();
if targets.is_empty() {
continue;
}
let target = targets[self.rng.usize(0..targets.len())];
let port = self.rng.usize(0..self.nodes[target].num_inputs);
self.connections.push(Connection {
from: src,
to: Port {
node: target,
index: port,
},
});
added += 1;
}
added
}
fn trim_orphaned_ports(&mut self) {
let output_id = self
.nodes
.iter()
.find(|n| n.kind == NodeKind::Output)
.map(|n| n.id);
let out_remap: Vec<Vec<usize>> = self
.nodes
.iter()
.map(|n| {
let mut used: Vec<bool> = vec![false; n.num_outputs];
for c in &self.connections {
if c.from.node == n.id && c.from.index < used.len() {
used[c.from.index] = true;
}
}
let mut map = vec![0usize; n.num_outputs];
let mut next = 0;
for i in 0..n.num_outputs {
if used[i] {
map[i] = next;
next += 1;
} else {
map[i] = usize::MAX; }
}
map
})
.collect();
let in_remap: Vec<Vec<usize>> = self
.nodes
.iter()
.map(|n| {
let mut used: Vec<bool> = vec![false; n.num_inputs];
for c in &self.connections {
if c.to.node == n.id && c.to.index < used.len() {
used[c.to.index] = true;
}
}
let mut map = vec![0usize; n.num_inputs];
let mut next = 0;
for i in 0..n.num_inputs {
if used[i] {
map[i] = next;
next += 1;
} else {
map[i] = usize::MAX;
}
}
map
})
.collect();
self.connections.retain(|c| {
let from_map = &out_remap[c.from.node];
let to_map = &in_remap[c.to.node];
c.from.index < from_map.len()
&& c.to.index < to_map.len()
&& from_map[c.from.index] != usize::MAX
&& to_map[c.to.index] != usize::MAX
});
for c in &mut self.connections {
c.from.index = out_remap[c.from.node][c.from.index];
c.to.index = in_remap[c.to.node][c.to.index];
}
for (i, node) in self.nodes.iter_mut().enumerate() {
if Some(node.id) != output_id {
node.num_outputs = out_remap[i]
.iter()
.filter(|&&v| v != usize::MAX)
.count()
.max(1);
}
let connected_in = in_remap[i].iter().filter(|&&v| v != usize::MAX).count();
if connected_in > 0 {
node.num_inputs = connected_in;
}
}
}
pub fn to_json(&self) -> Result<String, serde_json::Error> {
serde_json::to_string_pretty(self)
}
pub fn from_json(s: &str) -> Result<Topology, serde_json::Error> {
serde_json::from_str(s)
}
fn find_matching_node(
a: &Topology,
b: &Topology,
rng: &mut Rng,
) -> Option<(usize, usize)> {
let ha: Vec<usize> = a
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
let hb: Vec<usize> = b
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
let mut matches: Vec<(usize, usize)> = Vec::new();
for (ai, &a_idx) in ha.iter().enumerate() {
let an = &a.nodes[a_idx];
for (bi, &b_idx) in hb.iter().enumerate() {
let bn = &b.nodes[b_idx];
if an.num_inputs == bn.num_inputs && an.num_outputs == bn.num_outputs {
matches.push((ai, bi));
}
}
}
if matches.is_empty() {
None
} else {
Some(matches[rng.usize(0..matches.len())])
}
}
pub fn cx_one_point(a: &mut Topology, b: &mut Topology, rng: &mut Rng) -> bool {
let ha: Vec<usize> = a
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
let hb: Vec<usize> = b
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
if ha.is_empty() || hb.is_empty() {
return false;
}
if let Some((pivot_a, pivot_b)) = Self::find_matching_node(a, b, rng) {
let swap_a = &ha[pivot_a..];
let swap_b = &hb[pivot_b..];
let len = swap_a.len().min(swap_b.len());
for k in 0..len {
let tmp = a.nodes[swap_a[k]].clone();
a.nodes[swap_a[k]] = b.nodes[swap_b[k]].clone();
b.nodes[swap_b[k]] = tmp;
}
a.renumber_ids();
a.finalize();
b.renumber_ids();
b.finalize();
debug!("cx_one_point: pivot hidden[{}] <-> hidden[{}], swapped {} nodes", pivot_a, pivot_b, len);
return true;
}
debug!("cx_one_point: no matching node found, skipping");
false
}
pub fn cx_uniform(a: &mut Topology, b: &mut Topology, swap_prob: f32, rng: &mut Rng) -> bool {
let ha: Vec<usize> = a
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
let hb: Vec<usize> = b
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.kind == NodeKind::Hidden)
.map(|(i, _)| i)
.collect();
if ha.len() != hb.len() || ha.is_empty() {
debug!("cx_uniform: hidden node count mismatch ({} vs {}), skipping", ha.len(), hb.len());
return false;
}
let mut swaps = 0usize;
for (&ai, &bi) in ha.iter().zip(hb.iter()) {
if rng.f32() < swap_prob {
std::mem::swap(&mut a.nodes[ai], &mut b.nodes[bi]);
swaps += 1;
}
}
if swaps > 0 {
a.renumber_ids();
a.finalize();
b.renumber_ids();
b.finalize();
debug!("cx_uniform: swapped {swaps}/{} hidden nodes", ha.len());
}
swaps > 0
}
}
use crate::utils::graph_utils::{
build_node_sources, node_activation_counts, node_degrees, node_depths, node_kind_counts,
node_orphan_counts,
};
#[cfg(test)]
pub(crate) mod test_strategies {
use super::*;
use proptest::prelude::*;
pub(crate) fn topology_options_strategy() -> impl Strategy<Value = TopologyOptions> {
(
0usize..10_000, 1usize..4, 1usize..4, 1usize..8, 1usize..8, 1usize..8, )
.prop_map(
|(seed, min_in, min_out, input_dim, hidden_dim, output_dim)| TopologyOptions {
seed,
min_hidden_num_nodes: 2,
max_hidden_num_nodes: 6,
min_hidden_inputs_per_node: min_in,
max_hidden_inputs_per_node: min_in + 3,
min_hidden_outputs_per_node: min_out,
max_hidden_outputs_per_node: min_out + 3,
input_dim,
hidden_dim,
output_dim,
dropout_prob: 0.0,
},
)
}
pub(crate) fn topology_strategy() -> impl Strategy<Value = Topology> {
(topology_options_strategy(), 0usize..6).prop_map(|(opts, n_hidden)| {
let mut graph = Topology::new(0, Some(opts));
graph.nodes.push(Node::new_input(0, 2));
for i in 0..n_hidden {
let span_in = opts.max_hidden_inputs_per_node - opts.min_hidden_inputs_per_node + 1;
let span_out =
opts.max_hidden_outputs_per_node - opts.min_hidden_outputs_per_node + 1;
let ins = opts.min_hidden_inputs_per_node + (i * 7) % span_in;
let outs = opts.min_hidden_outputs_per_node + (i * 3) % span_out;
graph.nodes.push(Node::new_hidden(i + 1, ins, outs));
}
graph.nodes.push(Node::new_output(n_hidden + 1, 1, 1));
graph.refresh_labels();
graph.finalize();
graph
})
}
}
#[cfg(test)]
mod tests {
use super::test_strategies::*;
use super::*;
use crate::graph::network::Network;
use flodl::nn::Module;
use flodl::{DType, Device, Tensor, TensorOptions, Variable};
use proptest::prelude::*;
fn cpu_opts() -> TensorOptions {
TensorOptions {
dtype: DType::Float32,
device: Device::CPU,
}
}
fn rand_input(batch: i64, input_dim: usize) -> Variable {
Variable::new(
Tensor::randn(&[batch, input_dim as i64], cpu_opts()).unwrap(),
false,
)
}
#[test]
fn test_new_without_options() {
let graph = Topology::new(1, None);
assert_eq!(graph.nodes.len(), 0);
assert_eq!(graph.options.min_hidden_num_nodes, 2);
assert_eq!(graph.options.max_hidden_num_nodes, 5);
}
#[test]
fn test_new_with_options() {
let opts = TopologyOptions {
seed: 123,
min_hidden_num_nodes: 3,
max_hidden_num_nodes: 10,
min_hidden_inputs_per_node: 1,
max_hidden_inputs_per_node: 5,
min_hidden_outputs_per_node: 1,
max_hidden_outputs_per_node: 5,
input_dim: 4,
hidden_dim: 16,
output_dim: 10,
dropout_prob: 0.0,
};
let graph = Topology::new(1, Some(opts));
assert_eq!(graph.nodes.len(), 0);
assert_eq!(graph.options.min_hidden_num_nodes, 3);
assert_eq!(graph.options.max_hidden_num_nodes, 10);
assert_eq!(graph.options.input_dim, 4);
assert_eq!(graph.options.hidden_dim, 16);
assert_eq!(graph.options.output_dim, 10);
}
#[test]
fn test_create_random_hidden_node() {
let mut graph = Topology::new(1, None);
graph.create_random_hidden_node();
assert_eq!(graph.nodes.len(), 1);
}
#[test]
fn test_refresh_labels() {
let mut graph = Topology::new(1, None);
graph.create_random_hidden_node();
graph.create_random_hidden_node();
graph.create_random_hidden_node();
graph.refresh_labels();
let total_inputs: usize = graph.nodes.iter().map(|n| n.num_inputs).sum();
let total_outputs: usize = graph.nodes.iter().map(|n| n.num_outputs).sum();
assert_eq!(graph.graph_inputs.len(), total_inputs);
assert_eq!(graph.graph_outputs.len(), total_outputs);
}
#[test]
fn test_refresh_labels_mints_port_labels() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 3, 2));
graph.refresh_labels();
assert_eq!(graph.graph_inputs, vec!["n1_i0", "n1_i1", "n1_i2"]);
assert_eq!(
graph.graph_outputs,
vec!["n0_o0", "n0_o1", "n1_o0", "n1_o1"]
);
}
#[test]
fn test_finalize() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 3, 2));
graph.nodes.push(Node::new_hidden(2, 2, 1));
graph.finalize();
let mut seen_from: Vec<Port> = Vec::new();
let input_id = graph
.nodes
.iter()
.find(|n| n.kind == NodeKind::Input)
.unwrap()
.id;
for conn in &graph.connections {
assert!(
conn.from.node < conn.to.node,
"connection must go strictly forward: {conn}"
);
if conn.from.node != input_id {
assert!(
!seen_from.contains(&conn.from),
"output port {} used twice",
conn.from_label()
);
}
seen_from.push(conn.from);
}
assert!(!graph.connections.is_empty());
assert!(!graph.connections.is_empty());
assert_eq!(graph.connections.len(), graph.connection_labels().len());
}
#[test]
fn test_validate_ok_on_generated_graph() {
let mut graph = Topology::new(1, None);
graph.create_random_hidden_nodes(5);
graph.refresh_labels();
graph.finalize();
assert_eq!(graph.validate(), Ok(()));
}
#[test]
fn test_validate_rejects_empty_graph() {
let graph = Topology::new(1, None);
assert_eq!(graph.validate(), Err(TopologyError::EmptyTopology));
}
#[test]
fn test_validate_rejects_non_contiguous_ids() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(2, 1, 1)); assert_eq!(graph.validate(), Err(TopologyError::NonContiguousNodeIds));
}
#[test]
fn test_validate_rejects_backward_connection() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 1));
graph.nodes.push(Node::new_hidden(1, 1, 1));
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 0, index: 0 },
});
assert!(matches!(
graph.validate(),
Err(TopologyError::BackwardConnection(_))
));
}
#[test]
fn test_validate_rejects_unknown_node() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 1));
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 0 },
});
assert!(matches!(
graph.validate(),
Err(TopologyError::UnknownNode(_))
));
}
#[test]
fn test_validate_rejects_port_out_of_bounds() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 1));
graph.nodes.push(Node::new_hidden(1, 1, 1));
graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 3 }, });
assert!(matches!(
graph.validate(),
Err(TopologyError::PortOutOfBounds { .. })
));
}
#[test]
fn test_validate_allows_multi_wired_input_port() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 1, 1));
graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 0 },
});
graph.connections.push(Connection {
from: Port { node: 0, index: 1 },
to: Port { node: 1, index: 0 }, });
assert_eq!(graph.validate(), Ok(()));
let module = Network::build(&graph, Device::CPU).unwrap();
let batch = 2i64;
let input = rand_input(batch, graph.options.input_dim);
let output = module.forward(&input).unwrap();
assert_eq!(output.shape(), &[batch, graph.options.hidden_dim as i64]);
}
#[test]
fn test_validate_rejects_double_used_output() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 2, 1));
graph.nodes.push(Node::new_hidden(2, 1, 1));
graph.nodes.push(Node::new_hidden(3, 1, 1));
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 0 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 0 }, to: Port { node: 3, index: 0 },
});
assert!(matches!(
graph.validate(),
Err(TopologyError::DoubleUsedOutput(_))
));
}
#[test]
fn test_orphan_counts() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 3, 2));
graph.nodes.push(Node::new_hidden(2, 2, 1));
graph.nodes.push(Node::new_output(3, 1, 1));
graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 2 },
});
graph.connections.push(Connection {
from: Port { node: 0, index: 1 },
to: Port { node: 2, index: 0 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 1 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 1 },
to: Port { node: 3, index: 0 },
});
assert_eq!(graph.orphan_counts(), (2, 1));
}
#[test]
fn test_derived_diagnostics() {
let mut g = Topology::new(1, None);
g.nodes.push(Node::new_input(0, 2));
g.nodes.push(Node::new_hidden(1, 3, 2));
g.nodes.push(Node::new_hidden(2, 2, 1));
g.nodes.push(Node::new_output(3, 1, 1));
g.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 0 },
});
g.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 0 },
});
g.connections.push(Connection {
from: Port { node: 2, index: 0 },
to: Port { node: 3, index: 0 },
});
assert_eq!(g.orphan_ports(0), (vec![], vec![1]));
assert_eq!(g.orphan_ports(1), (vec![1, 2], vec![1]));
assert_eq!(g.orphan_ports(2), (vec![1], vec![]));
assert_eq!(g.orphan_ports(3), (vec![], vec![0]));
assert_eq!(g.degrees(), vec![(0, 1), (1, 1), (1, 1), (1, 0)]);
assert_eq!(g.depths(), vec![0, 1, 2, 3]);
assert_eq!(g.node_dims(), vec![(1, 8), (8, 8), (8, 8), (8, 8)]);
assert_eq!(
g.kind_counts(),
KindCounts {
input: 1,
hidden: 2,
output: 1
}
);
assert_eq!(g.param_estimate(), 16 + 3 * 72);
assert_eq!(g.activation_counts(), vec![(Activation::Identity, 4)]);
}
#[test]
fn test_node_dims_with_override() {
let mut g = Topology::new(1, None);
g.nodes.push(Node::new_input(0, 1));
let mut wide = Node::new_hidden(1, 1, 1);
wide.hidden_dim = Some(32);
g.nodes.push(wide);
g.nodes.push(Node::new_output(2, 1, 1));
g.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 0 },
});
g.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 0 },
});
assert_eq!(g.node_dims(), vec![(1, 8), (8, 32), (32, 8)]);
}
#[test]
fn test_rewire_orphaned_outputs() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 3, 2));
graph.nodes.push(Node::new_hidden(2, 2, 1));
graph.nodes.push(Node::new_output(3, 1, 1));
graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 2 },
});
graph.connections.push(Connection {
from: Port { node: 0, index: 1 },
to: Port { node: 2, index: 0 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 1 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 1 },
to: Port { node: 3, index: 0 },
});
assert_eq!(graph.orphan_counts(), (2, 1));
let added = graph.rewire_orphaned_outputs();
assert_eq!(added, 1);
assert_eq!(graph.orphan_counts(), (2, 0));
assert_eq!(graph.validate(), Ok(()));
let module = Network::build(&graph, Device::CPU).unwrap();
let batch = 2i64;
let input = rand_input(batch, graph.options.input_dim);
let output = module.forward(&input).unwrap();
assert_eq!(output.shape(), &[batch, graph.options.hidden_dim as i64]);
}
#[test]
fn test_rewire_orphaned_outputs_rewires_even_with_dim_mismatch() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 1));
let mut wide = Node::new_hidden(1, 1, 1);
wide.hidden_dim = Some(32);
graph.nodes.push(wide);
graph.nodes.push(Node::new_output(2, 1, 1));
graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 1, index: 0 },
});
assert_eq!(graph.orphan_counts(), (1, 1));
assert_eq!(graph.rewire_orphaned_outputs(), 1);
assert_eq!(graph.orphan_counts(), (0, 0));
}
#[test]
fn test_rewire_orphaned_outputs_deterministic_per_seed() {
let build = |seed: usize| {
let mut graph = Topology::new(0, None);
graph.options.seed = seed;
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 2, 2));
graph.nodes.push(Node::new_hidden(2, 2, 2));
graph.nodes.push(Node::new_output(3, 2, 1));
graph.finalize();
assert_eq!(graph.validate(), Ok(()));
graph.connections.clone()
};
let a = build(42);
let b = build(42);
assert_eq!(a, b, "same seed must rewire identically");
let _ = build(99);
}
#[test]
fn test_finalize_auto_de_orphans() {
let mut graph = Topology::new(0, None);
graph.nodes.push(Node::new_input(0, 2));
graph.nodes.push(Node::new_hidden(1, 3, 2));
graph.nodes.push(Node::new_hidden(2, 2, 1));
graph.nodes.push(Node::new_output(3, 1, 1));
graph.finalize();
assert_eq!(graph.validate(), Ok(()));
let (_, orphaned_outputs) = graph.orphan_counts();
assert_eq!(orphaned_outputs, 0);
}
#[test]
fn test_validate_allows_inconsistent_input_dims() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 2)); let mut wide = Node::new_hidden(1, 1, 1);
wide.hidden_dim = Some(16);
graph.nodes.push(wide);
graph.nodes.push(Node::new_output(2, 2, 1)); graph.connections.push(Connection {
from: Port { node: 0, index: 0 },
to: Port { node: 2, index: 0 },
});
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 1 },
});
assert!(graph.validate().is_ok());
}
#[test]
fn test_validate_allows_orphan_dim_mismatch() {
let mut graph = Topology::new(1, None);
graph.nodes.push(Node::new_input(0, 1));
let mut wide = Node::new_hidden(1, 1, 1);
wide.hidden_dim = Some(16);
graph.nodes.push(wide);
graph.nodes.push(Node::new_output(2, 2, 1));
graph.connections.push(Connection {
from: Port { node: 1, index: 0 },
to: Port { node: 2, index: 0 },
});
assert!(graph.validate().is_ok());
}
#[test]
fn test_ensure_scaffold_adds_input_and_output() {
let mut graph = Topology::new(0, None);
graph.create_random_hidden_nodes(3);
graph.ensure_scaffold();
assert_eq!(graph.nodes[0].kind, NodeKind::Input);
assert_eq!(graph.nodes[0].num_outputs, 1);
assert_eq!(graph.nodes.last().unwrap().kind, NodeKind::Output);
for (i, n) in graph.nodes.iter().enumerate() {
assert_eq!(n.id, i);
}
}
#[test]
fn test_ensure_scaffold_idempotent() {
let mut graph = Topology::new(0, None);
graph.create_random_hidden_nodes(2);
graph.ensure_scaffold();
let nodes = graph.nodes.clone();
graph.ensure_scaffold();
assert_eq!(graph.nodes, nodes);
}
#[test]
fn test_finalize_scaffolds_hidden_only_graph() {
let mut graph = Topology::new(0, None);
graph.create_random_hidden_nodes(5);
graph.finalize();
let n_in = graph
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Input)
.count();
let n_out = graph
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Output)
.count();
assert_eq!(n_in, 1);
assert_eq!(n_out, 1);
assert_eq!(graph.validate(), Ok(()));
}
#[test]
fn test_multiple_output_nodes_rejected() {
let mut graph = Topology::new(0, None);
graph.nodes.push(Node::new_input(0, 1));
graph.nodes.push(Node::new_output(1, 1, 1));
graph.nodes.push(Node::new_output(2, 1, 1)); assert!(graph.validate().is_err(), "multiple outputs must fail");
}
proptest! {
#[test]
fn prop_random_graphs_always_validate(graph in topology_strategy()) {
prop_assert!(
graph.validate().is_ok(),
"random graph failed validation: {:?}",
graph.validate().err()
);
}
#[test]
fn prop_network_auto_de_orphans_outputs(graph in topology_strategy()) {
let (_input_orphans, _output_orphans) = graph.orphan_counts();
}
#[test]
fn prop_wiring_invariants(graph in topology_strategy()) {
let mut seen: Vec<Port> = Vec::new();
let input_id = graph.nodes.iter().find(|n| n.kind == NodeKind::Input).map(|n| n.id);
for conn in &graph.connections {
prop_assert!(conn.from.node < conn.to.node, "backward connection: {conn}");
if Some(conn.from.node) != input_id {
prop_assert!(
!seen.contains(&conn.from),
"output {} used twice",
conn.from_label()
);
}
seen.push(conn.from);
}
}
#[test]
fn prop_random_graphs_build_and_forward(graph in topology_strategy()) {
let module = Network::build(&graph, Device::CPU).unwrap();
let input = rand_input(2, graph.options.input_dim);
let out = module.forward(&input).unwrap();
prop_assert_eq!(out.shape(), &[2, graph.options.output_dim as i64]);
}
#[test]
fn prop_diagnostics_match_built_network(graph in topology_strategy()) {
let module = Network::build(&graph, Device::CPU).unwrap();
let dims = graph.node_dims();
prop_assert_eq!(&dims, &module.node_dims);
let real_params: i64 = module
.parameters()
.iter()
.map(|p| p.variable.data().numel())
.sum();
prop_assert_eq!(graph.param_estimate() as i64, real_params);
let degrees = graph.degrees();
let in_sum: usize = degrees.iter().map(|d| d.0).sum();
let out_sum: usize = degrees.iter().map(|d| d.1).sum();
prop_assert_eq!(in_sum, graph.connections.len());
prop_assert_eq!(out_sum, graph.connections.len());
let depths = graph.depths();
for c in &graph.connections {
prop_assert!(
depths[c.to.node] > depths[c.from.node],
"wire {c} must strictly increase depth: {:?}",
depths
);
}
}
#[test]
fn prop_finalize_scaffolds_skeleton(
opts in topology_options_strategy(),
n_hidden in 0usize..6,
) {
let mut graph = Topology::new(0, Some(opts));
graph.create_random_hidden_nodes(n_hidden);
graph.finalize();
let n_in = graph
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Input)
.count();
let n_out = graph
.nodes
.iter()
.filter(|n| n.kind == NodeKind::Output)
.count();
prop_assert!(n_in >= 1, "scaffold must ensure an Input node");
prop_assert_eq!(
n_out, 1,
"scaffold must leave exactly one Output node"
);
prop_assert!(graph.validate().is_ok());
}
}
}