1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

use crate::directed_bijective_connection_graph::lemma1::Lemma1;
use crate::directed_bijective_connection_graph::lemma2::Lemma2;
use crate::directed_bijective_connection_graph::node_to_set::NodeToSet;
use crate::node_path::NodePath;
use crate::{Dims, DirectedBijectiveConnectionGraphFunctions, Node};

pub trait NodeToNode {
    #[allow(non_snake_case)]
    fn N2N(&self, s: Node, d: Node) -> Vec<NodePath>;
    fn node_to_node(&self, s: Node, d: Node) -> Vec<NodePath>;
    fn node_to_node_helper(&self, n: Dims, s: Node, d: Node) -> Vec<NodePath>;
}

impl<F> NodeToNode for F
where
    F: DirectedBijectiveConnectionGraphFunctions + Lemma2 + Lemma1 + NodeToSet,
{
    #[allow(non_snake_case)]
    #[inline(always)]
    fn N2N(&self, s: Node, d: Node) -> Vec<NodePath> {
        self.node_to_node(s, d)
    }

    #[inline(always)]
    fn node_to_node(&self, s: Node, d: Node) -> Vec<NodePath> {
        self.node_to_node_helper(self.dimension(), s, d)
    }

    fn node_to_node_helper(&self, n: Dims, s: Node, d: Node) -> Vec<NodePath> {
        let mut paths;

        let mask = 1 << (n - 1);

        if s & mask == d & mask {
            paths = self.node_to_node_helper(n - 1, s, d);

            let mut path = NodePath::new(self);
            path.push_back(s);
            let phi_s = self.phi(n, s);
            path.push_back(phi_s);
            self.R_helper(n, phi_s, self.psi(n, d), &mut path);
            path.push_back(d);

            paths.push(path);
        } else {
            let mut path = NodePath::new(self);
            path.push_back(s);
            let phi_s = self.phi(n, s);
            path.push_back(phi_s);
            self.R_helper(n, phi_s, d, &mut path);

            let neighbor_node = path.inner_path()[path.inner_path().len() - 2];

            let lemma1_except_neighbor = self
                .lemma1(n, d)
                .into_iter()
                .filter(|path| !path.inner_path().contains(&neighbor_node))
                .collect::<Vec<_>>();

            let ds = lemma1_except_neighbor
                .iter()
                .map(|path| path.inner_path()[0])
                .collect::<Vec<_>>();

            let mut partial_paths = self.node_to_set(s, &ds);
            partial_paths
                .iter_mut()
                .zip(lemma1_except_neighbor.iter())
                .for_each(|(partial, lemma1)| {
                    partial
                        .inner_path_mut()
                        .extend(lemma1.inner_path().iter().skip(1))
                });

            paths = partial_paths;
            paths.push(path);
        }

        paths
    }
}

#[cfg(test)]
mod test {
    use crate::graphs::HyperCube;
    use crate::NodeToNode;

    #[test]
    fn node_to_set() {
        let graph = HyperCube::new(4);

        let s = 0b0000;
        let d = 0b1111;

        let paths = graph.node_to_node(s, d);

        assert_eq!(paths.len(), 4);
        assert!(paths
            .iter()
            .take(paths.len() - 1)
            .zip(paths.iter().skip(1))
            .all(|(p1, p2)| p1 != p2));
        paths.iter().for_each(|path| {
            assert!(path.is_valid());
            assert_eq!(path.inner_path().first().unwrap(), &0b0000);
            assert_eq!(path.inner_path().last().unwrap(), &0b1111);
        })
    }
}