A generic implementation of flag algebras.
Flag algebras is a framework used to produce computer-assisted proofs of some inequalities in combinatorics, relying on Semi-Definite Programming.
```rust // Proving that in any graph, at least 1/4 of the triples // are triangles or independent sets. use flagalgebra::*; use flagalgebra::flags::Graph;
pub fn main() { // Work on the graphs of size 3. let basis = Basis::new(3);
// Define useful flags. let k3 = flag(&Graph::new(3, &[(0, 1), (1, 2), (2, 0)])); // Triangle let e3 = flag(&Graph::new(3, &[])); // Independent set of size 3
// Definition of the optimization problem.
let pb = Problem::
// Write the correspondind SDP program in "goodman.sdpa". // This program can then be solved by CSDP. The answer would be 0.25. pb.write_sdpa("goodman").unwrap(); } ```
This library can currently do the following. * Generate list of flags from scratch. * Generate flag algebra operators and memoize them in files. * Compute in the flag algebra (multiplication, unlabeling) and add user-defined vectors. * Define, manipulate or amplify flag inequalities (for instance by multiplying an inequality by all flags). * Write problem in .spda format or directly run the CSDP solver. * Automatically eliminate unnecessary constraints (in a naive way). * It is generic: defining new specific class/subclass of flags boils down to implementing a Rust Trait. * Output flags, problems or certificates as html pages in (hopefully) human-readable format (provided that it has a reasonnable size).
This library is generic. To use a kind combinatorial objects as flags (e.g. graphs), it suffices to implement the Flag trait for the corresponding Rust datatype.
Currently, Flag is implemented for Graphs, Digraphs and edge-colored graphs with some fixed number of colors.
Beside implementing directly [Flag] for your own types, two mechanisms help
to define flag classes based on an existing flag class F.
* The Colored structure for defining vertex-colored flags.
If N is an integer identifier, Colored<F, N> is the type for flags of type F
where the vertices are further colored in N different colors.
Colored<F, N> automatically implement Flag when F does.
* The [SubClass] structure and
the [SubFlag] for classes that are subsets
of already defined classes.
This is usefull for instance for computing in triangle-free graphs flag algebra
without considering other graphs.
See the documentation page of [SubFlag] for more details.
See [Type], [Basis] and [QFlag].
The Type<F:Flag> structure identifies a
"type" σ in the sense of flag algebras (i.e. a completely labeled flag)
is represented by an object.
The Basis<F:Flag> structure corresponds to a couple (n, σ)
and identifies the set of σ-flags of size n.
The structure QFlag
License: GPL-3.0