Trait flag_algebra::SubFlag

source ·

pub trait SubFlag<F>where
    F: Flag,
    Self: Sized,{
    const SUBCLASS_NAME: &'static str;
    const HEREDITARY: bool = F::HEREDITARY;

    // Required method
    fn is_in_subclass(flag: &F) -> bool;
}

Expand description

Trait for defining a class of flag as a subset of an already defined class of flag.

The dimension of the related flag algebra will be equal to the size of the subclass.

Flags of a sublass are generated by filtering flags with the is_in_subclass method when extending Flags of size n from flags of size n-1 (in the subclass). Since filtering happens at each step, the exhaustive list of flags of the general class is never generated.

§Example

// This shows how to define triangle-free graphs based on graphs.
use flag_algebra::*;
use flag_algebra::flags::Graph;

// We first define a (zero-sized) type identifying the subclass
enum TriangleFree {}

// We want `SubClass<Graph, TriangleFree>` to be a subclass of `Graph`.
// This is done by implementing `SubFlag<Graph>` for `TriangleFree`.
impl SubFlag<Graph> for TriangleFree {
    const SUBCLASS_NAME: &'static str = "Triangle-free graph for the example";

    // Compute if the graph is triangle-free.
    fn is_in_subclass(g: &Graph) -> bool {
        for (u, v) in g.edges() {
            for w in 0..u {
                if g.edge(u, w) && g.edge(v, w) {
                    return false // Found a triangle
                }
            }
        }
        true
    }
}

// We can now use `SubClass<Graph, TriangleFree>` as flags for triangle-free graphs.
type F = SubClass<Graph, TriangleFree>;
let basis: Basis<F> = Basis::new(4);
assert_eq!(basis.get().len(), 7); // There are 7 triangle-free graphs of size 4