#flag #algebra #graph #combinatorics

flag-algebra

An implementation of Razborov’s flag algebras

7 releases

✓ Uses Rust 2018 edition

new 0.1.6 Dec 4, 2019
0.1.5 Nov 20, 2019
0.1.4 Jun 26, 2019
0.1.3 Jan 24, 2019

#80 in Math

Download history 37/week @ 2019-08-21 18/week @ 2019-08-28 21/week @ 2019-09-04 12/week @ 2019-09-11 39/week @ 2019-09-18 15/week @ 2019-09-25 10/week @ 2019-10-02 10/week @ 2019-10-16 12/week @ 2019-10-23 10/week @ 2019-10-30 2/week @ 2019-11-06 11/week @ 2019-11-13 24/week @ 2019-11-20 19/week @ 2019-11-27

57 downloads per month

GPL-3.0 license

125KB
3.5K SLoC

flag-algebra

An implementation of flag algebras.

Example

extern crate flag_algebra;

use flag_algebra::*;
use flags::Graph;
use operator::Basis;
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.
   pb.write_sdpa("goodman").unwrap();
}

License: GPL-3.0

Dependencies

~4.5MB
~93K SLoC