Crate flag_algebra

An 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;
use sdp::Problem;

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();
}

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	Example 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 self.flag ≥ self.bound. Expression recording how the left sides where constructed.
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 object 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 f.
flag_typed	Return the vector corresponding to the flag f with type_size labeled vertices.
flags_are_nonnegative	Return the inequalities expressing that the flags of basis are larger than zero.
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 basis is equal to one.