problemreductions/models/graph/

partition_into_triangles.rs

//! Partition Into Triangles problem implementation.
//!
//! Given a graph G = (V, E) where |V| = 3q, determine whether V can be
//! partitioned into q triples, each forming a triangle (K3) in G.

use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
use crate::topology::{Graph, SimpleGraph};
use crate::traits::Problem;
use crate::variant::VariantParam;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "PartitionIntoTriangles",
        display_name: "Partition Into Triangles",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Partition vertices into triangles (K3 subgraphs)",
        fields: &[
            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E) with |V| divisible by 3" },
        ],
    }
}

/// The Partition Into Triangles problem.
///
/// Given a graph G = (V, E) where |V| = 3q, determine whether V can be
/// partitioned into q triples, each forming a triangle (K3) in G.
///
/// # Type Parameters
///
/// * `G` - Graph type (e.g., SimpleGraph)
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::PartitionIntoTriangles;
/// use problemreductions::topology::SimpleGraph;
/// use problemreductions::{Problem, BruteForce};
///
/// // Triangle graph: 3 vertices forming a single triangle
/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
/// let problem = PartitionIntoTriangles::new(graph);
///
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
pub struct PartitionIntoTriangles<G> {
    /// The underlying graph.
    graph: G,
}

impl<G: Graph> PartitionIntoTriangles<G> {
    /// Create a new Partition Into Triangles problem from a graph.
    ///
    /// # Panics
    /// Panics if the number of vertices is not divisible by 3.
    pub fn new(graph: G) -> Self {
        assert!(
            graph.num_vertices().is_multiple_of(3),
            "Number of vertices ({}) must be divisible by 3",
            graph.num_vertices()
        );
        Self { graph }
    }

    /// Get a reference to the underlying graph.
    pub fn graph(&self) -> &G {
        &self.graph
    }

    /// Get the number of vertices in the underlying graph.
    pub fn num_vertices(&self) -> usize {
        self.graph.num_vertices()
    }

    /// Get the number of edges in the underlying graph.
    pub fn num_edges(&self) -> usize {
        self.graph.num_edges()
    }
}

impl<G> Problem for PartitionIntoTriangles<G>
where
    G: Graph + VariantParam,
{
    const NAME: &'static str = "PartitionIntoTriangles";
    type Solution = Vec<usize>;
    type Value = crate::types::Or;

    crate::problem_parameters![("num_vertices", num_vertices),];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![G]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        Ok({
            crate::types::Or({
                let n = self.graph.num_vertices();
                let q = n / 3;

                // Check config length
                if config.len() != n {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "partition assignment length does not match the graph vertices".into(),
                    ));
                }

                // Check all values are in range [0, q)
                if config.iter().any(|&c| c >= q) {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "partition assignment contains an out-of-range group".into(),
                    ));
                }

                // Count vertices per group
                let mut counts = vec![0usize; q];
                for &c in config {
                    counts[c] += 1;
                }

                // Each group must have exactly 3 vertices
                if counts.iter().any(|&c| c != 3) {
                    return Ok(crate::types::Or(false));
                }

                // Build per-group vertex lists in a single pass over config.
                let mut group_verts = vec![[0usize; 3]; q];
                let mut group_pos = vec![0usize; q];

                for (v, &g) in config.iter().enumerate() {
                    let pos = group_pos[g];
                    group_verts[g][pos] = v;
                    group_pos[g] = pos + 1;
                }

                // Check each group forms a triangle
                for verts in &group_verts {
                    if !self.graph.has_edge(verts[0], verts[1]) {
                        return Ok(crate::types::Or(false));
                    }
                    if !self.graph.has_edge(verts[0], verts[2]) {
                        return Ok(crate::types::Or(false));
                    }
                    if !self.graph.has_edge(verts[1], verts[2]) {
                        return Ok(crate::types::Or(false));
                    }
                }

                true
            })
        })
    }
}

impl<G> crate::solvers::BruteForceProblem for PartitionIntoTriangles<G>
where
    G: Graph + VariantParam,
{
    fn dimensions(&self) -> Vec<usize> {
        let q = self.graph.num_vertices() / 3;
        vec![q; self.graph.num_vertices()]
    }
}

crate::declare_variants! {
    default PartitionIntoTriangles<SimpleGraph> => "2^num_vertices",
}

crate::register_brute_force! {
    PartitionIntoTriangles<SimpleGraph>,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "partition_into_triangles_simplegraph",
        instance: Box::new(PartitionIntoTriangles::new(SimpleGraph::new(
            6,
            vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (0, 3)],
        ))),
        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/partition_into_triangles.rs"]
mod tests;