#flag #algebra #graph #combinatorics

flag-algebra

An implementation of Razborov’s flag algebras

7 releases

✓ Uses Rust 2018 edition

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

#95 in Math

Download history 7/week @ 2020-03-15 36/week @ 2020-03-22 3/week @ 2020-03-29 22/week @ 2020-04-05 28/week @ 2020-04-12 1/week @ 2020-04-26 7/week @ 2020-05-03 8/week @ 2020-05-24 22/week @ 2020-05-31 7/week @ 2020-06-14 8/week @ 2020-06-28

58 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
~90K SLoC