use crate::execution::WorkBudget;
use crate::{Error, Result};
#[cfg(any(test, cocycle_distance_bench))]
#[path = "wasserstein/instrumentation.rs"]
mod instrumentation;
#[cfg(any(test, cocycle_distance_bench))]
pub(crate) use instrumentation::{Options, Stats};
#[cfg(not(any(test, cocycle_distance_bench)))]
#[derive(Clone, Copy, Default)]
struct Options {}
#[cfg(not(any(test, cocycle_distance_bench)))]
#[derive(Default)]
struct Stats {}
mod dense;
mod direct;
mod graph;
mod numeric;
use dense::{certified_greedy, dense_sap, tiny};
use graph::{Edge, Graph, components, generate, groups};
use numeric::{
Point, cross_power, diagonal_power, finite, from_flows, from_matching, numerical, power_scale,
prepare, restore_scale, saving,
};
mod sparse;
#[cfg(test)]
mod tests;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum Metric {
W1,
W2,
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(crate) enum SparseLayout {
#[default]
Vectors,
#[cfg(any(test, cocycle_distance_bench))]
Arena,
}
#[cfg(any(test, cocycle_distance_bench))]
fn capacity_bytes<T>(values: &Vec<T>) -> usize {
values.capacity().saturating_mul(std::mem::size_of::<T>())
}
fn allocation() -> Error {
Error::AllocationFailed {
context: "Wasserstein workspace",
}
}
fn sum_size(a: usize, b: usize) -> Result<usize> {
a.checked_add(b).ok_or(Error::SizeOverflow {
operation: "Wasserstein workspace size",
})
}
fn product(a: usize, b: usize) -> Result<usize> {
a.checked_mul(b).ok_or(Error::SizeOverflow {
operation: "Wasserstein pair count",
})
}
fn buffer<T: Clone>(length: usize, value: T) -> Result<Vec<T>> {
let mut result = Vec::new();
result.try_reserve_exact(length).map_err(|_| allocation())?;
result.resize(length, value);
Ok(result)
}
fn push<T>(target: &mut Vec<T>, value: T) -> Result<()> {
target.try_reserve(1).map_err(|_| allocation())?;
target.push(value);
Ok(())
}
fn solve_graph<const CONTROLLED: bool>(
graph: &Graph,
dense: Option<bool>,
greedy: bool,
metric: Metric,
_options: Options,
_stats: &mut Stats,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<Vec<Option<usize>>> {
budget.check()?;
if greedy
&& (graph.rows.max(graph.columns) <= 32 || graph.density() <= 0.05)
&& let Some(matching) = certified_greedy(graph, _stats, budget)?
{
return Ok(matching);
}
let use_dense = dense.unwrap_or(graph.rows.max(graph.columns) <= 24 || graph.density() >= 0.15);
if use_dense {
dense_sap(
graph,
dense.is_none() && metric == Metric::W1 && graph.rows.max(graph.columns) >= 512,
_stats,
budget,
)
} else {
let flows = sparse::solve(
graph,
None,
experiment!(_options.sparse, SparseLayout::Vectors),
_stats,
budget,
)?;
let mut matching = buffer(graph.rows, None)?;
budget.step_by(flows.len())?;
for (row, column, amount) in flows {
if amount != 1 {
return Err(Error::InternalInvariant {
reason: "unit Wasserstein matching has non-unit flow",
});
}
matching[row] = Some(column);
}
Ok(matching)
}
}
fn solve_components<const CONTROLLED: bool>(
graph: &Graph,
metric: Metric,
_options: Options,
_stats: &mut Stats,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<Vec<Option<usize>>> {
let mut matching = buffer(graph.rows, None)?;
let mut column_map = buffer(graph.columns, 0)?;
for component in components(graph, budget)? {
if CONTROLLED {
budget.step_by(sum_size(component.rows.len(), component.columns.len())?)?;
}
record! { _stats.components += 1; }
if component.rows.len() == 1 || component.columns.len() == 1 {
let mut best = 0.0;
let mut pair = None;
for &row in &component.rows {
if CONTROLLED {
budget.step_by(graph.row_work(row))?;
}
for edge in graph.edges(row) {
if edge.saving > best {
best = edge.saving;
pair = Some((row, edge.column));
}
}
}
if let Some((row, column)) = pair {
matching[row] = Some(column);
}
record! { _stats.tiny_components += 1; }
continue;
}
for (local, &column) in component.columns.iter().enumerate() {
column_map[column] = local;
}
let mut candidates = buffer(component.rows.len(), Vec::new())?;
for (local, &row) in component.rows.iter().enumerate() {
if CONTROLLED {
budget.step_by(graph.row_work(row))?;
}
for edge in graph.edges(row) {
push(
&mut candidates[local],
Edge {
column: column_map[edge.column],
saving: edge.saving,
},
)?;
}
}
let local = Graph::from_candidates(candidates, component.columns.len(), true, budget)?;
record! { local.record_capacity(_stats); }
let local_matching = if sum_size(local.rows, local.columns)? <= 8 {
record! { _stats.tiny_components += 1; }
tiny(&local, budget)?
} else {
let dense = local.rows.max(local.columns) <= 24 || local.density() >= 0.20;
solve_graph(
&local,
Some(dense),
!dense,
metric,
_options,
_stats,
budget,
)?
};
for (row, column) in local_matching.into_iter().enumerate() {
if let Some(column) = column {
matching[component.rows[row]] = Some(component.columns[column]);
}
}
}
Ok(matching)
}
pub(crate) fn distance<const CONTROLLED: bool>(
first: &[[f64; 2]],
second: &[[f64; 2]],
metric: Metric,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<f64> {
solve(
first,
second,
metric,
Options::default(),
&mut Stats::default(),
budget,
)
}
#[cfg(any(test, cocycle_distance_bench))]
pub(crate) fn distance_with_options(
first: &[[f64; 2]],
second: &[[f64; 2]],
metric: Metric,
_options: Options,
_stats: &mut Stats,
) -> Result<f64> {
solve(
first,
second,
metric,
_options,
_stats,
&mut WorkBudget::unlimited(),
)
}
fn solve<const CONTROLLED: bool>(
first: &[[f64; 2]],
second: &[[f64; 2]],
metric: Metric,
_options: Options,
_stats: &mut Stats,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<f64> {
let scale = power_scale(first, second, budget)?;
let first = prepare(first, scale, budget)?;
let second = prepare(second, scale, budget)?;
let original_pairs = product(first.len(), second.len())?;
if !experiment!(_options.force_sparse, false) {
let (first_groups, rows) = groups(&first, budget)?;
let (second_groups, columns) = groups(&second, budget)?;
record! { _stats.duplicate_groups = sum_size(first_groups.len(), second_groups.len())?; }
let removed = first_groups.len() != first.len() || second_groups.len() != second.len();
if removed && product(first_groups.len(), second_groups.len())? <= original_pairs / 16 {
let mut candidates = buffer(first_groups.len(), Vec::new())?;
let mut direct_cost_required = false;
for (row, &point) in first_groups.iter().enumerate() {
budget.step_by(second_groups.len().max(1))?;
for (column, &other) in second_groups.iter().enumerate() {
record! { _stats.candidate_pairs += 1; }
let (value, direct) = saving(point, other, metric)?;
direct_cost_required |= direct;
if value > 0.0 {
push(
&mut candidates[row],
Edge {
column,
saving: value,
},
)?;
record! { _stats.positive_edges += 1; }
}
}
}
if direct_cost_required {
let matching = direct::matching(&first, &second, metric, _stats, budget)?;
return restore_scale(
from_matching(&first, &second, matching, metric, budget)?,
scale,
);
}
let graph = Graph::from_candidates(candidates, second_groups.len(), true, budget)?;
record! { graph.record_capacity(_stats); }
let flows = sparse::solve(
&graph,
Some((&rows, &columns)),
experiment!(_options.sparse, SparseLayout::Vectors),
_stats,
budget,
)?;
return restore_scale(
from_flows(
&first_groups,
&second_groups,
&rows,
&columns,
&flows,
metric,
budget,
)?,
scale,
);
}
}
let graph = generate(&first, &second, metric, _stats, budget)?;
record! { graph.record_capacity(_stats); }
let matching = if graph.direct_cost_required {
direct::matching(&first, &second, metric, _stats, budget)?
} else if experiment!(_options.force_sparse, false) {
solve_graph(&graph, Some(false), false, metric, _options, _stats, budget)?
} else if graph.density() >= 0.15 {
solve_graph(&graph, None, true, metric, _options, _stats, budget)?
} else {
solve_components(&graph, metric, _options, _stats, budget)?
};
restore_scale(
from_matching(&first, &second, matching, metric, budget)?,
scale,
)
}