Skip to content

Instantly share code, notes, and snippets.

Created March 4, 2017 20:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save anonymous/a53bc11473522f47fe71a7a46b54908d to your computer and use it in GitHub Desktop.
Save anonymous/a53bc11473522f47fe71a7a46b54908d to your computer and use it in GitHub Desktop.
Shared via Rust Playground
use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::Hash;
use std::fmt::Debug;
#[derive(Debug, Clone)]
struct EdgeIndex<Ix>(Ix);
#[derive(Debug, Clone)]
struct NodeIndex<Ix>(Ix);
#[derive(Debug, Clone)]
struct Node<N, Ix> {
value: N,
incoming: Vec<EdgeIndex<Ix>>,
outgoing: Vec<EdgeIndex<Ix>>
}
#[derive(Debug, Clone)]
struct Edge<E, Ix> {
value: E,
source: NodeIndex<Ix>,
sink: NodeIndex<Ix>
}
#[derive(Debug)]
struct DAG<N, E, Ix> where Ix:Eq + Hash {
inputs: Vec<Ix>,
outputs: Vec<Ix>,
nodes: HashMap<Ix, Node<N, Ix>>,
edges: HashMap<Ix, Edge<E, Ix>>
}
impl<N, E, Ix: Debug + Eq + Hash> DAG<N, E, Ix> {
fn relatives(
&self,
ref ix: &Ix,
edge_fn: Box<Fn(&Node<N, Ix>) -> &Vec<EdgeIndex<Ix>>>,
node_fn: Box<Fn(&Edge<E, Ix>) -> &NodeIndex<Ix>>
) -> Option<Vec<&Ix>> {
match self.nodes.get(ix) {
Some(node) => {
Some(edge_fn(node).iter().map(|&EdgeIndex(ref edge_ix)| {
let &NodeIndex(ref node_ix) = node_fn(self.edges.get(edge_ix).unwrap());
node_ix
}).collect())
}
_ => { None }
}
}
fn children(&self, ref ix: &Ix) -> Option<Vec<&Ix>> {
self.relatives(
ix,
Box::new(move |node| &node.outgoing),
Box::new(move |edge| &edge.sink)
)
}
fn parents(&self, ref ix: &Ix) -> Option<Vec<&Ix>> {
self.relatives(
ix,
Box::new(move |node| &node.incoming),
Box::new(move |edge| &edge.source)
)
}
fn dfs(&self) -> (Vec<&Ix>, Vec<&Ix>) {
let mut stack: Vec<&Ix> = self.inputs.iter().collect();
let mut pre: Vec<&Ix> = Vec::new();
let mut post: Vec<&Ix> = Vec::new();
let mut visited: HashSet<&Ix> = HashSet::new();
while !stack.is_empty() {
let ix = stack.pop().unwrap();
if visited.contains(ix) {
post.push(ix);
} else {
visited.insert(ix);
pre.push(ix);
stack.push(ix);
for target_ix in self.children(ix).unwrap() {
if !visited.contains(target_ix) {
stack.push(target_ix);
}
}
}
}
(pre, post)
}
fn topological_sort(&self) -> Vec<&Ix> {
let (_, mut post) = self.dfs();
post.reverse();
post
}
}
impl<Ix: Eq + Hash + Debug> DAG<Gate, Wire, Ix> {
fn compute(&self, input_bits: &Vec<Bit>) -> Vec<Bit> {
let mut value_map: HashMap<&Ix, Bit> = HashMap::new();
for (node_ix, &input_bit) in self.inputs.iter().zip(input_bits.iter()) {
value_map.insert(node_ix, input_bit);
}
let node_ixs: Vec<&Ix> = self.topological_sort();
for &node_ix in &node_ixs {
if let Node{value: Gate::Internal{ref op}, ..} = self.nodes[node_ix] {
let parent_ixs = self.parents(node_ix).unwrap();
let parent_bits: Vec<Bit> = parent_ixs.iter().map(|parent_ix| {
value_map[parent_ix]
}).collect();
if op.arity != (parent_bits.len() as u32) {
panic!("Logical operation arity {} does not match number of incoming wires {}.", op.arity, parent_bits.len());
}
value_map.insert(node_ix, (op.f)(parent_bits));
}
}
self.outputs.iter().map(|output_ix| value_map[output_ix]).collect()
}
}
type DefaultIx = u32;
type Bit = bool;
#[derive(Debug, Clone)]
enum OpType {
AND,
OR,
NOT
}
#[derive(Debug, Clone)]
struct LogicalOp {
op_type: OpType,
arity: u32,
f: fn(Vec<Bit>) -> Bit
}
const AND_OP: LogicalOp = LogicalOp {
op_type: OpType::AND,
arity: 2,
f: logical_add
};
const OR_OP: LogicalOp = LogicalOp {
op_type: OpType::OR,
arity: 2,
f: logical_or
};
const NOT_OP: LogicalOp = LogicalOp {
op_type: OpType::NOT,
arity: 1,
f: logical_not
};
fn logical_add(bits: Vec<Bit>) -> Bit { bits[0] & bits[1] }
fn logical_or(bits: Vec<Bit>) -> Bit { bits[0] || bits[1] }
fn logical_not(bits: Vec<Bit>) -> Bit { !bits[0] }
#[derive(Debug, Clone)]
enum Gate {
Input,
Internal {
op: LogicalOp
}
}
impl Gate {
fn new_internal(logical_op: LogicalOp) -> Gate {
Gate::Internal {op: logical_op}
}
fn new_input() -> Gate {
Gate::Input {}
}
}
#[derive(Debug, Clone)]
struct Wire {
}
impl Wire {
fn new() -> Wire {
Wire {}
}
}
fn test() -> Vec<Bit> {
let node0 = Node{value: Gate::new_input(), incoming: Vec::new(), outgoing: vec![EdgeIndex(0), EdgeIndex(1)]};
let node1 = Node{value: Gate::new_input(), incoming: Vec::new(), outgoing: vec![EdgeIndex(2)]};
let node2 = Node{value: Gate::new_internal(AND_OP), incoming: vec![EdgeIndex(0), EdgeIndex(2)], outgoing: vec![EdgeIndex(3)]};
let node3 = Node{value: Gate::new_internal(OR_OP), incoming: vec![EdgeIndex(1), EdgeIndex(3)], outgoing: vec![EdgeIndex(4)]};
let node4 = Node{value: Gate::new_internal(NOT_OP), incoming: vec![EdgeIndex(4)], outgoing: Vec::new()};
let edge0 = Edge{value: Wire::new(), source: NodeIndex(0), sink: NodeIndex(2)};
let edge1 = Edge{value: Wire::new(), source: NodeIndex(0), sink: NodeIndex(3)};
let edge2 = Edge{value: Wire::new(), source: NodeIndex(1), sink: NodeIndex(2)};
let edge3 = Edge{value: Wire::new(), source: NodeIndex(2), sink: NodeIndex(3)};
let edge4 = Edge{value: Wire::new(), source: NodeIndex(3), sink: NodeIndex(4)};
let dag: DAG<Gate, Wire, DefaultIx> = DAG {
inputs: vec![0, 1],
outputs: vec![4],
nodes: [(0, node0), (1, node1), (2, node2), (3, node3), (4, node4)].iter().cloned().collect(),
edges: [(0, edge0), (1, edge1), (2, edge2), (3, edge3), (4, edge4)].iter().cloned().collect()
};
let inputs = vec![false, false];
dag.compute(&inputs)
}
fn main() {
println!("{:?}", test());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment