Module graph 

Graph-based optimization problems.

This module contains NP-hard problems defined on graphs:

• IndependentSet: Maximum weight independent set
• MaximalIS: Maximal independent set
• VertexCovering: Minimum weight vertex cover
• DominatingSet: Minimum dominating set
• MaxCut: Maximum cut on weighted graphs
• Coloring: K-vertex coloring
• Matching: Maximum weight matching

Using the Template

New graph problems can be defined using the GraphProblem template by implementing the GraphConstraint trait:

use problemreductions::models::graph::{GraphProblem, GraphConstraint};

// Define a new graph problem constraint
struct MyConstraint;
impl GraphConstraint for MyConstraint {
    // ... implement required methods
}

// Create a type alias for convenience
type MyProblem<W = i32> = GraphProblem<MyConstraint, W>;

Re-exports

pub use template::CliqueConstraint;

pub use template::CliqueT;

pub use template::GraphConstraint;

pub use template::GraphProblem;

pub use template::IndependentSetConstraint;

pub use template::IndependentSetT;

pub use template::VertexCoverConstraint;

pub use template::VertexCoverT;

Modules

template

Generic graph problem template.

Structs

Coloring

The Graph K-Coloring problem.

DominatingSet

The Dominating Set problem.

IndependentSet

The Independent Set problem.

Matching

The Maximum Matching problem.

MaxCut

The Maximum Cut problem.

MaximalIS

The Maximal Independent Set problem.

VertexCovering

The Vertex Covering problem.

Functions

cut_size

Compute the cut size for a given partition.

is_dominating_set

Check if a set of vertices is a dominating set.

is_independent_set

Check if a set of vertices forms an independent set.

is_matching

Check if a selection of edges forms a valid matching.

is_maximal_independent_set

Check if a set is a maximal independent set.

is_valid_coloring

Check if a coloring is valid for a graph.

is_vertex_cover

Check if a set of vertices forms a vertex cover.