block_graph/
graph.rs

1fn set_bit(x: u64, idx: u8, b: bool) -> u64{(x & !(1 << idx)) | ((b as u64) << idx)}
2impl BuildHasher for H{
3	fn build_hasher(&self)->Self::Hasher{*self}
4	type Hasher=H;
5}
6impl Decompose for Label{
7	fn compose(label:Self::Decomposition)->Self{label.into()}
8	fn decompose(self)->Self::Decomposition{self.to_string()}
9	fn decompose_cloned(&self)->Self::Decomposition{self.clone().decompose()}
10	type Decomposition=String;
11}
12impl Default for Label{
13	fn default()->Self{
14		Self{id:rand::random(),name:None}
15	}
16}
17impl Display for Label{
18	fn fmt(&self,f:&mut Formatter<'_>)->FmtResult{
19		if self.id!=0{UpperHex::fmt(&self.id,f)?}
20		if let Some(text)=&self.name{
21			write!(f,"{}{text}",if self.id==0{""}else{": "})?;
22		}
23		Ok(())
24	}
25}
26impl From<Option<String>> for Label{
27	fn from(value:Option<String>)->Self{
28		if let Some(v)=value{v.into()}else{Self::new()}
29	}
30}
31impl From<String> for Label{
32	fn from(value:String)->Self{Self::from_str(&value).unwrap()}
33}
34impl From<u64> for Label{
35	fn from(value:u64)->Self{
36		Self{id:value,name:None}
37	}
38}
39impl From<usize> for Label{
40	fn from(value:usize)->Self{Self::from(value as u64)}
41}
42impl FromStr for Label{
43	fn from_str(s:&str)->Result<Self,Self::Err>{
44		let parsewithid:Option<Self>=(||{
45			let idstop=s.find(": ").unwrap_or(s.len());
46			let id=u64::from_str_radix(&s[..idstop],16).ok()?;
47			let name=(idstop<s.len()).then(||Arc::from(&s[idstop+2..]));
48			Some(Self{id,name})
49		})();
50		Ok(if let Some(l)=parsewithid{l}else{Self::from(0_u64).with_name(s)})
51	}
52	type Err=();
53}
54impl Hasher for H{
55	#[inline]
56	fn finish(&self)->u64{self.0}
57	#[inline]
58	fn write(&mut self,bytes:&[u8]){
59		let H(h)=self;
60		for &byte in bytes.iter(){*h=h.rotate_left(8)^byte as u64}
61	}
62    #[inline]
63    fn write_u64(&mut self,n:u64){self.0^=n}
64}
65impl Label{
66	/// creates a new label
67	pub fn new()->Self{
68		Self{id:rand::random(),name:None}
69	}
70	/// sets the label id
71	pub fn with_id(mut self,id:u64)->Self{
72		self.id=id;
73		self
74	}
75	/// names the label
76	pub fn with_name<S:AsRef<str>>(mut self,name:S)->Self{
77		let name=name.as_ref();
78		self.name=if name.len()==0{None}else{Some(name.into())};
79		self
80	}
81	/// sets the label id
82	pub fn with_random_id(mut self)->Self{
83		self.id=rand::random();
84		self
85	}
86}
87impl<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> ConnectionEditor<'a,C,V>{
88	/// gets the index, or usize::MAX to insert at the end of the order regardless of the number of connections
89	pub fn get_index(&self)->usize{self.index}
90	/// references the input label
91	pub fn input(&self)->&Label{&self.input}
92	/// adds a layer to the associated graph if there is one, returning the layer if not or the previous layer associated with the layer id
93	pub fn insert_layer<L:Into<C>>(&mut self,layer:L)->Option<C>{self.graph.as_mut().and_then(|g|g.layers.insert(self.layer.clone(),layer.into()))}
94	/// checks if clear
95	pub fn is_clear(&self)->bool{self.clear}
96	/// references the connection label
97	pub fn label(&self)->&Label{&self.connection}
98	/// references the layer label
99	pub fn layer(&self)->&Label{&self.layer}
100	/// references the input label
101	pub fn output(&self)->&Label{&self.output}
102	/// inserts the layer into the graph using the current layer id
103	pub fn with<L:Into<C>>(mut self,layer:L)->Self{
104		self.insert_layer(layer);
105		self
106	}
107	/// sets the flag for whether the input should be cleared after use
108	pub fn with_clear(mut self,clear:bool)->Self{
109		self.clear=clear;
110		self
111	}
112	/// sets the index to insert in the run order, or usize::MAX to insert at the end of the order regardless of the number of connections
113	pub fn with_index(mut self,index:usize)->Self{
114		self.index=index;
115		self
116	}
117	/// sets the input label
118	pub fn with_input<L:Into<Label>>(mut self,label:L)->Self{
119		self.input=label.into();
120		self
121	}
122	/// sets the connection label
123	pub fn with_label<L:Into<Label>>(mut self,label:L)->Self{
124		self.connection=label.into();
125		self
126	}
127	/// sets the layer label
128	pub fn with_layer<L:Into<Label>>(mut self,label:L)->Self{
129		self.layer=label.into();
130		self
131	}
132	/// sets the output label
133	pub fn with_output<L:Into<Label>>(mut self,label:L)->Self{
134		self.output=label.into();
135		self
136	}
137}
138impl<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge>ConnectionInfo<'a,C,V>{
139	/// gets the index in the connection processing order
140	pub fn get_index(&self)->usize{
141		let connection=self.connection;
142		self.graph.order.iter().position(|label|connection==label).expect("order should contain all connection labels")
143	}
144	/// gets the underlying layer associated with the layer label
145	pub fn get_layer(&self)->Option<&C>{self.graph.layers.get(&self.layer)}
146	/// references the input label
147	pub fn input(&self)->&Label{&self.input}
148	/// checks if clear
149	pub fn is_clear(&self)->bool{self.clear}
150	/// references the connection label
151	pub fn label(&self)->&Label{self.connection}
152	/// references the layer label
153	pub fn layer(&self)->&Label{self.layer}
154	/// references the input label
155	pub fn output(&self)->&Label{self.output}
156}
157impl<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> Default for ConnectionEditor<'a,C,V>{
158	fn default()->Self{
159		Self{clear:false,connection:Label::new(),graph:None,index:usize::MAX,input:Label::new(),layer:Label::new(),output:Label::new()}
160	}
161}
162impl<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> Drop for ConnectionEditor<'a,C,V>{
163	fn drop(&mut self){
164		if let Some(g)=self.graph.take(){g.add_connection(self)}
165	}
166}
167impl<A:AI<Vec<X>,Vec<Y>>,X,Y> AI<X,Y> for Unvec<A>{
168	fn forward(&self,input:X)->Y{self.0.forward(vec![input]).into_iter().next().unwrap()}
169	fn forward_mut(&mut self,input:X)->Y{self.0.forward_mut(vec![input]).into_iter().next().unwrap()}
170}
171impl<A:Decompose> Decompose for Unvec<A>{
172	fn compose(decomposition:Self::Decomposition)->Self{Self(A::compose(decomposition))}
173	fn decompose(self)->Self::Decomposition{self.0.decompose()}
174	fn decompose_cloned(&self)->Self::Decomposition{self.0.decompose_cloned()}
175	type Decomposition=A::Decomposition;
176}
177impl<A:Into<C>,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> Extend<Graph<A>> for Graph<C>{
178	fn extend<I:IntoIterator<Item=Graph<A>>>(&mut self,iter:I){iter.into_iter().for_each(|graph|self.merge(graph))}
179}
180impl<A:Into<C>,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> FromIterator<Graph<A>> for Graph<C>{
181	fn from_iter<I:IntoIterator<Item=Graph<A>>>(iter:I)->Self{
182		let mut graph=Graph::default();
183		graph.extend(iter);
184		graph
185	}
186}
187impl<A:Op<Output=Vec<Y>>,Y> Op for Unvec<A>{
188	type Output=Y;
189}
190impl<C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> AI<Vec<V>,Vec<V>> for Graph<C>{
191	fn forward(&self,mut values:Vec<V>)->Vec<V>{
192		let mut map=HashMap::with_capacity_and_hasher(values.len(),H(0));
193		values.reverse();
194		for (_clear,input,_layer,_output) in self.order.iter().filter_map(|c|self.connections.get(c)){
195			if values.len()==0{break}
196			map.entry(input.clone()).or_insert_with(||values.pop().unwrap());
197		}
198		map=self.forward(map);
199		for (_clear,_input,_layer,output) in self.order.iter().rev().filter_map(|c|self.connections.get(c)){
200			if map.len()==0{break}
201			if let Some(y)=map.remove(output){values.push(y)}
202		}
203		values.reverse();
204		values
205	}
206	fn forward_mut(&mut self,mut values:Vec<V>)->Vec<V>{
207		let mut map=HashMap::with_capacity_and_hasher(values.len(),H(0));
208		values.reverse();
209		for (_clear,input,_layer,_output) in self.order.iter().filter_map(|c|self.connections.get(c)){
210			if values.len()==0{break}
211			map.entry(input.clone()).or_insert_with(||values.pop().unwrap());
212		}
213		map=self.forward_mut(map);
214		for (_clear,_input,_layer,output) in self.order.iter().rev().filter_map(|c|self.connections.get(c)){
215			if map.len()==0{break}
216			if let Some(y)=map.remove(output){values.push(y)}
217		}
218		values.reverse();
219		values
220	}
221}
222impl<C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge,S:BuildHasher> AI<HashMap<Label,V,S>,HashMap<Label,V,S>> for Graph<C>{
223	fn forward(&self,mut map:HashMap<Label,V,S>)->HashMap<Label,V,S>{
224		let (connections,order)=(&self.connections,&self.order);
225		let layers=&self.layers;
226
227		order.iter().filter_map(|c|connections.get(c)).for_each(|(clear,input,layer,output)|{
228			let x=if *clear>0{map.remove(input)}else{map.get(input).cloned()}.unwrap_or_default();
229			let y=if let Some(f)=layers.get(layer){f.forward(x)}else{x};
230			map.entry(output.clone()).or_default().merge(y);
231		});
232		map
233	}
234	fn forward_mut(&mut self,mut map:HashMap<Label,V,S>)->HashMap<Label,V,S>{
235		let (connections,order)=(&self.connections,&self.order);
236		let layers=&mut self.layers;
237
238		order.iter().filter_map(|c|connections.get(c)).for_each(|(clear,input,layer,output)|{
239			let x=if *clear>0{map.remove(input)}else{map.get(input).cloned()}.unwrap_or_default();
240			let y=if let Some(f)=layers.get_mut(layer){f.forward_mut(x)}else{x};
241			map.entry(output.clone()).or_default().merge(y);
242		});
243		map
244	}
245}
246impl<C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> Default for Graph<C>{
247	fn default()->Self{Self::new()}
248}
249impl<C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge> Graph<C>{
250	/// creates a new empty graph
251	pub fn new()->Self{
252		Self{connections:HashMap::with_hasher(H(0)),layers:HashMap::with_hasher(H(0)),order:Vec::new()}
253	}
254	/// adds a connection between two vertices
255	pub fn add_connection<'a>(&mut self,config:&ConnectionEditor<'a,C,V>){
256		let (connections,order)=(&mut self.connections,&mut self.order);
257		let (connection,input,layer,output)=(config.connection.clone(),config.input.clone(),config.layer.clone(),config.output.clone());
258		let (clear,index)=(config.clear,config.index);
259
260		connections.insert(connection.clone(),(clear as u64,input,layer,output));
261		if index<order.len(){order.insert(index,connection)}else{order.push(connection)}
262	}
263	/// adds a layer without connecting it
264	pub fn add_layer<X:Into<C>,L:Into<Label>>(&mut self,label:L,layer:X){
265		self.layers.insert(label.into(),layer.into());
266	}
267	/// adds a connection between vertices
268	pub fn connect<I:Into<Label>,O:Into<Label>>(&mut self,input:I,output:O)->ConnectionEditor<'_,C,V>{
269		let (connection,layer)=(Label::new(),Label::new());
270		let (input,output)=(input.into(),output.into());
271		let clear=false;
272		let index=self.order.len();
273
274		let graph=Some(self);
275		ConnectionEditor{clear,connection,graph,index,input,layer,output}
276	}
277	/// returns an iterator over the connections in an arbitrary order
278	pub fn connections<'a>(&'a self)->impl Iterator<Item=ConnectionInfo<'a,C,V>>{self.connections.keys().filter_map(move|k|self.get_connection(k))}
279	/// gets connection information by label
280	pub fn get_connection<'a>(&'a self,label:&Label)->Option<ConnectionInfo<'a,C,V>>{
281		let (connection,(clear,input,layer,output))=self.connections.get_key_value(label)?;
282		let clear=*clear>0;
283		let graph=self;
284
285		Some(ConnectionInfo{clear,connection,graph,input,layer,output})
286	}
287	/// gets the layer information by label
288	pub fn get_layer(&self,label:&Label)->Option<&C>{self.layers.get(label)}
289	/// another graphs into this one
290	pub fn merge<A:Into<C>>(&mut self,graph:Graph<A>){
291		self.connections.extend(graph.connections);
292		self.layers.extend(graph.layers.into_iter().map(|(l,a)|(l,a.into())));
293		self.order.extend(graph.order);
294	}
295	/// gets the connection order
296	pub fn order(&self)->&[Label]{&self.order}
297	/// splits the graph according to the predicate(clear, connectionlabel, inputlabel, layer, layerlabel, outputlabel). true will be sent to the returned graph. the resulting graphs will only have the layers they use
298	pub fn split<F:FnMut(bool,&Label,&Label,&C,&Label,&Label)->bool>(&mut self,mut predicate:F)->Self where C:Clone{
299		let (connections,layers,order)=(&mut self.connections,&mut self.layers,&mut self.order);
300
301		let newconnections:HashMap<_,_,H>=connections.extract_if(|connectionlabel,(clear,inputlabel,layerlabel,outputlabel)|if let Some(layer)=layers.get_mut(layerlabel){
302			predicate(*clear>0,connectionlabel,inputlabel,layer,layerlabel,outputlabel)
303		}else{
304			false
305		}).collect();
306
307		let mut oldlayers=mem::take(layers);
308		let newlayers=newconnections.iter().filter_map(|(_connectionlabel,(_clear,_inputlabel,layerlabel,_outputlabel))|if let Some(layer)=oldlayers.get(layerlabel){
309			Some((layerlabel.clone(),layer.clone()))
310		}else{
311			None
312		}).collect();
313		connections.iter().for_each(|(_connectionlabel,(_clear,_inputlabel,layerlabel,_outputlabel))|if let Some(layer)=oldlayers.remove(layerlabel){
314			layers.insert(layerlabel.clone(),layer);
315		});
316
317		let neworder=order.extract_if(..,|label|newconnections.contains_key(label)).collect();
318		order.retain(|label|connections.contains_key(label));
319
320		Self{connections:newconnections,layers:newlayers,order:neworder}
321	}
322	/// topologically sorts the graph. Inputs to the same node will retain their relative order.
323	pub fn sort(&mut self){
324		let connections=&mut self.connections;
325		let mut dedup=HashSet::with_capacity(connections.len());
326		let mut nodes:HashMap<Label,(Vec<Label>,usize)>=HashMap::with_capacity(connections.len());
327		let order=&mut self.order;
328		order.drain(..).for_each(|label|if let Some((_clear,input,_layer,output))=connections.get(&label){
329			let (_inputinputs,inputoutputs)=nodes.entry(input.clone()).or_default();
330			*inputoutputs+=1;
331			let (outputinputs,_outputoutputs)=nodes.entry(output.clone()).or_default();
332			outputinputs.push(label);
333		});
334
335		while nodes.len()>0{
336			let mut cycle=true;
337			let mut n=order.len();
338			nodes.retain(|_node,(inputs,outputs)|{
339				if *outputs==0{
340					cycle=false;
341					order.extend(inputs.drain(..).filter(|i|dedup.insert(i.clone())).rev());
342				}
343				inputs.len()>0
344			});
345			if cycle{order.extend(nodes.iter_mut().filter_map(|(_node,(inputs,_outputs))|inputs.pop()).filter(|i|dedup.insert(i.clone())))}
346			while n<order.len(){
347				if let Some((inputs,outputs))=nodes.get_mut(&connections.get(&order[n]).unwrap().1){
348					*outputs-=1;
349					if inputs.len()==1&&*outputs==0{order.push(inputs.pop().unwrap())}
350				}
351				n+=1;
352			}
353		}
354		order.iter().for_each(|label|if let Some((clear,input,_layer,_output))=connections.get_mut(label){*clear=set_bit(*clear,1,!nodes.contains_key(input))});
355		order.reverse();
356	}
357}
358impl<C:Decompose> Decompose for Graph<C>{// TODO ideally this would preserve unconnected layers too
359	fn compose((connections,layers):Self::Decomposition)->Self{
360		let mut order=Vec::with_capacity(connections.len());
361		let connections=connections.into_iter().map(|decomposed|{
362			let (label,(clear,input,layer,output)):(Label,(u64,Label,Label,Label))=Decompose::compose(decomposed);
363			order.push(label.clone());
364			(label,(clear,input,layer,output))
365		}).collect();
366		let layers=layers.into_iter().map(Decompose::compose).collect();
367		Self{connections,layers,order}
368	}
369	fn decompose(self)->Self::Decomposition{
370		let (mut connections,mut layers,order)=(self.connections,self.layers,self.order);
371
372		let (mut decomposedconnections,mut decomposedlayers)=(Vec::new(),Vec::new());
373		order.iter().filter_map(|label|connections.remove_entry(label)).for_each(|(label,(clear,input,layer,output))|{
374			decomposedlayers.extend(layers.remove_entry(&layer).map(|(label,layer)|(label.decompose(),layer.decompose())));
375			decomposedconnections.push((label.decompose(),(clear,input.decompose(),layer.decompose(),output.decompose())));
376		});
377		(decomposedconnections,decomposedlayers)
378	}
379	fn decompose_cloned(&self)->Self::Decomposition{
380		let (connections,layers,order)=(&self.connections,&self.layers,&self.order);
381		let mut layersfound=HashSet::new();
382
383		let (mut decomposedconnections,mut decomposedlayers)=(Vec::new(),Vec::new());
384		order.iter().filter_map(|label|connections.get_key_value(label)).for_each(|(label,(clear,input,layer,output))|{
385			if layersfound.insert(layer.clone()){decomposedlayers.extend(layers.get_key_value(layer).map(|(label,layer)|(label.decompose_cloned(),layer.decompose_cloned())))}
386			decomposedconnections.push((label.decompose_cloned(),(*clear,input.decompose_cloned(),layer.decompose_cloned(),output.decompose_cloned())));
387		});
388		(decomposedconnections,decomposedlayers)
389	}
390	type Decomposition=(Vec<(String,(u64,String,String,String))>,Vec<(String,C::Decomposition)>);
391}
392impl<C:Op> Op for Graph<C>{
393	type Output=Vec<C::Output>;
394}
395impl<E,V:Extend<E>+IntoIterator<Item=E>> Merge for Extendable<V>{
396	fn merge(&mut self,other:Self){self.0.extend(other.0)}
397}
398impl<E:Merge> Merge for Option<E>{
399	fn merge(&mut self,other:Self){
400		match (self,other){(Some(this),Some(other))=>this.merge(other),(this,Some(other))=>*this=Some(other),_=>()}
401	}
402}
403impl<E> Merge for Vec<E>{
404	fn merge(&mut self,other:Self){self.extend(other)}
405}
406impl<S:?Sized+AsRef<str>> From<&S> for Label{
407	fn from(value:&S)->Self{Self::from_str(value.as_ref()).unwrap()}
408}
409#[cfg(test)]
410mod tests{
411	#[test]
412	fn sort_digons(){
413		let mut graph:Graph<Append<u64>>=Graph::new();
414		let mut order=[0,1,2,3,4];
415
416		order.shuffle(&mut rand::rng());
417		for &n in order.iter(){
418			graph.connect(n,n+1).with_clear(true).with(Append(n+100));
419			graph.connect(n,n+1).with_clear(true).with(Append(n+200));
420		}
421		let unsorted:Vec<u64>=Unvec(&graph).forward(Vec::new());
422
423		graph.sort();
424		let sorted:Vec<u64>=Unvec(&graph).forward(Vec::new());
425		assert_eq!(sorted,[100,200,101,201,102,202,103,203,104,204]);
426		assert_ne!(sorted,unsorted);
427	}
428	#[test]
429	fn sort_line(){
430		let mut graph:Graph<Append<u64>>=Graph::new();
431		let mut order=[0,1,2,3,4,5,6,7,8,9];
432
433		order.shuffle(&mut rand::rng());
434		for &n in order.iter(){
435			graph.connect(n,n+1).with(Append(n));
436		}
437		let unsorted:Vec<u64>=Unvec(&graph).forward(Vec::new());
438
439		graph.sort();
440		let sorted:Vec<u64>=Unvec(&graph).forward(Vec::new());
441		assert_eq!(sorted,[0,1,2,3,4,5,6,7,8,9]);
442		assert_ne!(sorted,unsorted);
443	}
444	impl<E:Clone> AI<Vec<E>,Vec<E>> for Append<E>{
445		fn forward(&self,mut input:Vec<E>)->Vec<E>{
446			input.push(self.0.clone());
447			input
448		}
449	}
450	impl<E:Clone> Op for Append<E>{
451		type Output=Vec<E>;
452	}
453	#[derive(Clone,Debug)]
454	/// test ai module that appends a number to a vec
455	struct Append<E:Clone>(E);
456	use rand::seq::SliceRandom;
457	use super::*;
458}
459#[derive(Clone,Debug,Default,Eq,Hash,Ord,PartialEq,PartialOrd)]
460#[repr(transparent)]
461/// wraps collections so that merging concatenates them using the Extend trait
462pub struct Extendable<V>(pub V);
463/*#[derive(Clone,Debug)]
464/// allows configuring a connection to add to the graph
465pub struct ConnectionConfig{clear:bool,connection:Label,index:usize,input:Label,layer:Label,output:Label}*/
466#[derive(Debug)]// TODO split connection config and connection editor
467/// allows configuring a connection to add to the graph, or manipulating an existing connection
468pub struct ConnectionEditor<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge>{clear:bool,connection:Label,graph:Option<&'a mut Graph<C>>,index:usize,input:Label,layer:Label,output:Label}
469#[derive(Clone,Debug)]
470/// information about a connection
471pub struct ConnectionInfo<'a,C:AI<V,V>+Op<Output=V>,V:Clone+Default+Merge>{clear:bool,connection:&'a Label,graph:&'a Graph<C>,input:&'a Label,layer:&'a Label,output:&'a Label}
472#[derive(Clone,Debug,Eq,PartialEq)]
473/// graph like ai operation structure
474pub struct Graph<C>{connections:HashMap<Label,(u64,Label,Label,Label),H>,layers:HashMap<Label,C,H>,order:Vec<Label>}
475#[derive(Clone,Debug,Eq,Hash,PartialEq)]
476/// label for graph connections or layers or nodes. format is id: name where id is a hex number or simply id if there is no name. name without a number will be parse as a name with a 0 id
477pub struct Label{id:u64,name:Option<Arc<str>>}
478#[derive(Clone,Copy,Debug,Default)]
479#[repr(transparent)]
480/// wraps the graph so it can take singular io
481pub struct Unvec<A>(pub A);
482/// trait to allow merging multiple outputs into one graph node
483pub trait Merge{
484	/// merges the other into self, taking out of other if convenient
485	fn merge(&mut self,other:Self);
486}
487#[derive(Clone,Copy,Debug,Default)]
488#[repr(transparent)]
489struct H(u64);
490use crate::{AI,Decompose,Op};
491use std::{
492	collections::{HashMap,HashSet},fmt::{Display,Formatter,UpperHex,Result as FmtResult},hash::{BuildHasher,Hasher,Hash},iter::{FromIterator,Extend},mem,str::FromStr,sync::Arc
493};
block_graph/graph.rs

block_graph/
graph.rs
