[−][src]Crate flag_algebra
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.
Example
// Proving that in any graph, at least 1/4 of the triples // are triangles or independent sets. extern crate flag_algebra; use flag_algebra::*; use flag_algebra::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::<i64, _> { // Constraints ineqs: vec![total_sum_is_one(basis), flags_are_nonnegative(basis)], // Use all relevant Cauchy-Schwarz inequalities. cs: basis.all_cs(), // Minimize density of triangle plus density of independent of size 3. obj: k3 + e3, }; // 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(); }
Features
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).
Supported flags
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 typeF
where the vertices are further colored inN
different colors.Colored<F, N>
automatically implementFlag
whenF
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.
Re-exports
pub use crate::operator::Basis; |
pub use crate::operator::Savable; |
pub use crate::operator::Type; |
pub use crate::report::Html; |
pub use crate::sdp::Problem; |
Modules
density | Computing coefficients of a flag algebra operator. |
draw | |
expr | Expression of computations in the flag algebra for prettyprinting. |
flags | Implementations of flags. |
operator | Computing and stocking operators of the flag algebra. |
report | |
sdp | Create and manipulate semi-definite problems. |
sdpa |
Structs
FlagSolver | A higher level object to try several selectors on a problem |
Ineq | A set of bounds on elements of a flag algebra. |
IneqData | Contains the vector and the bound of one inequality in a flag algebra.
This inequality has the form |
IneqMeta | Contains informations about a set of inequalities of a flag algebra. |
QFlag | An element of a flag algebra. |
SubClass | A wrapper type for flags from a sub-class of flags. |
Traits
Flag | Trait for combinatorial objects that can be used as flags. |
SubFlag | Trait for defining a class of flag as a subset of an already defined class of flag. |
Functions
flag | Return the vector corresponding to the unlabeled flag |
flag_typed | Return the vector corresponding to the flag |
flags_are_nonnegative | Return the inequalities expressing that the flags of |
init_debug_log | Initialize the logs to be outputted to the console with detailed information. |
init_default_log | Initialize the logs to be outputted to the console. |
total_sum_is_one | Return the inequalities expressing that the sum of the flags of |