problemreductions/models/graph/

longest_circuit.rs

//! Longest Circuit problem implementation.
//!
//! The Longest Circuit problem asks for a simple circuit in a graph
//! that maximizes the total edge length.

use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
use crate::topology::{Graph, SimpleGraph};
use crate::traits::Problem;
use crate::types::{Max, WeightElement};
use num_traits::Zero;
use serde::{Deserialize, Serialize};
use std::collections::VecDeque;

inventory::submit! {
    ProblemSchemaEntry {
        name: "LongestCircuit",
        display_name: "Longest Circuit",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
            VariantDimension::new("weight", "i64", &["i64"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Find a simple circuit in a graph that maximizes total edge length",
        fields: LongestCircuitCreateSpec::FIELDS,
    }
}

/// The Longest Circuit problem.
///
/// Given an undirected graph `G = (V, E)` with positive edge lengths `l(e)`,
/// find a simple circuit in `G` that maximizes the total edge-length sum.
///
/// # Representation
///
/// Each edge is assigned a binary variable:
/// - `0`: edge is not in the circuit
/// - `1`: edge is in the circuit
///
/// A valid configuration must select edges that form exactly one connected
/// simple circuit using only edges from `graph`.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "LongestCircuitData<G, W>")]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>"))]
pub struct LongestCircuit<G, W: WeightElement> {
    graph: G,
    edge_lengths: Vec<W>,
}

#[derive(Deserialize)]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>"))]
struct LongestCircuitData<G, W: WeightElement> {
    graph: G,
    edge_lengths: Vec<W>,
}

impl<G, W> TryFrom<LongestCircuitData<G, W>> for LongestCircuit<G, W>
where
    G: Graph,
    W: WeightElement,
{
    type Error = crate::registry::ConstructionError;

    fn try_from(data: LongestCircuitData<G, W>) -> Result<Self, Self::Error> {
        Self::try_new(data.graph, data.edge_lengths)
    }
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct LongestCircuitCreateSpec {
    #[create(codec = "edge-list")]
    graph: Vec<(usize, usize)>,
    num_vertices: Option<usize>,
    #[create(codec = "comma-separated")]
    edge_weights: Option<Vec<i64>>,
}

impl TryFrom<LongestCircuitCreateSpec> for LongestCircuit<SimpleGraph, i64> {
    type Error = crate::registry::ConstructionError;

    fn try_from(spec: LongestCircuitCreateSpec) -> Result<Self, Self::Error> {
        let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
        let edge_lengths = spec
            .edge_weights
            .unwrap_or_else(|| vec![1; graph.num_edges()]);
        Self::try_new(graph, edge_lengths)
    }
}

fn simple_graph_from_create(
    edges: Vec<(usize, usize)>,
    num_vertices: Option<usize>,
) -> Result<SimpleGraph, crate::registry::ConstructionError> {
    if edges.is_empty() && num_vertices.is_none() {
        return Err("num_vertices is required for an empty graph"
            .to_string()
            .into());
    }
    for (index, &(u, v)) in edges.iter().enumerate() {
        if u == v {
            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
        }
    }
    let inferred = edges
        .iter()
        .flat_map(|&(u, v)| [u, v])
        .max()
        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
        .transpose()?
        .unwrap_or(0);
    let num_vertices = num_vertices.unwrap_or(inferred);
    if num_vertices < inferred {
        return Err(format!(
            "num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}"
        )
        .into());
    }
    Ok(SimpleGraph::new(num_vertices, edges))
}

impl<G: Graph, W: WeightElement> LongestCircuit<G, W> {
    /// Create a new LongestCircuit instance.
    ///
    /// # Panics
    ///
    /// Panics if the number of edge lengths does not match the graph's edge
    /// count, or if any edge length is non-positive.
    pub fn new(graph: G, edge_lengths: Vec<W>) -> Self {
        Self::try_new(graph, edge_lengths).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(graph: G, edge_lengths: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
        Self::check_weights(&graph, &edge_lengths)?;
        Ok(Self {
            graph,
            edge_lengths,
        })
    }

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

    /// Get the edge lengths.
    pub fn edge_lengths(&self) -> &[W] {
        &self.edge_lengths
    }

    /// Replace the edge lengths.
    pub fn set_lengths(&mut self, edge_lengths: Vec<W>) {
        Self::check_weights(&self.graph, &edge_lengths).unwrap_or_else(|error| panic!("{error}"));
        self.edge_lengths = edge_lengths;
    }

    fn check_weights(graph: &G, weights: &[W]) -> Result<(), crate::registry::ConstructionError> {
        if weights.len() != graph.num_edges() {
            return Err(crate::registry::ConstructionError::length_mismatch(
                "weights",
                weights.len(),
                graph.num_edges(),
            ));
        }
        if !weights
            .iter()
            .all(|weight| weight.to_sum() > W::Sum::zero())
        {
            return Err("All edge lengths must be positive (> 0)".into());
        }
        Ok(())
    }

    /// Replace the edge lengths via the generic weight-management naming.
    pub fn set_weights(&mut self, weights: Vec<W>) {
        self.set_lengths(weights);
    }

    /// Get the edge lengths as a cloned vector.
    pub fn weights(&self) -> Vec<W> {
        self.edge_lengths.clone()
    }

    /// Smallest h >= 1 with every edge length strictly below 2^h.
    pub fn max_length_bits(&self) -> u64 {
        crate::types::max_numeric_magnitude_bits(
            self.edge_lengths.iter().map(|length| length.to_sum()),
        )
    }

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

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

    /// Check if the problem uses a non-unit weight type.
    pub fn is_weighted(&self) -> bool {
        !W::IS_UNIT
    }

    /// Check whether a configuration is a valid simple circuit.
    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
        is_simple_circuit(&self.graph, config)
    }
}

impl<G, W> Problem for LongestCircuit<G, W>
where
    G: Graph + crate::variant::VariantParam,
    W: WeightElement + crate::variant::VariantParam,
{
    const NAME: &'static str = "LongestCircuit";
    type Solution = Vec<bool>;
    type Value = Max<W::Sum>;

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

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

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
        if config.len() != self.graph.num_edges() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "edge-selection length does not match the graph".into(),
            ));
        }
        Ok({
            if !is_simple_circuit(&self.graph, config) {
                return Ok(Max(None));
            }
            let mut total = W::Sum::zero();
            for (idx, &selected) in config.iter().enumerate() {
                if selected {
                    total = W::checked_add_to_sum(
                        total,
                        self.edge_lengths[idx].to_sum(),
                        "summing circuit edge lengths",
                    )?;
                }
            }
            Max(Some(total))
        })
    }
}

impl<G, W> crate::solvers::BruteForceProblem for LongestCircuit<G, W>
where
    G: Graph + crate::variant::VariantParam,
    W: WeightElement + crate::variant::VariantParam,
{
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.graph.num_edges()]
    }
}

/// Check whether a binary edge-selection encodes exactly one simple circuit.
pub(crate) fn is_simple_circuit<G: Graph>(graph: &G, config: &[bool]) -> bool {
    if config.len() != graph.num_edges() {
        return false;
    }

    let edges = graph.edges();
    let n = graph.num_vertices();
    let mut degree = vec![0usize; n];
    let mut adjacency = vec![Vec::new(); n];
    let mut selected_count = 0usize;
    let mut start = None;

    for (idx, &selected) in config.iter().enumerate() {
        if !selected {
            continue;
        }
        let (u, v) = edges[idx];
        degree[u] += 1;
        degree[v] += 1;
        adjacency[u].push(v);
        adjacency[v].push(u);
        selected_count += 1;
        if start.is_none() {
            start = Some(u);
        }
    }

    if selected_count < 3 {
        return false;
    }

    let selected_vertices: Vec<usize> = degree
        .iter()
        .enumerate()
        .filter_map(|(vertex, &deg)| (deg > 0).then_some(vertex))
        .collect();

    if selected_vertices.is_empty() || selected_vertices.iter().any(|&vertex| degree[vertex] != 2) {
        return false;
    }

    let start = match start {
        Some(vertex) => vertex,
        None => return false,
    };

    let mut visited = vec![false; n];
    let mut queue = VecDeque::new();
    visited[start] = true;
    queue.push_back(start);
    let mut visited_selected_vertices = 0usize;

    while let Some(vertex) = queue.pop_front() {
        visited_selected_vertices += 1;
        for &neighbor in &adjacency[vertex] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }

    visited_selected_vertices == selected_vertices.len()
}

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

crate::impl_random_generate!(LongestCircuit<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
    let graph = spec.graph()?;
    let lengths = vec![1; graph.num_edges()];
    Ok(LongestCircuit::new(graph, lengths))
});

crate::declare_variants! {
    default LongestCircuit<SimpleGraph, i64> => "2^num_vertices * num_vertices^2" create LongestCircuitCreateSpec random,
}

crate::register_brute_force! {
    LongestCircuit<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

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

crate::decision_problem_meta!(LongestCircuit<SimpleGraph, i64>, "DecisionLongestCircuit");
crate::register_decision_variant!(
    LongestCircuit<SimpleGraph, i64>, "DecisionLongestCircuit", "2^num_vertices * num_vertices^2", &[],
    "Does a feasible solution have objective value >= the bound?",
    category: crate::registry::ProblemCategory::Graph,
    dims: [
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
            VariantDimension::new("weight", "i64", &["i64"]),
        ],
    fields: [
        crate::registry::FieldInfo { name: "graph", type_name: "Vec<(usize,usize)>", description: "Graph edges as comma-separated vertex pairs." },
        crate::registry::FieldInfo { name: "num_vertices", type_name: "usize", description: "Number of vertices, including isolated vertices." },
        crate::registry::FieldInfo { name: "edge_weights", type_name: "Vec<i64>", description: "Weights for each edge in graph order." },
        crate::registry::FieldInfo { name: "bound", type_name: "i64", description: "Accept objective values >= this bound" },
    ],
    decode: |_, indices: Vec<usize>| crate::config::config_to_bits(&indices)
);

#[cfg(feature = "example-db")]
pub(crate) fn decision_canonical_rule_example_specs(
) -> Vec<crate::example_db::specs::RuleExampleSpec> {
    vec![crate::example_db::specs::RuleExampleSpec {
        id: "decision_longest_circuit_to_longest_circuit",
        build: || {
            let source = crate::models::decision::Decision::new(
                LongestCircuit::new(
                    SimpleGraph::new(
                        6,
                        vec![
                            (0, 1),
                            (1, 2),
                            (2, 3),
                            (3, 4),
                            (4, 5),
                            (5, 0),
                            (0, 3),
                            (1, 4),
                            (2, 5),
                            (3, 5),
                        ],
                    ),
                    vec![3, 2, 4, 1, 5, 2, 3, 2, 1, 2],
                ),
                18,
            );
            let witness = serde_json::json!(vec![
                true, false, true, false, true, false, true, true, true, false
            ]);
            crate::example_db::specs::rule_example_with_witness::<_, LongestCircuit<SimpleGraph, i64>>(
                source,
                crate::export::SolutionPair {
                    source_config: witness.clone(),
                    target_config: witness,
                },
            )
        },
    }]
}