problemreductions/rules/unitdiskmapping/triangular/

mapping.rs

//! Mapping functions for weighted triangular lattice.
//!
//! This module provides functions to map arbitrary graphs to weighted triangular
//! lattice grid graphs using the copy-line technique.

use super::super::copyline::{create_copylines, CopyLine};
use super::super::grid::MappingGrid;
use super::super::ksg::mapping::MappingResult;
use super::super::ksg::KsgTapeEntry as TapeEntry;
use super::super::pathdecomposition::{
    pathwidth, vertex_order_from_layout, PathDecompositionMethod,
};
use super::gadgets::{apply_crossing_gadgets, apply_simplifier_gadgets, tape_entry_mis_overhead};
use crate::rules::unitdiskmapping::ksg::mapping::GridKind;
use crate::rules::unitdiskmapping::{mapping_integer_overflow, mapping_invalid};
use crate::rules::ReductionError;
use std::collections::HashMap;

fn position_index(
    result: &MappingResult,
) -> Result<HashMap<(usize, usize), usize>, ReductionError> {
    result
        .positions
        .iter()
        .enumerate()
        .map(|(index, &(row, column))| {
            let row = usize::try_from(row)
                .map_err(|_| mapping_invalid("mapping result contains a negative grid row"))?;
            let column = usize::try_from(column)
                .map_err(|_| mapping_invalid("mapping result contains a negative grid column"))?;
            Ok(((row, column), index))
        })
        .collect()
}

/// Spacing between copy lines on triangular lattice.
pub const SPACING: usize = 6;

/// Padding around the grid for triangular lattice.
pub const PADDING: usize = 2;

/// Calculate crossing point for two copylines on triangular lattice.
fn crossat(
    copylines: &[CopyLine],
    v: usize,
    w: usize,
    spacing: usize,
    padding: usize,
) -> (usize, usize) {
    let line_v = &copylines[v];
    let line_w = &copylines[w];

    // Use vslot to determine order
    let (line_first, line_second) = if line_v.vslot < line_w.vslot {
        (line_v, line_w)
    } else {
        (line_w, line_v)
    };

    let hslot = line_first.hslot;
    let max_vslot = line_second.vslot;

    // 0-indexed coordinates (subtract 1 from Julia's 1-indexed formula)
    let row = (hslot - 1) * spacing + 1 + padding; // 0-indexed
    let col = (max_vslot - 1) * spacing + padding; // 0-indexed

    (row, col)
}

/// Map a graph to a weighted triangular lattice grid graph using optimal path decomposition.
///
/// This is the main entry point for triangular lattice mapping. It uses
/// automatic path decomposition (exact for ≤30 vertices, greedy for larger).
///
/// # Arguments
/// * `num_vertices` - Number of vertices in the original graph
/// * `edges` - Edge list as (u, v) pairs
///
/// # Returns
/// A `MappingResult` containing the grid graph and mapping metadata.
///
/// # Errors
/// Returns [`ReductionError`] if the input graph or generated dimensions are invalid.
///
/// # Example
/// ```rust
/// use problemreductions::rules::unitdiskmapping::triangular::mapping::map_weighted;
/// use problemreductions::topology::Graph;
///
/// let edges = vec![(0, 1), (1, 2)];
/// let result = map_weighted(3, &edges).unwrap();
/// assert!(result.to_triangular_subgraph().num_vertices() > 0);
/// ```
pub fn map_weighted(
    num_vertices: usize,
    edges: &[(usize, usize)],
) -> Result<MappingResult, ReductionError> {
    map_weighted_with_method(num_vertices, edges, PathDecompositionMethod::Auto)
}

/// Map a graph to weighted triangular lattice using a specific path decomposition method.
///
/// # Arguments
/// * `num_vertices` - Number of vertices in the original graph
/// * `edges` - Edge list as (u, v) pairs
/// * `method` - Path decomposition method to use
///
/// # Returns
/// A `MappingResult` containing the grid graph and mapping metadata.
pub fn map_weighted_with_method(
    num_vertices: usize,
    edges: &[(usize, usize)],
    method: PathDecompositionMethod,
) -> Result<MappingResult, ReductionError> {
    let layout = pathwidth(num_vertices, edges, method);
    let vertex_order = vertex_order_from_layout(&layout);
    map_weighted_with_order(num_vertices, edges, &vertex_order)
}

/// Map a graph to weighted triangular lattice with specific vertex ordering.
///
/// This is the most flexible mapping function, allowing custom vertex ordering
/// for cases where a specific layout is desired.
///
/// # Arguments
/// * `num_vertices` - Number of vertices in the original graph
/// * `edges` - Edge list as (u, v) pairs
/// * `vertex_order` - Custom vertex ordering
///
/// # Returns
/// A `MappingResult` containing the grid graph and mapping metadata.
///
/// # Errors
/// Returns [`ReductionError`] if the vertex order, graph, or generated dimensions are invalid.
pub fn map_weighted_with_order(
    num_vertices: usize,
    edges: &[(usize, usize)],
    vertex_order: &[usize],
) -> Result<MappingResult, ReductionError> {
    if num_vertices == 0 {
        return Err(mapping_invalid("num_vertices must be positive"));
    }

    let spacing = SPACING;
    let padding = PADDING;

    let copylines = create_copylines(num_vertices, edges, vertex_order)?;

    // Calculate grid dimensions
    // Julia formula: N = (n-1)*col_spacing + 2 + 2*padding
    //                M = nrow*row_spacing + 2 + 2*padding
    // where nrow = max(hslot, vstop) and n = num_vertices
    let max_hslot = copylines.iter().map(|l| l.hslot).max().unwrap_or(1);
    let max_vstop = copylines.iter().map(|l| l.vstop).max().unwrap_or(1);

    let padding_twice = padding.checked_mul(2).ok_or(mapping_integer_overflow(
        "computing triangular grid padding",
    ))?;
    let extent = |slots: usize| {
        slots
            .checked_mul(spacing)
            .and_then(|value| value.checked_add(2))
            .and_then(|value| value.checked_add(padding_twice))
            .ok_or(mapping_integer_overflow(
                "computing triangular grid dimensions",
            ))
    };
    let rows = extent(max_hslot.max(max_vstop))?;
    // Use (num_vertices - 1) for cols, matching Julia's (n-1) formula
    let cols = extent(num_vertices - 1)?;

    let mut grid = MappingGrid::with_padding(rows, cols, spacing, padding);

    // Add copy line nodes using triangular dense locations
    // (includes the endpoint node for triangular weighted mode)
    for line in &copylines {
        for (row, col, weight) in line.copyline_locations_triangular(padding, spacing) {
            let weight = i64::try_from(weight).map_err(|_| {
                mapping_integer_overflow("converting a triangular grid weight to i64")
            })?;
            grid.add_node(row, col, weight);
        }
    }

    // Mark edge connections at crossing points
    for &(u, v) in edges {
        let u_line = &copylines[u];
        let v_line = &copylines[v];

        let (smaller_line, larger_line) = if u_line.vslot < v_line.vslot {
            (u_line, v_line)
        } else {
            (v_line, u_line)
        };

        let (row, col) = crossat(
            &copylines,
            smaller_line.vertex,
            larger_line.vertex,
            spacing,
            padding,
        );

        // Mark connected cells at crossing point
        if col > 0 {
            grid.connect(row, col - 1);
        }
        if row > 0 && grid.is_occupied(row - 1, col) {
            grid.connect(row - 1, col);
        } else if row + 1 < grid.size().0 && grid.is_occupied(row + 1, col) {
            grid.connect(row + 1, col);
        }
    }

    // Apply crossing gadgets (iterates ALL pairs, not just edges)
    let mut triangular_tape = apply_crossing_gadgets(&mut grid, &copylines, spacing, padding);

    // Apply simplifier gadgets (weighted DanglingLeg pattern)
    // Julia's triangular mode uses: weighted.(default_simplifier_ruleset(UnWeighted()))
    // which applies the weighted DanglingLeg pattern to reduce grid complexity.
    let simplifier_tape = apply_simplifier_gadgets(&mut grid, 10);
    triangular_tape.extend(simplifier_tape);

    // Calculate MIS overhead from copylines using the dedicated function
    // which matches Julia's mis_overhead_copyline(TriangularWeighted(), ...)
    let copyline_overhead = copylines.iter().try_fold(0_i64, |total, line| {
        total
            .checked_add(super::super::copyline::mis_overhead_copyline_triangular(
                line, spacing,
            )?)
            .ok_or(mapping_integer_overflow(
                "summing triangular copy-line MIS overhead",
            ))
    })?;

    // Add gadget overhead (crossing gadgets + simplifiers)
    let gadget_overhead = triangular_tape.iter().try_fold(0_i64, |total, entry| {
        total
            .checked_add(tape_entry_mis_overhead(entry)?)
            .ok_or(mapping_integer_overflow(
                "summing triangular gadget MIS overhead",
            ))
    })?;
    let mis_overhead =
        copyline_overhead
            .checked_add(gadget_overhead)
            .ok_or(mapping_integer_overflow(
                "computing total triangular MIS overhead",
            ))?;

    if grid.has_unresolved_cells() {
        return Err(mapping_invalid(
            "triangular mapping left doubled or connected cells unresolved",
        ));
    }

    // Convert triangular tape entries to generic tape entries
    let tape: Vec<TapeEntry> = triangular_tape
        .into_iter()
        .map(|entry| TapeEntry {
            pattern_idx: entry.gadget_idx,
            row: entry.row,
            col: entry.col,
        })
        .collect();

    // Extract doubled cells before extracting positions
    let doubled_cells = grid.doubled_cells();

    // Extract positions and weights from occupied cells
    let positions_and_weights = grid
        .occupied_coords()
        .into_iter()
        .filter_map(|(row, col)| {
            grid.get(row, col)
                .filter(|cell| cell.weight() > 0)
                .map(|cell| {
                    Ok((
                        (
                            i64::try_from(row).map_err(|_| {
                                mapping_integer_overflow("converting a grid row to i64")
                            })?,
                            i64::try_from(col).map_err(|_| {
                                mapping_integer_overflow("converting a grid column to i64")
                            })?,
                        ),
                        cell.weight(),
                    ))
                })
        })
        .collect::<Result<Vec<_>, ReductionError>>()?;
    let (positions, node_weights): (Vec<_>, Vec<_>) = positions_and_weights.into_iter().unzip();

    Ok(MappingResult {
        positions,
        node_weights,
        grid_dimensions: grid.size(),
        kind: GridKind::Triangular,
        lines: copylines,
        padding,
        spacing,
        mis_overhead,
        tape,
        doubled_cells,
    })
}

/// Read the original vertex configuration at the traced triangular centers.
pub fn map_config_back(
    result: &MappingResult,
    grid_config: &[usize],
) -> crate::rules::ExtractionResult<Vec<usize>> {
    map_config_back_internal(result, grid_config)
        .map_err(|error| crate::rules::ExtractionError::invalid(error.to_string()))
}

fn map_config_back_internal(
    result: &MappingResult,
    grid_config: &[usize],
) -> Result<Vec<usize>, ReductionError> {
    if grid_config.len() != result.positions.len() {
        return Err(mapping_invalid(
            "grid configuration length must match the mapped vertex count",
        ));
    }
    let positions = position_index(result)?;

    super::super::weighted::trace_centers(result)?
        .into_iter()
        .map(|center| {
            positions
                .get(&center)
                .map(|&index| grid_config[index])
                .ok_or(mapping_invalid(
                    "a traced center is missing from the mapped graph",
                ))
        })
        .collect()
}

/// Encode unit source weights exactly in the integer target weights.
///
/// Multiplying the base gadget weights by `n + 1` preserves the mapping's
/// primary objective. Adding one at each traced source center then maximizes
/// the source independent-set size among those primary optima.
pub fn map_unit_weights(result: &MappingResult) -> Result<Vec<i64>, ReductionError> {
    let count = i64::try_from(result.lines.len())
        .map_err(|_| mapping_integer_overflow("converting the source vertex count to i64"))?;
    let scale = count.checked_add(1).ok_or(mapping_integer_overflow(
        "computing the unit-weight encoding scale",
    ))?;
    let mut weights = result
        .node_weights
        .iter()
        .map(|weight| {
            weight.checked_mul(scale).ok_or(mapping_integer_overflow(
                "scaling a triangular mapped weight",
            ))
        })
        .collect::<Result<Vec<_>, _>>()?;
    let positions = position_index(result)?;

    for center in super::super::weighted::trace_centers(result)? {
        let index = positions.get(&center).copied().ok_or(mapping_invalid(
            "a traced center is missing from the mapped graph",
        ))?;
        weights[index] = weights[index]
            .checked_add(1)
            .ok_or(mapping_integer_overflow(
                "adding a unit source weight to a triangular center",
            ))?;
    }
    Ok(weights)
}

#[cfg(test)]
#[path = "../../../unit_tests/rules/unitdiskmapping/triangular/mapping.rs"]
mod tests;