Trait GraphConstraint 

pub trait GraphConstraint:
    Clone
    + Send
    + Sync
    + 'static {
    const NAME: &'static str;
    const DESCRIPTION: &'static str;
    const ENERGY_MODE: EnergyMode;
    const SUBCATEGORY: GraphSubcategory;
    const ALIASES: &'static [&'static str] = _;
    const REDUCES_FROM: Option<&'static str> = None;

    // Required method
    fn edge_constraint_spec() -> [bool; 4];

    // Provided methods
    fn is_edge_satisfied(u_selected: bool, v_selected: bool) -> bool { ... }
    fn problem_info() -> ProblemInfo { ... }
    fn category() -> ProblemCategory { ... }
}

Trait defining the constraint semantics for a binary graph problem.

Implement this trait to define a new graph problem type. The trait specifies how edges constrain the selection of vertices and what the optimization objective is.

Example

pub struct IndependentSetConstraint;

impl GraphConstraint for IndependentSetConstraint {
    const NAME: &'static str = "Independent Set";
    const DESCRIPTION: &'static str = "Find maximum weight set of non-adjacent vertices";
    const ENERGY_MODE: EnergyMode = EnergyMode::LargerSizeIsBetter;
    const SUBCATEGORY: GraphSubcategory = GraphSubcategory::Independent;

    fn edge_constraint_spec() -> [bool; 4] {
        [true, true, true, false]  // (0,0), (0,1), (1,0) OK; (1,1) invalid
    }
}

Required Associated Constants

const NAME: &'static str

The canonical name of this problem.

const DESCRIPTION: &'static str

Brief description of the problem.

const ENERGY_MODE: EnergyMode

Whether to maximize or minimize the objective.

const SUBCATEGORY: GraphSubcategory

The graph subcategory this problem belongs to.

Provided Associated Constants

const ALIASES: &'static [&'static str] = _

Alternative names for this problem (default: empty).

const REDUCES_FROM: Option<&'static str> = None

The problem this canonically reduces from (default: None).

Required Methods

fn edge_constraint_spec() -> [bool; 4]

The edge constraint specification.

Returns a 4-element array representing which (u_selected, v_selected) combinations are valid for an edge (u, v):

• Index 0: (0, 0) - neither endpoint selected
• Index 1: (0, 1) - only v selected
• Index 2: (1, 0) - only u selected
• Index 3: (1, 1) - both endpoints selected

Provided Methods

fn is_edge_satisfied(u_selected: bool, v_selected: bool) -> bool

Check if an edge is satisfied given endpoint selection states.

Default implementation uses edge_constraint_spec().

fn problem_info() -> ProblemInfo

Get the problem info for this constraint type.

fn category() -> ProblemCategory

Get the problem category.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl GraphConstraint for CliqueConstraint

const NAME: &'static str = "Clique"

const DESCRIPTION: &'static str = "Find a maximum clique (complete subgraph)"

const ENERGY_MODE: EnergyMode = EnergyMode::LargerSizeIsBetter

const SUBCATEGORY: GraphSubcategory = GraphSubcategory::Independent

const ALIASES: &'static [&'static str]

const REDUCES_FROM: Option<&'static str>

impl GraphConstraint for IndependentSetConstraint

const NAME: &'static str = "Independent Set"

const DESCRIPTION: &'static str = "Find a maximum weight set of non-adjacent vertices"

const ENERGY_MODE: EnergyMode = EnergyMode::LargerSizeIsBetter

const SUBCATEGORY: GraphSubcategory = GraphSubcategory::Independent

const ALIASES: &'static [&'static str]

const REDUCES_FROM: Option<&'static str>

impl GraphConstraint for VertexCoverConstraint

const NAME: &'static str = "Vertex Cover"

const DESCRIPTION: &'static str = "Find a minimum weight set of vertices covering all edges"

const ENERGY_MODE: EnergyMode = EnergyMode::SmallerSizeIsBetter

const SUBCATEGORY: GraphSubcategory = GraphSubcategory::Covering

const ALIASES: &'static [&'static str]

const REDUCES_FROM: Option<&'static str>