flag-algebra 0.4.0

An implementation of Razborov's flag algebras
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

//!A generic implementation of
//![flag algebras](http://people.cs.uchicago.edu/~razborov/files/flag.pdf).
//!
//! Flag algebras is a framework used to produce computer-assisted proofs of some inequalities in combinatorics, relying on Semi-Definite Programming.
//!
//!# Example
//!
//!```rust,no_run
//!// Proving that in any graph, at least 1/4 of the triples
//!// are triangles or independent sets.
//!use flag_algebra::*;
//!use flag_algebra::flags::Graph;
//!
//!// 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@Flag) trait for the corresponding Rust datatype.
//!
//! Currently, [Flag](trait@Flag) is implemented for [Graphs](struct@flags::Graph),
//! [Oriented graphs](struct@flags::OrientedGraph), [Directed graphs](struct@flags::DirectedGraph)
//! and [edge-colored graphs](struct@flags::CGraph) 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](struct@flags::Colored) structure for defining vertex-colored flags.
//! If `N` is an integer identifier, `Colored<F, N>` is the type for flags of type `F`
//! where the vertices are further colored in `N` different colors.
//! `Colored<F, N>` automatically implement `Flag` when `F` 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.
//! See the documentation page of [`SubFlag`] for more details.
//!
//!# Expressing elements of a flag algebra
//! See [Type], [Basis] and [`QFlag`].
//!
//! The `Type<F:Flag>` structure identifies a
//! "type" σ in the sense of flag algebras (i.e. a completely labeled flag)
//! is represented by an object.
//! The `Basis<F:Flag>` structure corresponds to a couple (n, σ)
//! and identifies the set of σ-flags of size n.
//! The structure `QFlag`

#![warn(
    missing_debug_implementations,
    missing_copy_implementations,
    trivial_casts,
    trivial_numeric_casts,
    unsafe_code,
    unstable_features,
    unused_import_braces,
    unused_qualifications,
    unused_labels,
    unused_results
)]

mod algebra;
pub use crate::algebra::*;

mod combinatorics;
mod density;
pub mod flags;
mod iterators;
pub mod operator;
pub mod tools;
pub use crate::operator::{Basis, Savable, Type};

mod expr;
pub mod sdp;
pub mod sdpa;
pub use crate::sdp::Problem;
pub use crate::tools::FlagSolver;

mod flag;
pub use crate::flag::*;

#[macro_use]
extern crate serde_derive;

// Feedback information in the library are sent using simplelog
// This logs require to be initialized
use simplelog::*;

/// Initialize the logs to be outputted to the console.
///
/// In order to be recorded, the logs need to be initialized via this function
/// or any initializer of the simplelog library
pub fn init_default_log() {
    let config = ConfigBuilder::new()
        .set_max_level(LevelFilter::Error)
        .set_target_level(LevelFilter::Off)
        .set_thread_level(LevelFilter::Off)
        .build();
    TermLogger::init(
        LevelFilter::Info,
        config,
        TerminalMode::Mixed,
        ColorChoice::Auto,
    )
    .unwrap();
}

/// Initialize the logs to be outputted to the console with detailed information.
///
/// In order to be recorded, the logs need to be initialized via this function
/// or any initializer of the simplelog library
pub fn init_debug_log() {
    let config = ConfigBuilder::new()
        .set_max_level(LevelFilter::Error)
        .set_target_level(LevelFilter::Off)
        .set_thread_level(LevelFilter::Off)
        .build();
    TermLogger::init(
        LevelFilter::Trace,
        config,
        TerminalMode::Mixed,
        ColorChoice::Auto,
    )
    .unwrap();
}