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, Solver, 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.find_witness(&problem);
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: 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<'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 Value = Or

The evaluation value type.

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

Returns variant attributes derived from type parameters.

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

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Or

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

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) -> Self::Result

Reduce this problem to the target problem type.

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

type Result = Reduction3SATToMonochromaticTriangle

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

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.

impl DeclaredVariant for MonochromaticTriangle<SimpleGraph>