use std::fmt::{self, Write as _};
use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame};
use crate::kernel::{SetOptions, kernel_set};
use crate::linalg::{for_each_combination, indicator, solve_square};
use crate::{Domain, nucleolus, values};
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct PlotOptions {
pub kernel: bool,
pub shapley: bool,
pub points: Vec<Vec<f64>>,
pub title: Option<String>,
}
impl Default for PlotOptions {
fn default() -> PlotOptions {
PlotOptions {
kernel: true,
shapley: true,
points: Vec::new(),
title: None,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Figure {
pub svg: String,
pub core_vertices: Vec<Vec<f64>>,
pub kernel_pieces: Vec<Vec<Vec<f64>>>,
pub points: Vec<(Point, Vec<f64>)>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Point {
Nucleolus,
Shapley,
Extra(usize),
}
impl fmt::Display for Point {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Point::Nucleolus => f.write_str("仁"),
Point::Shapley => f.write_str("Shapley 値"),
Point::Extra(k) => write!(f, "点 {k}"),
}
}
}
const WIDTH: f64 = 640.0;
const HEIGHT: f64 = 600.0;
pub fn imputation_figure(game: &ExplicitGame, options: &PlotOptions) -> Result<Figure> {
let n = game.players();
if !(n == 3 || n == 4) {
return Err(Error::InvalidArgument(format!(
"図は 3 人か 4 人のゲームに限る ({n} 人)"
)));
}
let singles = game.singleton_values();
let surplus = game.value(game.grand()) - singles.iter().sum::<f64>();
if surplus <= 1e-12 * game.max_abs_value().max(1.0) {
return Err(Error::InvalidArgument(
"配分集合が 1 点以下 (v(N) <= sum v({i})) なので描けない".into(),
));
}
let projection = Projection::new(n, singles.clone(), surplus);
let core_vertices = core_vertices(game);
let kernel_pieces = if options.kernel {
kernel_set(game, Domain::Imputation, SetOptions::for_game(game))?
.pieces
.into_iter()
.filter_map(|piece| piece.vertices)
.collect()
} else {
Vec::new()
};
let mut points: Vec<(Point, Vec<f64>)> =
vec![(Point::Nucleolus, nucleolus::nucleolus(game)?.allocation)];
if options.shapley {
points.push((Point::Shapley, values::shapley(game)));
}
points.extend(
options
.points
.iter()
.enumerate()
.map(|(k, x)| (Point::Extra(k), x.clone())),
);
for (point, x) in &points {
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"{point} の長さが人数と異なる"
)));
}
}
let corners: Vec<Vec<f64>> = (0..n)
.map(|i| {
let mut x = singles.clone();
x[i] += surplus;
x
})
.collect();
let mut screen: Vec<(f64, f64)> = corners.iter().map(|x| projection.project(x)).collect();
screen.extend(points.iter().map(|(_, x)| projection.project(x)));
let scene = Scene {
n,
view: View::fit(&screen),
projection,
corners: screen[..n].to_vec(),
};
let title = options
.title
.clone()
.unwrap_or_else(|| format!("{n} 人ゲームの配分集合"));
let mut svg = String::new();
draw_header(&mut svg, &title);
scene.draw_frame(&mut svg);
scene.draw_core(&mut svg, game, &core_vertices);
scene.draw_kernel(&mut svg, &kernel_pieces);
scene.draw_vertex_labels(&mut svg);
scene.draw_points(&mut svg, &points, options.shapley);
draw_legend(
&mut svg,
!core_vertices.is_empty(),
options.kernel,
points.len() > 1,
);
svg.push_str("</svg>\n");
Ok(Figure {
svg,
core_vertices,
kernel_pieces,
points,
})
}
fn draw_header(svg: &mut String, title: &str) {
let _ = writeln!(
svg,
r#"<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 {WIDTH} {HEIGHT}" width="{WIDTH}" height="{HEIGHT}" role="img" aria-labelledby="t d" font-family="system-ui, -apple-system, 'Hiragino Sans', 'Noto Sans JP', sans-serif">"#
);
let _ = writeln!(svg, "<title id=\"t\">{}</title>", escape(title));
let _ = writeln!(
svg,
"<desc id=\"d\">配分集合と、コア (青)・カーネル (橙)・仁 (水色) などの位置。各点の値は点に重ねたツールチップにある。</desc>"
);
svg.push_str(STYLE);
let _ = writeln!(
svg,
r#"<rect class="surface" width="{WIDTH}" height="{HEIGHT}"/>"#
);
let _ = writeln!(
svg,
r#"<text class="title" x="24" y="36">{}</text>"#,
escape(title)
);
}
fn line(svg: &mut String, class: &str, p: (f64, f64), q: (f64, f64), tooltip: Option<&str>) {
let _ = write!(
svg,
r#"<line class="{class}" x1="{:.1}" y1="{:.1}" x2="{:.1}" y2="{:.1}""#,
p.0, p.1, q.0, q.1
);
match tooltip {
Some(text) => {
let _ = writeln!(svg, "><title>{text}</title></line>");
}
None => svg.push_str("/>\n"),
}
}
fn polygon(svg: &mut String, class: &str, points: &[(f64, f64)], tooltip: &str) {
let path: Vec<String> = convex_order(points)
.iter()
.map(|(x, y)| format!("{x:.1},{y:.1}"))
.collect();
let _ = writeln!(
svg,
r#"<polygon class="{class}" points="{}"><title>{tooltip}</title></polygon>"#,
path.join(" ")
);
}
#[derive(Clone, Copy)]
enum Marker {
Circle,
Diamond,
Square,
}
impl Marker {
fn svg(self, x: f64, y: f64) -> String {
match self {
Marker::Circle => {
format!(r#"<circle class="nucleolus" cx="{x:.1}" cy="{y:.1}" r="5.5"/>"#)
}
Marker::Diamond => format!(
r#"<rect class="other" x="{:.1}" y="{:.1}" width="9" height="9" transform="rotate(45 {x:.1} {y:.1})"/>"#,
x - 4.5,
y - 4.5
),
Marker::Square => format!(
r#"<rect class="other" x="{:.1}" y="{:.1}" width="9" height="9"/>"#,
x - 4.5,
y - 4.5
),
}
}
}
struct Scene {
n: usize,
projection: Projection,
view: View,
corners: Vec<(f64, f64)>,
}
impl Scene {
fn map(&self, x: &[f64]) -> (f64, f64) {
self.view.map(self.projection.project(x))
}
fn draw_frame(&self, svg: &mut String) {
for a in 0..self.n {
for b in a + 1..self.n {
let (p, q) = (
self.view.map(self.corners[a]),
self.view.map(self.corners[b]),
);
line(svg, "frame", p, q, None);
}
}
}
fn draw_core(&self, svg: &mut String, game: &ExplicitGame, vertices: &[Vec<f64>]) {
if vertices.is_empty() {
return;
}
let mapped: Vec<(f64, f64)> = vertices.iter().map(|x| self.map(x)).collect();
if self.n == 3 {
let tooltip = format!("コア ({} 頂点)", vertices.len());
polygon(svg, "core", &mapped, &tooltip);
} else {
for (a, b) in core_edges(game, vertices) {
line(svg, "core-edge", mapped[a], mapped[b], None);
}
}
}
fn draw_kernel(&self, svg: &mut String, pieces: &[Vec<Vec<f64>>]) {
for piece in pieces {
let mapped: Vec<(f64, f64)> = piece.iter().map(|x| self.map(x)).collect();
let tooltip = format!("カーネル ({} 頂点)", piece.len());
match mapped.len() {
1 => {}
2 => line(svg, "kernel", mapped[0], mapped[1], Some(&tooltip)),
_ => polygon(svg, "kernel-area", &mapped, &tooltip),
}
}
for piece in pieces.iter().filter(|p| p.len() == 1) {
let (x, y) = self.map(&piece[0]);
let _ = writeln!(
svg,
r#"<circle class="kernel-dot" cx="{x:.1}" cy="{y:.1}" r="9"><title>カーネル: {}</title></circle>"#,
format_allocation(&piece[0])
);
}
}
fn draw_vertex_labels(&self, svg: &mut String) {
let center = {
let (sx, sy) = self
.corners
.iter()
.fold((0.0, 0.0), |acc, p| (acc.0 + p.0, acc.1 + p.1));
self.view.map((sx / self.n as f64, sy / self.n as f64))
};
for (i, &corner) in self.corners.iter().enumerate() {
let (x, y) = self.view.map(corner);
let (dx, dy) = (x - center.0, y - center.1);
let norm = (dx * dx + dy * dy).sqrt().max(1e-9);
let (lx, ly) = (x + 22.0 * dx / norm, y + 22.0 * dy / norm + 5.0);
let _ = writeln!(
svg,
r#"<text class="vertex" x="{lx:.1}" y="{ly:.1}" text-anchor="middle">{i}</text>"#
);
}
}
fn draw_points(&self, svg: &mut String, points: &[(Point, Vec<f64>)], shapley: bool) {
let placed: Vec<(f64, f64)> = points.iter().map(|(_, x)| self.map(x)).collect();
let mut taken: Vec<Rect> = placed
.iter()
.map(|&(x, y)| Rect::around(x, y, 11.0))
.collect();
let mut marks: Vec<String> = Vec::new();
for (k, ((point, x), &(px, py))) in points.iter().zip(&placed).enumerate() {
let label = point.to_string();
let marker = match k {
0 => Marker::Circle,
1 if shapley => Marker::Diamond,
_ => Marker::Square,
};
let tooltip = format!("{label}: {}", format_allocation(x));
marks.push(format!(
r#"<g class="point">{}<circle class="hit" cx="{px:.1}" cy="{py:.1}" r="12"/><title>{}</title></g>"#,
marker.svg(px, py),
escape(&tooltip)
));
let (lx, ly, anchor, rect) = place_label(px, py, text_width(&label, 13.0), &taken);
taken.push(rect);
let _ = writeln!(
svg,
r#"<text class="label" x="{lx:.1}" y="{ly:.1}" text-anchor="{anchor}">{}</text>"#,
escape(&label)
);
}
for mark in marks.iter().rev() {
let _ = writeln!(svg, "{mark}");
}
}
}
fn place_label(px: f64, py: f64, width: f64, taken: &[Rect]) -> (f64, f64, &'static str, Rect) {
let candidates = [
(px + 15.0, py + 4.5, "start"),
(px - 15.0, py + 4.5, "end"),
(px + 15.0, py + 22.0, "start"),
(px + 15.0, py - 13.0, "start"),
(px - 15.0, py + 22.0, "end"),
(px - 15.0, py - 13.0, "end"),
];
let with_rect =
|(x, y, anchor): (f64, f64, &'static str)| (x, y, anchor, Rect::label(x, y, anchor, width));
candidates
.iter()
.map(|&c| with_rect(c))
.find(|(_, _, _, rect)| taken.iter().all(|other| !rect.overlaps(other)))
.unwrap_or_else(|| with_rect(candidates[0]))
}
fn draw_legend(svg: &mut String, core: bool, kernel: bool, others: bool) {
let legend_y = HEIGHT - 28.0;
let mut lx = 24.0;
let mut item = |svg: &mut String, swatch: &str, text: &str| {
let _ = writeln!(
svg,
r#"<g transform="translate({lx:.0},{legend_y:.0})">{swatch}<text class="legend" x="18" y="5">{text}</text></g>"#
);
lx += 18.0 + text_width(text, 13.0) + 22.0;
};
item(
svg,
r#"<line class="frame" x1="0" y1="0" x2="12" y2="0"/>"#,
"配分集合",
);
item(
svg,
r#"<rect class="core" x="0" y="-6" width="12" height="12"/>"#,
if core { "コア" } else { "コア (空)" },
);
if kernel {
item(
svg,
r#"<line class="kernel" x1="0" y1="0" x2="12" y2="0"/>"#,
"カーネル",
);
}
item(
svg,
r#"<circle class="nucleolus" cx="6" cy="0" r="5"/>"#,
"仁",
);
if others {
item(
svg,
r#"<rect class="other" x="2" y="-4" width="8" height="8"/>"#,
"その他の点",
);
}
}
const STYLE: &str = r#"<style>
svg { --surface: #fcfcfb; --text-primary: #0b0b0b; --text-secondary: #52514e; --grid: #d6d5d0;
--series-1: #2a78d6; --series-2: #eb6834; --series-3: #1baf7a; }
@media (prefers-color-scheme: dark) {
svg { --surface: #1a1a19; --text-primary: #ffffff; --text-secondary: #c3c2b7; --grid: #4a4a46;
--series-1: #3987e5; --series-2: #d95926; --series-3: #199e70; }
}
.surface { fill: var(--surface); }
.title { fill: var(--text-primary); font-size: 18px; font-weight: 600; }
.vertex { fill: var(--text-primary); font-size: 15px; font-weight: 600; }
.label, .legend { fill: var(--text-secondary); font-size: 13px; }
.label, .vertex { paint-order: stroke; stroke: var(--surface); stroke-width: 4px; stroke-linejoin: round; }
.frame { stroke: var(--text-secondary); stroke-width: 1; fill: none; }
.core { fill: var(--series-1); fill-opacity: 0.12; stroke: var(--series-1); stroke-width: 2; stroke-linejoin: round; }
.core-edge { stroke: var(--series-1); stroke-width: 2; stroke-linecap: round; }
.kernel { stroke: var(--series-2); stroke-width: 3; stroke-linecap: round; }
.kernel-area { fill: var(--series-2); fill-opacity: 0.15; stroke: var(--series-2); stroke-width: 2; }
.kernel-dot { fill: none; stroke: var(--series-2); stroke-width: 2.5; }
.nucleolus { fill: var(--series-3); stroke: var(--surface); stroke-width: 2; }
.other { fill: var(--text-primary); stroke: var(--surface); stroke-width: 2; }
.hit { fill: transparent; }
.point:hover .nucleolus, .point:hover .other { stroke: var(--text-primary); }
</style>
"#;
fn text_width(text: &str, size: f64) -> f64 {
text.chars()
.map(|c| if c.is_ascii() { 0.55 * size } else { size })
.sum()
}
#[derive(Clone, Copy)]
struct Rect {
left: f64,
top: f64,
right: f64,
bottom: f64,
}
impl Rect {
fn around(x: f64, y: f64, radius: f64) -> Rect {
Rect {
left: x - radius,
top: y - radius,
right: x + radius,
bottom: y + radius,
}
}
fn label(x: f64, y: f64, anchor: &str, width: f64) -> Rect {
let left = if anchor == "start" { x } else { x - width };
Rect {
left,
top: y - 11.0,
right: left + width,
bottom: y + 3.0,
}
}
fn overlaps(&self, other: &Rect) -> bool {
self.left < other.right
&& other.left < self.right
&& self.top < other.bottom
&& other.top < self.bottom
}
}
fn escape(text: &str) -> String {
text.replace('&', "&")
.replace('<', "<")
.replace('>', ">")
}
fn format_allocation(x: &[f64]) -> String {
let values: Vec<String> = x.iter().map(|v| format!("{v:.4}")).collect();
format!("({})", values.join(", "))
}
struct Projection {
singles: Vec<f64>,
surplus: f64,
corners: Vec<[f64; 3]>,
}
impl Projection {
fn new(n: usize, singles: Vec<f64>, surplus: f64) -> Projection {
let h = 3f64.sqrt() / 2.0;
let corners = if n == 3 {
vec![[0.5, 0.0, 0.0], [0.0, h, 0.0], [1.0, h, 0.0]]
} else {
let raw = [
[0.0, 0.0, 0.0],
[1.0, 0.0, 0.0],
[0.5, h, 0.0],
[0.5, h / 3.0, (2.0f64 / 3.0).sqrt()],
];
let (theta, phi) = (0.45f64, 0.35f64);
raw.iter()
.map(|p| {
let (x, y) = (p[0] - 0.5, p[1] - h / 3.0);
let rx = x * theta.cos() - y * theta.sin();
let ry = x * theta.sin() + y * theta.cos();
let sy = -(p[2] * phi.cos()) + ry * phi.sin();
[rx, sy, 0.0]
})
.collect()
};
Projection {
singles,
surplus,
corners,
}
}
fn project(&self, x: &[f64]) -> (f64, f64) {
let mut point = (0.0, 0.0);
for (i, corner) in self.corners.iter().enumerate() {
let lambda = (x[i] - self.singles[i]) / self.surplus;
point.0 += lambda * corner[0];
point.1 += lambda * corner[1];
}
point
}
}
struct View {
scale: f64,
offset: (f64, f64),
}
impl View {
fn fit(points: &[(f64, f64)]) -> View {
let (mut min, mut max) = (
(f64::INFINITY, f64::INFINITY),
(f64::NEG_INFINITY, f64::NEG_INFINITY),
);
for p in points {
min = (min.0.min(p.0), min.1.min(p.1));
max = (max.0.max(p.0), max.1.max(p.1));
}
let (left, top, right, bottom) = (70.0, 80.0, 90.0, 80.0);
let width = (max.0 - min.0).max(1e-9);
let height = (max.1 - min.1).max(1e-9);
let scale = ((WIDTH - left - right) / width).min((HEIGHT - top - bottom) / height);
let offset = (
left + (WIDTH - left - right - scale * width) / 2.0 - scale * min.0,
top + (HEIGHT - top - bottom - scale * height) / 2.0 - scale * min.1,
);
View { scale, offset }
}
fn map(&self, p: (f64, f64)) -> (f64, f64) {
(
self.offset.0 + self.scale * p.0,
self.offset.1 + self.scale * p.1,
)
}
}
fn convex_order(points: &[(f64, f64)]) -> Vec<(f64, f64)> {
let count = points.len() as f64;
let center = points.iter().fold((0.0, 0.0), |acc, p| {
(acc.0 + p.0 / count, acc.1 + p.1 / count)
});
let mut ordered = points.to_vec();
ordered.sort_by(|a, b| {
(a.1 - center.1)
.atan2(a.0 - center.0)
.total_cmp(&(b.1 - center.1).atan2(b.0 - center.0))
});
ordered
}
fn core_constraints(game: &ExplicitGame) -> Vec<(Coalition, f64)> {
(1..game.grand().0)
.map(|mask| (Coalition(mask), game.value(Coalition(mask))))
.collect()
}
pub fn core_vertices(game: &ExplicitGame) -> Vec<Vec<f64>> {
let n = game.players();
let tolerance = 1e-9 * game.max_abs_value().max(1.0);
let constraints = core_constraints(game);
let total = game.value(game.grand());
let mut vertices: Vec<Vec<f64>> = Vec::new();
for_each_combination(constraints.len(), n - 1, &mut |chosen: &[usize]| {
let mut a: Vec<Vec<f64>> = chosen
.iter()
.map(|&k| indicator(constraints[k].0, n))
.collect();
let mut b: Vec<f64> = chosen.iter().map(|&k| constraints[k].1).collect();
a.push(vec![1.0; n]);
b.push(total);
let Some(x) = solve_square(a, b, 1e-12) else {
return;
};
let feasible = constraints.iter().all(|&(s, v)| s.sum(&x) >= v - tolerance);
let duplicate = vertices.iter().any(|y| {
y.iter()
.zip(&x)
.all(|(p, q)| (p - q).abs() <= 1e3 * tolerance)
});
if feasible && !duplicate {
vertices.push(x);
}
});
vertices
}
fn core_edges(game: &ExplicitGame, vertices: &[Vec<f64>]) -> Vec<(usize, usize)> {
let n = game.players();
let tolerance = 1e-7 * game.max_abs_value().max(1.0);
let constraints = core_constraints(game);
let tight: Vec<Vec<usize>> = vertices
.iter()
.map(|x| {
constraints
.iter()
.enumerate()
.filter(|(_, (s, v))| (s.sum(x) - v).abs() <= tolerance)
.map(|(k, _)| k)
.collect()
})
.collect();
let mut edges = Vec::new();
for a in 0..vertices.len() {
for b in a + 1..vertices.len() {
let common: Vec<usize> = tight[a]
.iter()
.copied()
.filter(|k| tight[b].contains(k))
.collect();
let mut span = crate::linalg::Span::new(n);
span.insert(&vec![1.0; n]);
for k in common {
span.insert_coalition(constraints[k].0);
}
if span.rank() >= n - 1 {
edges.push((a, b));
}
}
}
edges
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn three_player_figure_contains_core_kernel_and_points() {
let game = ExplicitGame::from_lex(&[-1.0, 0.0, 1.0, 3.0, 4.0, 2.0, 5.0]).unwrap();
let figure = imputation_figure(&game, &PlotOptions::default()).unwrap();
assert!(figure.svg.starts_with("<svg"));
assert!(figure.svg.contains("class=\"core\""));
assert!(!figure.core_vertices.is_empty());
for x in &figure.core_vertices {
assert!((x.iter().sum::<f64>() - 5.0).abs() < 1e-9);
assert!(crate::properties::is_in_core(&game, x, 1e-7));
}
assert_eq!(figure.points[0].0, Point::Nucleolus);
assert!(figure.svg.contains("仁: (2.6667, 0.6667, 1.6667)"));
}
#[test]
fn title_is_escaped() {
let majority = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let options = PlotOptions {
title: Some("<a> b&c".into()),
..PlotOptions::default()
};
let figure = imputation_figure(&majority, &options).unwrap();
assert!(!figure.svg.contains("<a>"));
assert!(!figure.svg.contains("b&c"));
assert!(figure.svg.contains("<a> b&c"));
}
#[test]
fn diamond_marks_only_the_shapley_value() {
let game = ExplicitGame::from_lex(&[-1.0, 0.0, 1.0, 3.0, 4.0, 2.0, 5.0]).unwrap();
let options = PlotOptions {
shapley: false,
points: vec![vec![2.0, 1.0, 2.0]],
..PlotOptions::default()
};
let figure = imputation_figure(&game, &options).unwrap();
assert!(!figure.svg.contains("rotate(45"));
let figure = imputation_figure(&game, &PlotOptions::default()).unwrap();
assert_eq!(figure.svg.matches("rotate(45").count(), 1);
}
#[test]
fn empty_core_and_four_players() {
let majority = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let figure = imputation_figure(&majority, &PlotOptions::default()).unwrap();
assert!(figure.core_vertices.is_empty());
assert!(figure.svg.contains("コア (空)"));
let game = ExplicitGame::from_lex(&[
0.0, 0.0, 0.0, 0.0, 5.0, 5.0, 8.0, 9.0, 10.0, 8.0, 13.0, 15.0, 16.0, 17.0, 21.0,
])
.unwrap();
let figure = imputation_figure(&game, &PlotOptions::default()).unwrap();
assert!(figure.core_vertices.len() >= 4);
assert!(figure.svg.contains("core-edge"));
for x in &figure.core_vertices {
assert!(crate::properties::is_in_core(&game, x, 1e-7));
}
}
#[test]
fn rejects_unsupported_games() {
assert!(
imputation_figure(
&crate::generators::bnf(1, 5, 0).unwrap(),
&PlotOptions::default()
)
.is_err()
);
let degenerate = ExplicitGame::from_lex(&[1.0, 1.0, 1.0, 2.0, 2.0, 2.0, 3.0]).unwrap();
assert!(imputation_figure(°enerate, &PlotOptions::default()).is_err());
}
}