eq/
eq.rs

1/*
2
3This example shows to generate all solutions of an equation of the form:
4
5    x0 + x1 + x2 + ... + xn-2 = xn-1
6
7For example:
8
9    a + b = c
10    c - a = b
11    c - b = a
12
13Each solution is a node in a generated graph.
14An edge tells how to swap sides and sign to get from one node to another.
15
16To get from one solution to another, one only needs to move maximum two terms.
17
18If the right side is negative, automatic inversion is used.
19This improves the performance of the graph generation.
20
21The number of nodes from `n` terms and `m` right-side terms is:
22
23    bin(n, m)
24
25The number of edges is the number of pairs between nodes:
26
27    pairs(bin(n, m))
28
29    pairs(n) = n * (n-1) / 2
30
31*/
32
33extern crate graph_builder;
34
35use std::str::FromStr;
36
37use graph_builder::*;
38
39fn main() {
40    // Change this to control the number of terms in the equation.
41    let n: usize = if let Some(x) = std::env::args_os().skip(1).take(1).next() {
42        usize::from_str(&x.into_string().expect("number")).unwrap()
43    } else {
44        3
45    };
46    // Change this to control how many
47    let solution_terms: usize = if let Some(x) = std::env::args_os().skip(2).take(1).next() {
48        usize::from_str(&x.into_string().expect("number")).unwrap()
49    } else {
50        1
51    };
52
53    // Putting all terms except the last one
54    let start = Eq {
55        side: {
56            if solution_terms == 1 && n > 0 {
57                let mut res = vec![true; n-1];
58                res.push(false);
59                res
60            } else {
61                vec![true; n]
62            }
63        },
64        positive: vec![true; n],
65    };
66
67    // Swap side and sign on the chosen term.
68    let f = |eq: &Eq, ind: usize| {
69        let mut eq = eq.clone();
70        eq.side[ind] = !eq.side[ind];
71        eq.positive[ind] = !eq.positive[ind];
72        Ok((eq, Swap(vec![ind])))
73    };
74    // Filter nodes to those with the specified number of solutions.
75    let g = |eq: &Eq| eq.len_right() == solution_terms;
76    // Join operations.
77    // Since these swap operations are commutative, require order.
78    let h = |a: &Swap, b: &Swap| if a.0 >= b.0 {Err(None)} else {Ok(Swap({
79        let mut a = a.0.clone();
80        a.extend_from_slice(&b.0);
81        a.sort();
82        a
83    }))};
84
85    let settings = GenerateSettings {
86        max_nodes: 1000,
87        max_edges: 1000,
88    };
89
90    let seed = (vec![start], vec![]);
91    // Generate graph.
92    let (eqs, mut edges) = match gen(seed, n, f, g, h, &settings) {
93        Ok(x) => x,
94        Err((x, ())) => x,
95    };
96
97    // Remove all edges that are not bidirectional.
98    bidir(&mut edges);
99    edges.sort();
100    for i in 0..eqs.len() {
101        println!("{}: {}", i, eqs[i]);
102    }
103    for i in 0..edges.len() {
104        println!("{:?}", edges[i]);
105    }
106
107    println!("(nodes, edges): ({}, {})", eqs.len(), edges.len());
108}
109
110
111/// Stores an equation.
112#[derive(PartialEq, Eq, Clone, Hash)]
113pub struct Eq {
114    /// The sides of the terms.
115    pub side: Vec<bool>,
116    /// The signs of the terms.
117    pub positive: Vec<bool>,
118}
119
120impl Eq {
121    /// Returns the number of terms on the right.
122    pub fn len_right(&self) -> usize {
123        self.side.iter().filter(|&&n| n).count()
124    }
125
126    /// Returns an index if the equation has a unique right side.
127    pub fn unique_right(&self) -> Option<usize> {
128        let mut found = None;
129        for i in 0..self.side.len() {
130            if self.side[i] {
131                if found.is_some() {return None};
132                found = Some(i);
133            }
134        }
135        found
136    }
137
138    /// Returns a tuple of signs, one when positive and one when negative.
139    pub fn signs(&self) -> (&'static str, &'static str) {
140        if let Some(ind) = self.unique_right() {
141            if self.positive[ind] {("+", "-")}
142            else {("-", "+")}
143        } else {("+", "-")}
144    }
145}
146
147/// Stores swap operations.
148#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
149pub struct Swap(pub Vec<usize>);
150
151impl std::fmt::Display for Eq {
152    fn fmt(&self, w: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
153        let mut left: usize = 0;
154        let (plus, minus) = self.signs();
155        for i in 0..self.side.len() {
156            if !self.side[i] {
157                if self.positive[i] {write!(w, "{}", plus)?}
158                else {write!(w, "{}", minus)?}
159                write!(w, "x{} ", i)?;
160                left += 1;
161            }
162        }
163        if left == 0 {write!(w, "0 ")?}
164        write!(w, "= ")?;
165        if self.side.len() - left == 0 {
166            write!(w, "0")?;
167        } else {
168            for i in 0..self.side.len() {
169                if self.side[i] {
170                    if self.positive[i] {write!(w, "{}", plus)?}
171                    else {write!(w, "{}", minus)?}
172                    write!(w, "x{} ", i)?
173                }
174            }
175        }
176        Ok(())
177    }
178}
eq/eq.rs

eq/
eq.rs
