Module template 

Generic graph problem template.

This module provides a template for defining binary graph problems with minimal boilerplate. Instead of writing ~400 lines per problem, you can define a new graph problem in ~15 lines by implementing GraphConstraint.

Overview

Binary graph problems share a common structure:

• Each vertex can be selected (1) or not selected (0)
• Edges impose constraints on which pairs can be simultaneously selected
• The objective is to maximize or minimize the total weight of selected vertices

This template captures this pattern via:

• GraphConstraint - Trait defining problem-specific semantics
• GraphProblem<C, W> - Generic struct implementing all standard traits

Quick Start

use problemreductions::models::graph::{GraphConstraint, GraphProblem};
use problemreductions::topology::SimpleGraph;
use problemreductions::registry::GraphSubcategory;
use problemreductions::types::EnergyMode;

// Step 1: Define the constraint
#[derive(Debug, Clone, Copy)]
pub struct MyConstraint;

impl GraphConstraint for MyConstraint {
    const NAME: &'static str = "My Problem";
    const DESCRIPTION: &'static str = "Description of my problem";
    const ENERGY_MODE: EnergyMode = EnergyMode::LargerSizeIsBetter;
    const SUBCATEGORY: GraphSubcategory = GraphSubcategory::Independent;

    fn edge_constraint_spec() -> [bool; 4] {
        // [neither, only_v, only_u, both] selected
        [true, true, true, false]  // At most one endpoint
    }
}

// Step 2: Create a type alias (G defaults to SimpleGraph, W defaults to i32)
pub type MyProblem<G = SimpleGraph, W = i32> = GraphProblem<MyConstraint, G, W>;

// Step 3: Use it!
let problem: MyProblem = MyProblem::new(3, vec![(0, 1), (1, 2)]);

Built-in Problem Types

Type Alias	Constraint	Energy Mode	Edge Spec
IndependentSetT	At most one selected	Maximize	[T,T,T,F]
VertexCoverT	At least one selected	Minimize	[F,T,T,T]
CliqueT	For complement graph	Maximize	[T,T,T,F]

Edge Constraint Specification

The edge_constraint_spec method returns a 4-element array [bool; 4] indexed by (u_selected * 2 + v_selected):

Index	u	v	Meaning
0	0	0	Neither endpoint selected
1	0	1	Only v selected
2	1	0	Only u selected
3	1	1	Both endpoints selected

Common patterns:

• Independent Set: [true, true, true, false] - at most one selected
• Vertex Cover: [false, true, true, true] - at least one selected
• Perfect Matching: Define on edge graph with exactly one selected

Structs

CliqueConstraint

Constraint for the Clique problem.

GraphProblem

A generic graph problem parameterized by constraint type, graph type, and weight type.

IndependentSetConstraint

Constraint for the Independent Set problem.

VertexCoverConstraint

Constraint for the Vertex Cover problem.

Traits

GraphConstraint

Trait defining the constraint semantics for a binary graph problem.

Type Aliases

CliqueT

Clique problem using the generic template.

IndependentSetT

Independent Set problem using the generic template.

VertexCoverT

Vertex Cover problem using the generic template.