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

use crate::DirectedBijectiveConnectionGraph;
use gt_graph::{Dims, Node};
use gt_graph_path::GraphPath;

pub trait SinglePath {
    fn single_path(&self, s: Node, d: Node) -> GraphPath;
}

impl<F> SinglePath for F
where
    F: DirectedBijectiveConnectionGraph,
{
    fn single_path(&self, s: Node, d: Node) -> GraphPath {
        let mut path = GraphPath::new(self);
        path.push(s);

        single_path_helper(self, self.dimension(), s, d, &mut path);

        path
    }
}

fn single_path_helper<F>(graph: &F, n: Dims, s: Node, d: Node, path: &mut GraphPath)
where
    F: DirectedBijectiveConnectionGraph,
{
    // if same: do nothing
    if s == d {
        return;
    }

    // Step 1
    if n == 1 {
        path.push(s ^ 1);
        return;
    }

    // Step 2
    let mask = 1 << (n - 1);
    if s & mask == d & mask {
        single_path_helper(graph, n - 1, s, d, path);
        return;
    }

    // Step 3
    let phi_s;
    phi_s = graph.phi(n, s);
    path.push(phi_s);
    single_path_helper(graph, n - 1, phi_s, d, path);
}