bfs - rust

bfs.rs

use std::cmp::Ordering;
use std::cmp::PartialEq;
use std::collections::BTreeMap;
use std::collections::HashMap;
use std::collections::VecDeque;

#[derive(Debug, Eq, PartialOrd)]
struct GraphNode {
    id: i32,
    adjacent: Vec<i32>,
}

impl PartialEq for GraphNode {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl Ord for GraphNode {
    fn cmp(&self, other: &Self) -> Ordering {
        self.id.cmp(&other.id)
    }
}

#[derive(Debug)]
struct GraphNodePair {
    from: GraphNode,
    to: GraphNode,
}

struct Graph {
    nodes: Vec<GraphNode>,
}

fn bfs(g: &Graph, start: &GraphNode, goal: &GraphNode) -> (Vec<GraphNodePair>, bool) {
    let mut g_map: HashMap<i32, &GraphNode> = Default::default();
    for node in g.nodes.iter() {
        g_map.insert(node.id, node);
    }
    let mut path_found = false;
    let mut q: VecDeque<i32> = VecDeque::new();
    let mut out_map: BTreeMap<i32, GraphNode> = BTreeMap::new();
    let mut out: Vec<GraphNodePair> = vec![];

    q.push_back(start.id);
    while !q.is_empty() {
        let current_id = q.pop_front().unwrap();
        let current = g_map.get(&current_id).unwrap();

        if current_id == goal.id {
            path_found = true;
            break;
        }

        for node_id in current.adjacent.iter() {
            match out_map.get(node_id) {
                None => {
                    if *node_id != start.id {
                        let node = g_map.get(node_id).unwrap();
                        q.push_back(*node_id);
                        out.push(GraphNodePair {
                            from: GraphNode {
                                id: current.id,
                                adjacent: current.adjacent.clone(),
                            },
                            to: GraphNode {
                                id: *node_id,
                                adjacent: node.adjacent.clone(),
                            },
                        });
                        out_map.insert(
                            *node_id,
                            GraphNode {
                                id: current.id,
                                adjacent: current.adjacent.clone(),
                            },
                        );
                    }
                }
                _ => {}
            }
        }
    }

    (out, path_found)
}

mod tests {
    use super::*;

    #[test]
    fn test_equal_graph_node() {
        let a = GraphNode {
            id: 1,
            adjacent: Vec::new(),
        };
        let b: GraphNode = GraphNode {
            id: 1,
            adjacent: Vec::new(),
        };
        assert!(a == b)
    }

    #[test]
    fn test_not_equal_graph_node() {
        let a = GraphNode {
            id: 1,
            adjacent: Vec::new(),
        };
        let b: GraphNode = GraphNode {
            id: 2,
            adjacent: Vec::new(),
        };
        assert!(a != b)
    }

    fn create_3x3_ippon_graph() -> Graph {
        // 01 → 02 → 03
        //           ↓
        // 0４ ← 05　← 06
        // ↓
        // 07 →　08　→ 09
        Graph {
            nodes: vec![
                GraphNode {
                    id: 1,
                    adjacent: vec![2],
                },
                GraphNode {
                    id: 2,
                    adjacent: vec![1, 3],
                },
                GraphNode {
                    id: 3,
                    adjacent: vec![2, 6],
                },
                GraphNode {
                    id: 4,
                    adjacent: vec![5, 7],
                },
                GraphNode {
                    id: 5,
                    adjacent: vec![4, 6],
                },
                GraphNode {
                    id: 6,
                    adjacent: vec![3, 5],
                },
                GraphNode {
                    id: 7,
                    adjacent: vec![4, 8],
                },
                GraphNode {
                    id: 8,
                    adjacent: vec![7, 9],
                },
                GraphNode {
                    id: 9,
                    adjacent: vec![8],
                },
            ],
        }
    }

    fn create_3x3_ikidomari_graph() -> Graph {
        // 01 → 02 → 03
        //           ↓
        // 0４   05　← 06
        // ↑         ↓
        // 07 →　08　→ 09
        Graph {
            nodes: vec![
                GraphNode {
                    id: 1,
                    adjacent: vec![2],
                },
                GraphNode {
                    id: 2,
                    adjacent: vec![1, 3],
                },
                GraphNode {
                    id: 3,
                    adjacent: vec![2, 6],
                },
                GraphNode {
                    id: 4,
                    adjacent: vec![7],
                },
                GraphNode {
                    id: 5,
                    adjacent: vec![6],
                },
                GraphNode {
                    id: 6,
                    adjacent: vec![3, 5, 9],
                },
                GraphNode {
                    id: 7,
                    adjacent: vec![4, 8],
                },
                GraphNode {
                    id: 8,
                    adjacent: vec![7, 9],
                },
                GraphNode {
                    id: 9,
                    adjacent: vec![6, 8],
                },
            ],
        }
    }

    #[test]
    fn test_bfs_1() {
        let g = create_3x3_ippon_graph();
        let start = &g.nodes[0];
        let goal = &g.nodes[8];
        let (out, found_path) = bfs(&g, start, goal);

        let got = out.iter().map(|v| (v.from.id, v.to.id)).collect::<Vec<_>>();
        println!("{:?}", got);
        assert_eq!(got.len(), 8);
        assert_eq!(found_path, true);
        assert_eq!(
            got,
            vec![
                (1, 2),
                (2, 3),
                (3, 6),
                (6, 5),
                (5, 4),
                (4, 7),
                (7, 8),
                (8, 9)
            ]
        );
    }

    #[test]
    fn test_bfs_2() {
        let g = create_3x3_ikidomari_graph();
        let start = &g.nodes[0];
        let goal = &g.nodes[3];
        let (out, found_path) = bfs(&g, start, goal);

        let got = out.iter().map(|v| (v.from.id, v.to.id)).collect::<Vec<_>>();
        println!("{:?}", got);
        assert_eq!(got.len(), 8);
        assert_eq!(found_path, true);
        assert_eq!(
            got,
            vec![
                (1, 2),
                (2, 3),
                (3, 6),
                (6, 5),
                (6, 9),
                (9, 8),
                (8, 7),
                (7, 4)
            ]
        );
    }
}