use crate::graph::{ Graph, DefaultGraph, Error };
use super::pairing::Pairing;
#[derive(Debug,PartialEq)]
pub struct Blossom {
id: usize,
path: Vec<usize>
}
impl Blossom {
pub fn new(
id: usize, mut left: Vec<usize>, mut right: Vec<usize>
) -> Self {
for i in 0..left.len() {
for j in 0..right.len() {
if left[i] == right[j] {
let root = left[i];
left = left[0..i].to_vec();
right = right[0..j].to_vec();
right.reverse();
left.push(root);
left.append(&mut right);
return Self { id, path: left }
}
}
}
panic!("blossom root not found")
}
pub fn contract_graph<'a, G: Graph>(
&self, graph: &'a G
) -> Result<DefaultGraph, Error> {
let mut result = DefaultGraph::new();
result.add_node(self.id)?;
for id in graph.ids() {
if !self.path.contains(&id) {
result.add_node(id)?;
}
}
for (sid, tid) in graph.edges() {
if self.path.contains(&sid) {
if !self.path.contains(&tid) {
if !result.has_edge(self.id, tid)? {
result.add_edge(self.id, tid)?;
}
}
} else if self.path.contains(&tid) {
if !result.has_edge(sid, self.id)? {
result.add_edge(sid, self.id)?;
}
} else {
result.add_edge(sid, tid)?;
}
}
Ok(result)
}
pub fn contract_pairing(&self, pairing: &Pairing) -> Pairing {
let mut result = Pairing::new();
for (sid, tid) in pairing.edges() {
if self.path.contains(&sid) {
if !self.path.contains(&tid) {
result.pair(self.id, tid);
}
} else if self.path.contains(&tid) {
result.pair(sid, self.id);
} else {
result.pair(sid, tid);
}
}
result
}
pub fn lift<'a, G: Graph>(
&self, path: Vec<usize>, graph: &'a G
) -> Vec<usize> {
let index = match path.iter().position(|&pid| pid == self.id) {
Some(index) => index,
None => return path
};
let left = path[0..index].to_vec();
let right = path[(index + 1)..].to_vec();
if left.is_empty() && right.is_empty() {
self.path.to_vec()
} else if !left.is_empty() && right.is_empty() {
self.lift_left_blossom(left, graph)
} else if left.is_empty() && !right.is_empty() {
self.lift_blossom_right(right, graph)
} else {
self.lift_left_blossom_right(left, right, graph)
}
}
fn lift_left_blossom<'a, G: Graph>(
&self, mut left: Vec<usize>, graph: &'a G
) -> Vec<usize> {
let sid = left.last().unwrap();
let mut copy = self.path.to_vec();
while !graph.has_edge(*sid, copy[0]).unwrap() {
copy.rotate_right(1);
}
left.append(&mut copy);
left
}
fn lift_blossom_right<'a, G: Graph>(
&self, mut right: Vec<usize>, graph: &'a G
) -> Vec<usize> {
let tid = right[0];
let mut copy = self.path.to_vec();
while !graph.has_edge(*copy.last().unwrap(), tid).unwrap() {
copy.rotate_right(1);
}
copy.append(&mut right);
copy
}
fn lift_left_blossom_right<'a, G: Graph>(
&self, left: Vec<usize>, right: Vec<usize>, graph: &'a G
) -> Vec<usize> {
let &sid = left.last().unwrap();
let mut forward_blossom = self.path.to_vec();
let mut forward = left.to_vec();
while !graph.has_edge(sid, forward_blossom[0]).unwrap() {
forward_blossom.rotate_right(1);
}
let &tid = &right[0];
for &bid in &forward_blossom {
forward.push(bid);
if graph.has_edge(bid, tid).unwrap() {
break;
}
}
forward.extend(right.iter());
if forward.len() % 2 == 0 {
return forward
}
let mut reverse = left.to_vec();
let mut reverse_blossom = self.path.to_vec();
reverse_blossom.reverse();
while !graph.has_edge(sid, reverse_blossom[0]).unwrap() {
reverse_blossom.rotate_right(1);
}
for &bid in &reverse_blossom {
reverse.push(bid);
if graph.has_edge(bid, tid).unwrap() {
break;
}
}
reverse.extend(right.iter());
reverse
}
}
#[cfg(test)]
mod new {
use super::*;
#[test]
#[should_panic(expected="blossom root not found")]
fn different_roots() {
Blossom::new(1, vec![ 2, 1, 0 ], vec![ 5, 4, 3 ]);
}
#[test]
fn root_at_right() {
let blossom = Blossom::new(1, vec![ 2, 1, 0 ], vec![ 5, 4, 0 ]);
assert_eq!(blossom.path, vec![ 2, 1, 0, 4, 5 ])
}
#[test]
fn root_inside() {
let blossom = Blossom::new(1, vec![
4, 3, 2, 1, 0
], vec![
7, 6, 2, 1, 0
]);
assert_eq!(blossom.path, vec![ 4, 3, 2, 6, 7 ])
}
}
#[cfg(test)]
mod contract_graph {
use std::convert::TryFrom;
use super::*;
#[test]
fn butterfly_tid_inside() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 0), (3, 2), (3, 1)
]).unwrap();
let blossom = Blossom::new(4, vec![0], vec![ 1, 2, 0 ]);
let contracted = blossom.contract_graph(&graph);
assert_eq!(contracted, DefaultGraph::try_from(vec![
(3, 4)
]))
}
#[test]
fn butterfly_sid_inside() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 0), (2, 3), (1, 3)
]).unwrap();
let blossom = Blossom::new(4, vec![0], vec![ 1, 2, 0 ]);
let contracted = blossom.contract_graph(&graph);
assert_eq!(contracted, DefaultGraph::try_from(vec![
(3, 4)
]))
}
#[test]
fn sid_inside() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (4, 5), (5, 6)
]).unwrap();
let blossom = Blossom::new(7, vec![ 4, 0, 1 ], vec![ 3, 2, 1 ]);
let contracted = blossom.contract_graph(&graph);
assert_eq!(contracted, DefaultGraph::try_from(vec![
(6, 5), (5, 7)
]))
}
#[test]
fn tid_inside() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (5, 4), (5, 6)
]).unwrap();
let blossom = Blossom::new(7, vec![ 4, 0, 1 ], vec![ 3, 2, 1 ]);
let contracted = blossom.contract_graph(&graph);
assert_eq!(contracted, DefaultGraph::try_from(vec![
(6, 5), (5, 7)
]))
}
#[test]
fn example_causes_double_edge() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8),
(8, 2), (6, 1)
]).unwrap();
let blossom = Blossom::new(9, vec![ 8, 2, 3, 4 ], vec![ 7, 6, 5, 4 ]);
let contracted = blossom.contract_graph(&graph);
assert_eq!(contracted, DefaultGraph::try_from(vec![
(0, 1), (1, 9)
]))
}
}
#[cfg(test)]
mod contract_pairing {
use super::*;
#[test]
fn sid_inside() {
let blossom = Blossom::new(5, vec![ 2, 1, 0 ], vec![ 4, 3, 0 ]);
let mut pairing = Pairing::new();
pairing.pair(7, 8);
pairing.pair(1, 6);
let mut expected = Pairing::new();
expected.pair(7, 8);
expected.pair(5, 6);
assert_eq!(blossom.contract_pairing(&pairing), expected);
}
#[test]
fn tid_inside() {
let blossom = Blossom::new(5, vec![ 2, 1, 0 ], vec![ 4, 3, 0 ]);
let mut pairing = Pairing::new();
pairing.pair(7, 8);
pairing.pair(6, 1);
let mut expected = Pairing::new();
expected.pair(7, 8);
expected.pair(6, 5);
assert_eq!(blossom.contract_pairing(&pairing), expected);
}
#[test]
fn sid_tid_inside() {
let blossom = Blossom::new(5, vec![ 2, 1, 0 ], vec![ 4, 3, 0 ]);
let mut pairing = Pairing::new();
pairing.pair(7, 8);
pairing.pair(2, 1);
let mut expected = Pairing::new();
expected.pair(7, 8);
assert_eq!(blossom.contract_pairing(&pairing), expected);
}
}
#[cfg(test)]
mod lift {
use::std::convert::TryFrom;
use super::*;
#[test]
fn missing_blossom_id() {
let graph = DefaultGraph::try_from(vec![
(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)
]).unwrap();
let blossom = Blossom::new(5, vec![ 2, 1, 0 ], vec![ 4, 3, 0 ]);
let path = vec![ 8, 9, 10, 11 ];
assert_eq!(blossom.lift(path, &graph), vec![
8, 9, 10, 11
])
}
#[test]
fn none_blossom_none() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)
]).unwrap();
let blossom = Blossom::new(5, vec![ 2, 1, 0 ], vec![ 4, 3, 0 ]);
let path = vec![ 5 ];
assert_eq!(blossom.lift(path, &graph), vec![
2, 1, 0, 3, 4
])
}
#[test]
fn left_blossom_none() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 1)
]).unwrap();
let blossom = Blossom::new(6, vec![ 1, 2, 3 ], vec![ 5, 4, 3 ]);
let path = vec![ 0, 6 ];
assert_eq!(blossom.lift(path, &graph), vec![
0, 1, 2, 3, 4, 5
])
}
#[test]
fn left_blossom_none_rotated_twice() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 1)
]).unwrap();
let blossom = Blossom::new(6, vec![ 2, 3, 4 ], vec![ 1, 5, 4 ]);
let path = vec![ 0, 6 ];
assert_eq!(blossom.lift(path, &graph), vec![
0, 1, 2, 3, 4, 5
])
}
#[test]
fn none_blossom_right() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 1)
]).unwrap();
let blossom = Blossom::new(6, vec![ 2, 3, 4 ], vec![ 1, 5, 4 ]);
let path = vec![ 6, 0 ];
assert_eq!(blossom.lift(path, &graph), vec![
2, 3, 4, 5, 1, 0
])
}
#[test]
fn left_blossom_right() {
let graph = DefaultGraph::try_from(vec![
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (3, 6)
]).unwrap();
let blossom = Blossom::new(7, vec![ 2, 3, 4 ], vec![ 1, 5, 4 ]);
let path = vec![ 0, 7, 6 ];
assert_eq!(blossom.lift(path, &graph), vec![
0, 1, 5, 4, 3, 6
])
}
#[test]
fn left_blossom_right_shifted() {
let graph = DefaultGraph::try_from(vec![
(0, 5), (5, 1), (1, 2), (2, 3), (3, 4), (4, 5), (3, 6)
]).unwrap();
let blossom = Blossom::new(7, vec![ 2, 3, 4 ], vec![ 1, 5, 4 ]);
let path = vec![ 0, 7, 6 ];
assert_eq!(blossom.lift(path, &graph), vec![
0, 5, 1, 2, 3, 6
])
}
}