use crate::error::{Error, Result};
use crate::game::{ExplicitGame, PlayerSet, SetFunction};
use crate::nucleolus;
#[derive(Clone, Debug, PartialEq)]
pub struct SpanningTreeGame {
costs: Vec<Vec<f64>>,
}
impl SpanningTreeGame {
pub fn new(costs: Vec<Vec<f64>>) -> Result<SpanningTreeGame> {
let size = costs.len();
if size < 2 || costs.iter().any(|row| row.len() != size) {
return Err(Error::InvalidArgument(
"費用行列は (プレイヤー数 + 1) の正方行列".into(),
));
}
for (u, row) in costs.iter().enumerate() {
for (v, &c) in row.iter().enumerate() {
if !(c.is_finite() && c >= 0.0) || (c - costs[v][u]).abs() > 1e-12 {
return Err(Error::InvalidArgument(format!(
"費用 ({u}, {v}) が非負の有限値でないか、対称でない"
)));
}
}
}
Ok(SpanningTreeGame { costs })
}
fn prim(&self, members: &[usize]) -> (Vec<f64>, f64) {
let m = members.len();
let mut in_tree = vec![false; m];
let mut best: Vec<f64> = members.iter().map(|&i| self.costs[0][i + 1]).collect();
let mut paid = vec![0.0; m];
let mut total = 0.0;
for _ in 0..m {
let k = (0..m)
.filter(|&k| !in_tree[k])
.min_by(|&a, &b| best[a].total_cmp(&best[b]).then(a.cmp(&b)))
.expect("残りのメンバーがいる");
in_tree[k] = true;
paid[k] = best[k];
total += best[k];
for other in 0..m {
if !in_tree[other] {
let c = self.costs[members[k] + 1][members[other] + 1];
if c < best[other] {
best[other] = c;
}
}
}
}
(paid, total)
}
pub fn cost(&self, coalition: &PlayerSet) -> f64 {
let members: Vec<usize> = coalition.members().collect();
self.prim(&members).1
}
pub fn bird_rule(&self) -> Vec<f64> {
let members: Vec<usize> = (0..self.costs.len() - 1).collect();
self.prim(&members).0
}
pub fn nucleolus_costs(&self) -> Result<Vec<f64>> {
let savings = nucleolus::nucleolus(&ExplicitGame::tabulate(self)?)?.allocation;
Ok(crate::games::cost::shares_from_savings(
&self.costs[0][1..],
&savings,
))
}
}
impl SetFunction for SpanningTreeGame {
fn players(&self) -> usize {
self.costs.len() - 1
}
fn value(&self, coalition: &PlayerSet) -> f64 {
let standalone: f64 = coalition.members().map(|i| self.costs[0][i + 1]).sum();
standalone - self.cost(coalition)
}
}