Struct MonochromaticTriangle 

pub struct MonochromaticTriangle<G> { /* private fields */ }

The Monochromatic Triangle problem.

Given a graph G = (V, E), determine whether the edges of G can be 2-colored so that no triangle (three mutually adjacent vertices) has all three edges the same color.

Each configuration entry corresponds to an edge (in the order returned by graph.edges()), with value 0 or 1 representing the two colors.

Type Parameters

• G - Graph type (e.g., SimpleGraph)

Example

use problemreductions::models::graph::MonochromaticTriangle;
use problemreductions::topology::SimpleGraph;
use problemreductions::{Problem, BruteForce};

// K4: complete graph on 4 vertices
let graph = SimpleGraph::new(4, vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]);
let problem = MonochromaticTriangle::new(graph);

let solver = BruteForce::new();
let solution = solver.solve(&problem).unwrap();
assert!(solution.is_some());

Implementations

impl<G: Graph> MonochromaticTriangle<G>

pub fn new(graph: G) -> Self

Create a new Monochromatic Triangle instance.

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn num_vertices(&self) -> usize

Get the number of vertices in the underlying graph.

pub fn num_edges(&self) -> usize

Get the number of edges in the underlying graph.

pub fn triangles(&self) -> &[[usize; 3]]

Get the precomputed list of triangles (as edge-index triples).

pub fn num_triangles(&self) -> usize

Get the number of triangles in the graph.

pub fn edge_list(&self) -> &[(usize, usize)]

Get the ordered edge list.

Trait Implementations

impl<G> BruteForceProblem for MonochromaticTriangle<G>

where G: Graph + VariantParam,

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl<G: Clone> Clone for MonochromaticTriangle<G>

fn clone(&self) -> MonochromaticTriangle<G>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G: Debug> Debug for MonochromaticTriangle<G>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for MonochromaticTriangle<SimpleGraph>

impl<'de, G> Deserialize<'de> for MonochromaticTriangle<G>

where G: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<G> Problem for MonochromaticTriangle<G>

where G: Graph + VariantParam,

const NAME: &'static str = "MonochromaticTriangle"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<bool>

Mathematical witness type for this problem.

type Value = Or

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn evaluate(&self, config: &Self::Solution) -> Result<Or, EvaluationError>

Evaluate the problem on a solution.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for MonochromaticTriangle<SimpleGraph>

type Result = ReductionMonochromaticTriangleToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<MonochromaticTriangle<SimpleGraph>> for KSatisfiability<K3>

type Result = Reduction3SATToMonochromaticTriangle

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl<G> Serialize for MonochromaticTriangle<G>

where G: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.