Function gen

pub fn gen<T, U, F, G, H, E>(
    (nodes, edges): Graph<T, U>,
    n: usize,
    f: F,
    g: G,
    h: H,
    settings: &GenerateSettings,
) -> Result<Graph<T, U>, (Graph<T, U>, E)>
where
    T: Eq + Hash + Clone,
    F: Fn(&T, usize) -> Result<(T, U), E>,
    G: Fn(&T) -> bool,
    H: Fn(&U, &U) -> Result<U, Option<E>>,
    E: From<GenerateError>,

Generates a graph from:

• an initial seed state a
• maximum n edges
• a function f to generate a new node with edge
• a filter g to post-process nodes
• a composer h to use for transforming edges when nodes are filtered
• settings to control usage of memory

Returns a list of nodes and a list of edges.

• Ok if generation was successful without hitting memory limits
• Err if generation hit memory limits

Waiting with filtering until post-processing makes it possible to create an edge between nodes that require multiple steps.

The maximum number of edges is usually determined from the length of a list of valid operations.

Error handling

The algorithm continues to post-processing when hitting memory limits. It is assumed that one wants to make use of the data generated, where memory limits are met often due to combinatorial explosions.

The algorithm assumes that there are other limits besides those in GenerateSettings. To handle errors, one adds a type that implements From<GenerateError>. The unit type () can be used when error handling is not needed.

Tip: Since this function requires 6 generic type arguments, it is easier to set the error type on the output type and let Rust infer the rest.

For example:

let (nodes, edges) = match gen(start, n, f, g, h, &settings) {
    Ok(x) => x,
    Err((x, ())) => x,
};

When an error happens during composing edges, one can choose whether to report the error with Err(Some(err)), or ignore it with Err(None). This is useful because sometimes you want to filter edges without reporting errors. The algorithm assumes that one wishes to continue generating the graph when encountering an error. Only the first error will be reported.

Examples found in repository

examples/eq.rs (line 92)

fn main() {
    // Change this to control the number of terms in the equation.
    let n: usize = if let Some(x) = std::env::args_os().skip(1).take(1).next() {
        usize::from_str(&x.into_string().expect("number")).unwrap()
    } else {
        3
    };
    // Change this to control how many
    let solution_terms: usize = if let Some(x) = std::env::args_os().skip(2).take(1).next() {
        usize::from_str(&x.into_string().expect("number")).unwrap()
    } else {
        1
    };

    // Putting all terms except the last one
    let start = Eq {
        side: {
            if solution_terms == 1 && n > 0 {
                let mut res = vec![true; n-1];
                res.push(false);
                res
            } else {
                vec![true; n]
            }
        },
        positive: vec![true; n],
    };

    // Swap side and sign on the chosen term.
    let f = |eq: &Eq, ind: usize| {
        let mut eq = eq.clone();
        eq.side[ind] = !eq.side[ind];
        eq.positive[ind] = !eq.positive[ind];
        Ok((eq, Swap(vec![ind])))
    };
    // Filter nodes to those with the specified number of solutions.
    let g = |eq: &Eq| eq.len_right() == solution_terms;
    // Join operations.
    // Since these swap operations are commutative, require order.
    let h = |a: &Swap, b: &Swap| if a.0 >= b.0 {Err(None)} else {Ok(Swap({
        let mut a = a.0.clone();
        a.extend_from_slice(&b.0);
        a.sort();
        a
    }))};

    let settings = GenerateSettings {
        max_nodes: 1000,
        max_edges: 1000,
    };

    let seed = (vec![start], vec![]);
    // Generate graph.
    let (eqs, mut edges) = match gen(seed, n, f, g, h, &settings) {
        Ok(x) => x,
        Err((x, ())) => x,
    };

    // Remove all edges that are not bidirectional.
    bidir(&mut edges);
    edges.sort();
    for i in 0..eqs.len() {
        println!("{}: {}", i, eqs[i]);
    }
    for i in 0..edges.len() {
        println!("{:?}", edges[i]);
    }

    println!("(nodes, edges): ({}, {})", eqs.len(), edges.len());
}