B.2. 通过功能提供的可选实现

最后，以下实现是通过功能提供的

• ndarray通过impl_ndarray功能，
• indexmap通过impl_indexmap功能，
• smallvec通过impl_smallvec功能，
• 或者通过impl_all功能提供所有实现。

B.3. 扩展

为新的类型实现特质的实现很简单，只需要实现at方法。请参阅第C5节以获取示例。

C. 动机

以下示例中的用例演示了创建的动机。

假设我们需要解决一个网络问题，即最小成本网络流（mcnf）问题（维基百科）。在示例中，我们忽略图形输入。相反，我们关注以下输入

• 需求：图中的每个节点都有一个需求量，它表示负供给。
• 成本：每条弧都有一个相关的单位流量成本。
• 容量：每条弧都有一个有限的流量容量。

mcnf问题在输入上提供了一定程度的抽象。例如

• 如果只有两个节点的需求非零，则问题是单一商品问题；否则，它可以表示多商品mcnf问题。
• 如果源节点和汇节点的需求为1和-1，其他所有节点的需求为零，并且容量无关紧要，则问题变为最短路径问题。
• 如果我们想要找到最少的弧数而不是最短路径，我们可以使用一个所有元素都是1的弧成本矩阵。

对输入的抽象是强大的，因为它允许实现一个通用的mcnf求解器，而无需对具体的输入类型做出假设。

C.1 问题设置

以下是我们实现的针对输入类型的通用求解器。

use orx_funvec::*;

const N: usize = 4;
type Unit = i32;

#[derive(derive_new::new)]
struct FakeResult {
    sum_demands: i32,
    sum_costs: i32,
    sum_capacities: i32,
}

#[derive(derive_new::new)]
struct FakeMcnfSolver<Demands, Costs, Capacities>
where
    Demands: FunVec<1, Unit>,
    Costs: FunVec<2, Unit>,
    Capacities: FunVec<2, Unit>,
{
    demands: Demands,
    costs: Costs,
    capacities: Capacities,
}

impl<Demands, Costs, Capacities> FakeMcnfSolver<Demands, Costs, Capacities>
where
    Demands: FunVec<1, Unit>,
    Costs: FunVec<2, Unit>,
    Capacities: FunVec<2, Unit>,
{
    fn fake_solve(&self) -> FakeResult {
        let sum_demands = self
            .demands
            .iter_over(0..N)
            .flatten()
            .filter(|x| x > &0)
            .sum();

        let mut sum_costs = 0;
        let mut sum_capacities = 0;
        for i in 0..N {
            for j in 0..N {
                if let Some(cost) = self.costs.at([i, j]) {
                    sum_costs += cost;
                }

                if let Some(capacity) = self.capacities.at((i, j)) {
                    sum_capacities += capacity;
                }
            }
        }
        FakeResult::new(sum_demands, sum_costs, sum_capacities)
    }
}

C.2 变体 - 单商品

在下面的示例中，我们使用我们的通用求解器与

• 一个单商品问题，其中需求向量是一个廉价的闭包（Closure<_, usize, Unit>），
• 一个完整的成本矩阵（Vec<Vec<Unit>>），
• 一个表示为廉价的闭包的统一容量矩阵（Box<dyn Fn((usize, usize)) -> Unit>）。

use orx_closure::Capture;

fn some_if_not_self_edge(ij: (usize, usize), value: i32) -> Option<i32> {
    if ij.0 == ij.1 {
        None
    } else {
        Some(value)
    }
}

// mcnf problem with a single source and sink
let source = 0;
let sink = 2;
let demand = 10;

// demands vector as a no-box orx_closure::Closure
let demands =
    Capture((source, sink, demand)).fun(|(s, t, d), i: usize| match (i == *s, i == *t) {
        (true, _) => Some(*d),
        (_, true) => Some(-*d),
        _ => None,
    });

// complete cost matrix
let costs = vec![
    vec![0, 1, 2, 3],
    vec![2, 0, 2, 2],
    vec![7, 10, 0, 9],
    vec![1, 1, 1, 0],
];

// capacities matrix as a box dyn Fn
let capacities: Box<dyn Fn((usize, usize)) -> Option<i32>> =
    Box::new(|ij: (usize, usize)| some_if_not_self_edge(ij, 100));

// simulate & assert
let solver = FakeMcnfSolver::new(demands, costs, capacities);
let result = solver.fake_solve();

assert_eq!(10, result.sum_demands);
assert_eq!(41, result.sum_costs);
assert_eq!((N * (N - 1) * 100) as i32, result.sum_capacities);

C.3 变体 - 多商品

在第二个示例变体中，我们使用我们的求解器与

• 一个多商品问题，其中需求向量通过实时闭包计算（Closure<_, usize, Unit>），
• 通过闭包使用捕获的节点位置计算弧成本作为欧几里得距离（Closure<_, (usize, usize), Unit>），
• 使用哈希表的一个稀疏容量矩阵（Vec<HashMap<usize, Unit>>）。

use orx_closure::Capture;
use std::collections::HashMap;

fn get_euclidean_distance(location1: (f64, f64), location2: (f64, f64)) -> i32 {
    let (x1, y1) = location1;
    let (x2, y2) = location2;
    (f64::powf(x1 - x2, 2.0) + f64::powf(y1 - y2, 2.0)).sqrt() as i32
}

// multi-commodity mcnf problem
struct Commodity {
    origin: usize,
    destination: usize,
    amount: Unit,
}
let commodities = vec![
    Commodity {
        origin: 0,
        destination: 2,
        amount: 10,
    },
    Commodity {
        origin: 1,
        destination: 3,
        amount: 20,
    },
];

// demands vector as a no-box orx_closure::Closure capturing a reference of commodities collection
let demands = Capture(&commodities).fun(|com, i: usize| {
    Some(
        com.iter()
            .map(|c| {
                if c.origin == i {
                    c.amount
                } else if c.destination == i {
                    -c.amount
                } else {
                    0
                }
            })
            .sum::<i32>(),
    )
});

// costs computed as Euclidean distances of node coordinates
let locations = vec![(0.0, 3.0), (3.0, 5.0), (7.0, 2.0), (1.0, 1.0)];
let costs = Capture(locations).fun(|loc, (i, j): (usize, usize)| {
    loc.get(i)
        .and_then(|l1| loc.get(j).map(|l2| (l1, l2)))
        .map(|(l1, l2)| get_euclidean_distance(*l1, *l2))
});

// capacities defined as a Vec of HashMap to take advantage of sparsity in the graph
let capacities = vec![
    HashMap::from_iter([(1, 100), (3, 200)].into_iter()),
    HashMap::from_iter([(3, 300)].into_iter()),
    HashMap::from_iter([(0, 400), (3, 500)].into_iter()),
    HashMap::new(),
];

// simulate & assert
let solver = FakeMcnfSolver::new(demands, costs, capacities);
let result = solver.fake_solve();

assert_eq!(30, result.sum_demands);
assert_eq!(54, result.sum_costs);
assert_eq!(1500, result.sum_capacities);

let source = 3;
let sink = 1;

// demands vector as a no-box orx_closure::Closure
let demands = Capture((source, sink)).fun(|(s, t), i: usize| match (i == *s, i == *t) {
    (true, _) => Some(1),
    (_, true) => Some(-1),
    _ => None,
});

// costs computed as Euclidean distances of node coordinates
let locations = vec![(0.0, 3.0), (3.0, 5.0), (7.0, 2.0), (1.0, 1.0)];
let costs = Capture(locations).fun(|loc, (i, j): (usize, usize)| {
    loc.get(i)
        .and_then(|l1| loc.get(j).map(|l2| (l1, l2)))
        .map(|(l1, l2)| get_euclidean_distance(*l1, *l2))
});

// uniform capacities for all edges
let capacities = ScalarAsVec(1);

// simulate & assert
let solver = FakeMcnfSolver::new(demands, costs, capacities);
let result = solver.fake_solve();

assert_eq!(1, result.sum_demands);
assert_eq!(54, result.sum_costs);
assert_eq!((N * N) as i32, result.sum_capacities);

type Unit = i32;

use std::{cell::RefCell, collections::HashMap};

#[derive(Default)]
struct DistanceProvider {
    // graph: skipping for the brevity, but we'd probably hold a graph ref to compute the shortest distances
    cached: RefCell<HashMap<(usize, usize), Option<Unit>>>,
}
impl DistanceProvider {
    fn distance(&self, from: usize, to: usize) -> Option<Unit> {
        if let Some(cached) = self.cached.borrow().get(&(from, to)) {
            return *cached;
        }

        let distance = self.compute_shortest_distance(from, to);
        self.cached.borrow_mut().insert((from, to), distance);
        distance
    }

    /// Computes shortest distance between `from` and `to` returns `None` if `to` is unreachable from `from`.
    fn compute_shortest_distance(&self, _from: usize, _to: usize) -> Option<Unit> {
        Some(1) // expensive computation!
    }
}

impl FunVec<2, Unit> for DistanceProvider {
    fn at<Idx: IntoIndex<2>>(&self, index: Idx) -> Option<Unit> {
        let [from, to] = index.into_index();
        self.distance(from, to)
    }
}

let source = 3;
let sink = 1;

// demands vector as a no-box orx_closure::Closure
let demands = Capture((source, sink)).fun(|(s, t), i: usize| match (i == *s, i == *t) {
    (true, _) => Some(1),
    (_, true) => Some(-1),
    _ => None,
});

// our custom caching distance provider
let costs = DistanceProvider::default();

// uniform capacities for all edges
let capacities = ScalarAsVec(1);

// simulate & assert
let solver = FakeMcnfSolver::new(demands, costs, capacities);
let result = solver.fake_solve();

assert_eq!(1, result.sum_demands);
assert_eq!(4 * 4, result.sum_costs);
assert_eq!((N * N) as i32, result.sum_capacities);