flag_algebra/
lib.rs

1//!A generic implementation of
2//![flag algebras](http://people.cs.uchicago.edu/~razborov/files/flag.pdf).
3//!
4//! Flag algebras is a framework used to produce computer-assisted proofs of some inequalities in combinatorics, relying on Semi-Definite Programming.
5//!
6//!# Example
7//!
8//!```rust,no_run
9//!// Proving that in any graph, at least 1/4 of the triples
10//!// are triangles or independent sets.
11//!use flag_algebra::*;
12//!use flag_algebra::flags::Graph;
13//!
14//!// Work on the graphs of size 3.
15//!let basis = Basis::new(3);
16//!
17//!// Define useful flags.
18//!let k3 = flag(&Graph::new(3, &[(0, 1), (1, 2), (2, 0)])); // Triangle
19//!let e3 = flag(&Graph::new(3, &[])); // Independent set of size 3
20//!
21//!// Definition of the optimization problem.
22//!let pb = Problem::<i64, _> {
23//!     // Constraints
24//!    ineqs: vec![total_sum_is_one(basis), flags_are_nonnegative(basis)],
25//!     // Use all relevant Cauchy-Schwarz inequalities.
26//!     cs: basis.all_cs(),
27//!     // Minimize density of triangle plus density of independent of size 3.
28//!     obj: k3 + e3,
29//! };
30//!
31//! // Write the correspondind SDP program in "goodman.sdpa".
32//! // This program can then be solved by CSDP. The answer would be 0.25.
33//! pb.write_sdpa("goodman").unwrap();
34//!```
35//!# Features
36//! This library can currently do the following.
37//! * Generate list of flags from scratch.
38//! * Generate flag algebra operators and memoize them in files.
39//! * Compute in the flag algebra (multiplication, unlabeling) and add user-defined vectors.
40//! * Define, manipulate or amplify flag inequalities (for instance by multiplying an inequality by all flags).
41//! * Write problem in .spda format or directly run the CSDP solver.
42//! * Automatically eliminate unnecessary constraints (in a naive way).
43//! * It is generic:
44//! defining new specific class/subclass of flags boils down to implementing a Rust Trait.
45//! * Output flags, problems or certificates as html pages
46//! in (hopefully) human-readable format (provided that it has a reasonnable size).
47//!
48//!# Supported flags
49//! This library is generic.
50//! To use a kind combinatorial objects as flags (e.g. graphs), it suffices to
51//! implement the [Flag](trait@Flag) trait for the corresponding Rust datatype.
52//!
53//! Currently, [Flag](trait@Flag) is implemented for [Graphs](struct@flags::Graph),
54//! [Oriented graphs](struct@flags::OrientedGraph), [Directed graphs](struct@flags::DirectedGraph)
55//! and [edge-colored graphs](struct@flags::CGraph) with some fixed number of colors.
56//!
57//! Beside implementing directly [Flag] for your own types, two mechanisms help
58//! to define flag classes based on an existing flag class `F`.
59//! * The [Colored](struct@flags::Colored) structure for defining vertex-colored flags.
60//! If `N` is an integer identifier, `Colored<F, N>` is the type for flags of type `F`
61//! where the vertices are further colored in `N` different colors.
62//! `Colored<F, N>` automatically implement `Flag` when `F` does.
63//! * The [`SubClass`] structure and
64//! the [`SubFlag`] for classes that are subsets
65//! of already defined classes.
66//! This is usefull for instance for computing in triangle-free graphs flag algebra
67//! without considering other graphs.
68//! See the documentation page of [`SubFlag`] for more details.
69//!
70//!# Expressing elements of a flag algebra
71//! See [Type], [Basis] and [`QFlag`].
72//!
73//! The `Type<F:Flag>` structure identifies a
74//! "type" σ in the sense of flag algebras (i.e. a completely labeled flag)
75//! is represented by an object.
76//! The `Basis<F:Flag>` structure corresponds to a couple (n, σ)
77//! and identifies the set of σ-flags of size n.
78//! The structure `QFlag`
79
80#![warn(
81    missing_debug_implementations,
82    missing_copy_implementations,
83    trivial_casts,
84    trivial_numeric_casts,
85    unsafe_code,
86    unstable_features,
87    unused_import_braces,
88    unused_qualifications,
89    unused_labels,
90    unused_results
91)]
92
93mod algebra;
94pub use crate::algebra::*;
95
96mod combinatorics;
97mod density;
98pub mod flags;
99mod iterators;
100pub mod operator;
101pub mod tools;
102pub use crate::operator::{Basis, Savable, Type};
103
104mod expr;
105pub mod sdp;
106pub mod sdpa;
107pub use crate::sdp::Problem;
108pub use crate::tools::FlagSolver;
109
110mod flag;
111pub use crate::flag::*;
112
113#[macro_use]
114extern crate serde_derive;
115
116// Feedback information in the library are sent using simplelog
117// This logs require to be initialized
118use simplelog::*;
119
120/// Initialize the logs to be outputted to the console.
121///
122/// In order to be recorded, the logs need to be initialized via this function
123/// or any initializer of the simplelog library
124pub fn init_default_log() {
125    let config = ConfigBuilder::new()
126        .set_max_level(LevelFilter::Error)
127        .set_target_level(LevelFilter::Off)
128        .set_thread_level(LevelFilter::Off)
129        .build();
130    TermLogger::init(
131        LevelFilter::Info,
132        config,
133        TerminalMode::Mixed,
134        ColorChoice::Auto,
135    )
136    .unwrap();
137}
138
139/// Initialize the logs to be outputted to the console with detailed information.
140///
141/// In order to be recorded, the logs need to be initialized via this function
142/// or any initializer of the simplelog library
143pub fn init_debug_log() {
144    let config = ConfigBuilder::new()
145        .set_max_level(LevelFilter::Error)
146        .set_target_level(LevelFilter::Off)
147        .set_thread_level(LevelFilter::Off)
148        .build();
149    TermLogger::init(
150        LevelFilter::Trace,
151        config,
152        TerminalMode::Mixed,
153        ColorChoice::Auto,
154    )
155    .unwrap();
156}
flag_algebra/lib.rs

flag_algebra/
lib.rs
