problemreductions/models/graph/

disjoint_connecting_paths.rs

//! Disjoint Connecting Paths problem implementation.
//!
//! The problem asks whether an undirected graph contains pairwise
//! vertex-disjoint paths connecting a prescribed collection of terminal pairs.

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

inventory::submit! {
    ProblemSchemaEntry {
        name: "DisjointConnectingPaths",
        display_name: "Disjoint Connecting Paths",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Find pairwise vertex-disjoint paths connecting given terminal pairs",
        fields: DisjointConnectingPathsCreateSpec::FIELDS,
    }
}

/// Disjoint Connecting Paths on an undirected graph.
///
/// A configuration uses one binary variable per edge in the graph's canonical
/// sorted edge list. A valid solution selects exactly the edges of one simple
/// path for each terminal pair, with all such paths pairwise vertex-disjoint.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "DisjointConnectingPathsData<G>")]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
pub struct DisjointConnectingPaths<G> {
    graph: G,
    terminal_pairs: Vec<(usize, usize)>,
}

#[derive(Deserialize)]
#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
struct DisjointConnectingPathsData<G> {
    graph: G,
    terminal_pairs: Vec<(usize, usize)>,
}

impl<G> TryFrom<DisjointConnectingPathsData<G>> for DisjointConnectingPaths<G>
where
    G: Graph,
{
    type Error = crate::registry::ConstructionError;

    fn try_from(data: DisjointConnectingPathsData<G>) -> Result<Self, Self::Error> {
        Self::try_new(data.graph, data.terminal_pairs)
    }
}

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

impl TryFrom<DisjointConnectingPathsCreateSpec> for DisjointConnectingPaths<SimpleGraph> {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: DisjointConnectingPathsCreateSpec) -> Result<Self, Self::Error> {
        if spec.graph.is_empty() && spec.num_vertices.is_none() {
            return Err("num_vertices is required for an empty graph".into());
        }
        for &(u, v) in &spec.graph {
            if u == v {
                return Err(format!("self-loop {u}-{v} is not allowed").into());
            }
        }
        let inferred = spec
            .graph
            .iter()
            .flat_map(|&(u, v)| [u, v])
            .max()
            .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
            .transpose()?
            .unwrap_or(0);
        let count = spec.num_vertices.unwrap_or(inferred);
        if count < inferred {
            return Err("num_vertices is too small for graph endpoints".into());
        }
        Self::try_new(SimpleGraph::new(count, spec.graph), spec.terminal_pairs)
    }
}

impl<G: Graph> DisjointConnectingPaths<G> {
    /// Create a new Disjoint Connecting Paths instance.
    ///
    /// # Panics
    ///
    /// Panics if no terminal pairs are provided, if a pair uses invalid or
    /// repeated endpoints, or if any terminal appears in more than one pair.
    pub fn new(graph: G, terminal_pairs: Vec<(usize, usize)>) -> Self {
        Self::try_new(graph, terminal_pairs).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        graph: G,
        terminal_pairs: Vec<(usize, usize)>,
    ) -> Result<Self, crate::registry::ConstructionError> {
        if terminal_pairs.is_empty() {
            return Err("terminal_pairs must contain at least one pair".into());
        }

        let num_vertices = graph.num_vertices();
        let mut used = vec![false; num_vertices];
        for &(source, sink) in &terminal_pairs {
            if source >= num_vertices {
                return Err("terminal pair source out of bounds".into());
            }
            if sink >= num_vertices {
                return Err("terminal pair sink out of bounds".into());
            }
            if source == sink {
                return Err("terminal pair endpoints must be distinct".into());
            }
            if used[source] {
                return Err("terminal vertices must be pairwise disjoint across pairs".into());
            }
            if used[sink] {
                return Err("terminal vertices must be pairwise disjoint across pairs".into());
            }
            used[source] = true;
            used[sink] = true;
        }

        Ok(Self {
            graph,
            terminal_pairs,
        })
    }

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

    /// Get the terminal pairs.
    pub fn terminal_pairs(&self) -> &[(usize, usize)] {
        &self.terminal_pairs
    }

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

    /// Get the number of terminal pairs.
    pub fn num_pairs(&self) -> usize {
        self.terminal_pairs.len()
    }

    /// Return the canonical lexicographically sorted undirected edge list.
    pub fn ordered_edges(&self) -> Vec<(usize, usize)> {
        canonical_edges(&self.graph)
    }

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

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

    crate::problem_parameters![
        ("num_edges", num_edges),
        ("num_pairs", num_pairs),
        ("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> {
        if config.len() != self.num_edges() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "edge-selection length does not match the graph".into(),
            ));
        }
        Ok(crate::types::Or(self.is_valid_solution(config)))
    }
}

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

fn canonical_edges<G: Graph>(graph: &G) -> Vec<(usize, usize)> {
    let mut edges = graph
        .edges()
        .into_iter()
        .map(|(u, v)| if u <= v { (u, v) } else { (v, u) })
        .collect::<Vec<_>>();
    edges.sort_unstable();
    edges
}

fn normalize_edge(u: usize, v: usize) -> (usize, usize) {
    if u <= v {
        (u, v)
    } else {
        (v, u)
    }
}

fn is_valid_disjoint_connecting_paths<G: Graph>(
    graph: &G,
    terminal_pairs: &[(usize, usize)],
    config: &[bool],
) -> bool {
    let edges = canonical_edges(graph);
    if config.len() != edges.len() {
        return false;
    }
    let num_vertices = graph.num_vertices();
    let mut adjacency = vec![Vec::new(); num_vertices];
    let mut degrees = vec![0usize; num_vertices];
    for (index, &chosen) in config.iter().enumerate() {
        if chosen {
            let (u, v) = edges[index];
            adjacency[u].push(v);
            adjacency[v].push(u);
            degrees[u] += 1;
            degrees[v] += 1;
        }
    }

    let mut terminal_vertices = vec![false; num_vertices];
    let required_pairs = terminal_pairs
        .iter()
        .map(|&(u, v)| {
            terminal_vertices[u] = true;
            terminal_vertices[v] = true;
            normalize_edge(u, v)
        })
        .collect::<BTreeSet<_>>();
    let mut matched_pairs = BTreeSet::new();
    let mut visited = vec![false; num_vertices];
    let mut component_count = 0usize;

    for start in 0..num_vertices {
        if degrees[start] == 0 || visited[start] {
            continue;
        }

        component_count += 1;
        let mut stack = vec![start];
        let mut vertices = Vec::new();
        let mut degree_sum = 0usize;
        visited[start] = true;

        while let Some(vertex) = stack.pop() {
            vertices.push(vertex);
            degree_sum += degrees[vertex];
            for &neighbor in &adjacency[vertex] {
                if !visited[neighbor] {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }

        let edge_count = degree_sum / 2;
        if edge_count + 1 != vertices.len() {
            return false;
        }

        let mut endpoints = Vec::new();
        for &vertex in &vertices {
            match degrees[vertex] {
                1 => endpoints.push(vertex),
                2 => {
                    if terminal_vertices[vertex] {
                        return false;
                    }
                }
                _ => return false,
            }
        }

        if endpoints.len() != 2 {
            return false;
        }

        let realized_pair = normalize_edge(endpoints[0], endpoints[1]);
        if !required_pairs.contains(&realized_pair) || !matched_pairs.insert(realized_pair) {
            return false;
        }
    }

    component_count == terminal_pairs.len() && matched_pairs.len() == terminal_pairs.len()
}

crate::declare_variants! {
    default DisjointConnectingPaths<SimpleGraph> => "2^num_edges" create DisjointConnectingPathsCreateSpec,
}

crate::register_brute_force! {
    DisjointConnectingPaths<SimpleGraph> 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: "disjoint_connecting_paths_simplegraph",
        instance: Box::new(DisjointConnectingPaths::new(
            SimpleGraph::new(
                6,
                vec![(0, 1), (1, 3), (0, 2), (1, 4), (2, 4), (3, 5), (4, 5)],
            ),
            vec![(0, 3), (2, 5)],
        )),
        optimal_config: serde_json::json!(vec![true, false, true, false, true, false, true]),
        optimal_value: serde_json::json!(true),
    }]
}

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