problemreductions/models/graph/

min_max_multicenter.rs

//! Min-Max Multicenter (vertex p-center) problem implementation.
//!
//! The vertex p-center problem asks for K centers on vertices of a graph that
//! minimize the maximum weighted distance from any vertex to its nearest center.

use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
use crate::topology::{Graph, SimpleGraph};
use crate::traits::Problem;
use crate::types::{Min, One, WeightElement};
use num_traits::Zero;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "MinMaxMulticenter",
        display_name: "Min-Max Multicenter",
        aliases: &["pCenter"],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
            VariantDimension::new("weight", "i64", &["i64", "One"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Find K centers minimizing the maximum weighted distance from any vertex to its nearest center (vertex p-center)",
        fields: MinMaxMulticenterI64CreateSpec::FIELDS,
    }
}

/// The Min-Max Multicenter (vertex p-center) problem.
///
/// Given a graph G = (V, E) with vertex weights w(v) and edge lengths l(e),
/// and a number K of centers to place, find a subset P of K vertices (centers)
/// that minimizes max_{v in V} w(v) * d(v, P),
/// where d(v, P) is the shortest-path distance from v to the nearest center.
///
/// # Type Parameters
///
/// * `G` - The graph type (e.g., `SimpleGraph`)
/// * `W` - The weight/length type (e.g., `i64`)
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::MinMaxMulticenter;
/// use problemreductions::topology::SimpleGraph;
/// use problemreductions::{Problem, BruteForce};
///
/// // Hexagonal-like graph: 6 vertices, 7 edges, unit weights/lengths, K=2
/// let graph = SimpleGraph::new(6, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 5), (1, 4)]);
/// let problem = MinMaxMulticenter::new(graph, vec![1i64; 6], vec![1i64; 7], 2);
///
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "MinMaxMulticenterData<G, W>")]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>"))]
pub struct MinMaxMulticenter<G, W: WeightElement> {
    /// The underlying graph.
    graph: G,
    /// Non-negative weight for each vertex.
    vertex_weights: Vec<W>,
    /// Non-negative length for each edge (in edge index order).
    edge_lengths: Vec<W>,
    /// Number of centers to place.
    k: usize,
}

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

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

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

macro_rules! min_max_multicenter_create_spec {
    ($name:ident, $weight:ty, $one:expr $(, $weights:ident, $edge_weights:ident)?) => {
        #[derive(Debug, Deserialize, crate::CreateSpec)]
        struct $name {
            #[create(codec = "edge-list")]
            graph: Vec<(usize, usize)>,
            num_vertices: Option<usize>,
            $(
            #[create(codec = "comma-separated")]
            $weights: Option<Vec<$weight>>,
            )?
            $(
            #[create(codec = "comma-separated")]
            $edge_weights: Option<Vec<$weight>>,
            )?
            k: usize,
        }

        impl TryFrom<$name> for MinMaxMulticenter<SimpleGraph, $weight> {
            type Error = crate::registry::ConstructionError;

            fn try_from(spec: $name) -> Result<Self, Self::Error> {
                let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
                let vertex_weights = { $(if let Some(value) = spec.$weights { value } else)? { vec![$one; graph.num_vertices()] } };
                let edge_lengths = { $(if let Some(value) = spec.$edge_weights { value } else)? { vec![$one; graph.num_edges()] } };
                Self::try_new(graph, vertex_weights, edge_lengths, spec.k)
            }
        }
    };
}

min_max_multicenter_create_spec!(
    MinMaxMulticenterI64CreateSpec,
    i64,
    1,
    weights,
    edge_weights
);
min_max_multicenter_create_spec!(MinMaxMulticenterOneCreateSpec, One, One);

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> MinMaxMulticenter<G, W> {
    /// Create a MinMaxMulticenter problem.
    ///
    /// # Panics
    /// - If `vertex_weights.len() != graph.num_vertices()`
    /// - If `edge_lengths.len() != graph.num_edges()`
    /// - If any vertex weight or edge length is negative
    /// - If `k == 0` or `k > graph.num_vertices()`
    pub fn new(graph: G, vertex_weights: Vec<W>, edge_lengths: Vec<W>, k: usize) -> Self {
        Self::try_new(graph, vertex_weights, edge_lengths, k)
            .unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        graph: G,
        vertex_weights: Vec<W>,
        edge_lengths: Vec<W>,
        k: usize,
    ) -> Result<Self, crate::registry::ConstructionError> {
        if vertex_weights.len() != graph.num_vertices() {
            return Err(crate::registry::ConstructionError::length_mismatch(
                "vertex_weights",
                vertex_weights.len(),
                graph.num_vertices(),
            ));
        }
        if edge_lengths.len() != graph.num_edges() {
            return Err(crate::registry::ConstructionError::length_mismatch(
                "edge_lengths",
                edge_lengths.len(),
                graph.num_edges(),
            ));
        }
        let zero = W::Sum::zero();
        if !vertex_weights
            .iter()
            .all(|weight| weight.to_sum() >= zero.clone())
        {
            return Err("vertex_weights must be non-negative".into());
        }
        if !edge_lengths
            .iter()
            .all(|length| length.to_sum() >= zero.clone())
        {
            return Err("edge_lengths must be non-negative".into());
        }
        if k == 0 {
            return Err("k must be positive".into());
        }
        if k > graph.num_vertices() {
            return Err("k must not exceed num_vertices".into());
        }
        Ok(Self {
            graph,
            vertex_weights,
            edge_lengths,
            k,
        })
    }

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

    /// Get a reference to the vertex weights.
    pub fn vertex_weights(&self) -> &[W] {
        &self.vertex_weights
    }

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

    /// Get the number of centers K.
    pub fn k(&self) -> usize {
        self.k
    }

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

    /// 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()
    }

    /// Get the number of centers K.
    pub fn num_centers(&self) -> usize {
        self.k
    }

    /// Compute shortest distances from each vertex to the nearest center.
    ///
    /// Uses multi-source Dijkstra with linear scan: initializes all centers
    /// at distance 0 and greedily relaxes edges by increasing distance.
    /// Correct because all edge lengths are non-negative.
    ///
    /// Returns `None` if any vertex is unreachable from all centers.
    fn shortest_distances(
        &self,
        config: &[bool],
    ) -> Result<Option<Vec<W::Sum>>, crate::traits::EvaluationError> {
        let n = self.graph.num_vertices();
        let edges = self.graph.edges();

        let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n];
        for (idx, &(u, v)) in edges.iter().enumerate() {
            let len = self.edge_lengths[idx].to_sum();
            adj[u].push((v, len.clone()));
            adj[v].push((u, len));
        }

        // Multi-source Dijkstra with linear scan (works with PartialOrd)
        let mut dist: Vec<Option<W::Sum>> = vec![None; n];
        let mut visited = vec![false; n];

        // Initialize centers
        for (v, &selected) in config.iter().enumerate() {
            if selected {
                dist[v] = Some(W::Sum::zero());
            }
        }

        for _ in 0..n {
            // Find unvisited vertex with smallest distance
            let mut u = None;
            for v in 0..n {
                if visited[v] {
                    continue;
                }
                if let Some(ref dv) = dist[v] {
                    match u {
                        None => u = Some(v),
                        Some(prev) => {
                            if *dv < dist[prev].clone().unwrap() {
                                u = Some(v);
                            }
                        }
                    }
                }
            }
            let u = match u {
                Some(v) => v,
                None => break, // remaining vertices are unreachable
            };
            visited[u] = true;

            let du = dist[u].clone().unwrap();
            for &(next, ref len) in &adj[u] {
                if visited[next] {
                    continue;
                }
                let new_dist = W::checked_add_to_sum(
                    du.clone(),
                    len.clone(),
                    "adding min-max multicenter path lengths",
                )?;
                let update = match &dist[next] {
                    None => true,
                    Some(d) => new_dist < *d,
                };
                if update {
                    dist[next] = Some(new_dist);
                }
            }
        }

        Ok(dist.into_iter().collect())
    }
}

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

    crate::problem_parameters![
        ("max_numeric_magnitude_bits", max_numeric_magnitude_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<Min<W::Sum>, crate::traits::EvaluationError> {
        Ok({
            if config.len() != self.graph.num_vertices() {
                return Err(crate::traits::EvaluationError::InvalidConfiguration(
                    "center-selection length does not match the graph vertices".into(),
                ));
            }

            // Check exactly K centers are selected
            let num_selected = config.iter().filter(|&&selected| selected).count();
            if num_selected != self.k {
                return Ok(Min(None));
            }

            // Compute shortest distances to nearest center
            let distances = match self.shortest_distances(config)? {
                Some(d) => d,
                None => {
                    return Ok(Min(None));
                }
            };

            // Compute max weighted distance: max_{v} w(v) * d(v)
            let mut max_wd = W::Sum::zero();
            for (v, dist) in distances.iter().enumerate() {
                let wd = W::checked_mul_sum(
                    self.vertex_weights[v].to_sum(),
                    dist.clone(),
                    "multiplying min-max multicenter vertex weight by distance",
                )?;
                if wd > max_wd {
                    max_wd = wd;
                }
            }

            Min(Some(max_wd))
        })
    }
}

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

crate::declare_variants! {
    default MinMaxMulticenter<SimpleGraph, i64> => "1.4969^num_vertices" create MinMaxMulticenterI64CreateSpec,
    MinMaxMulticenter<SimpleGraph, One> => "1.4969^num_vertices" create MinMaxMulticenterOneCreateSpec,
}

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

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

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

crate::decision_problem_meta!(MinMaxMulticenter<SimpleGraph, One>, "DecisionMinMaxMulticenter");
crate::register_decision_variant!(
    MinMaxMulticenter<SimpleGraph, One>, "DecisionMinMaxMulticenter", "1.4969^num_vertices", &[],
    "Does a feasible solution have objective value <= the bound?",
    category: crate::registry::ProblemCategory::Graph,
    dims: [
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
            VariantDimension::new("weight", "One", &["One"]),
        ],
    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: "k", type_name: "usize", description: "Number of centers." },
        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_min_max_multicenter_to_min_max_multicenter",
        build: || {
            let source = crate::models::decision::Decision::new(
                MinMaxMulticenter::new(
                    SimpleGraph::new(
                        6,
                        vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 5), (1, 4)],
                    ),
                    vec![crate::types::One; 6],
                    vec![crate::types::One; 7],
                    2,
                ),
                1,
            );
            let witness = serde_json::json!(vec![false, true, false, false, true, false]);
            crate::example_db::specs::rule_example_with_witness::<
                _,
                MinMaxMulticenter<SimpleGraph, One>,
            >(
                source,
                crate::export::SolutionPair {
                    source_config: witness.clone(),
                    target_config: witness,
                },
            )
        },
    }]
}