algorithmica/graph/
mod.rs

1use std::fs::File;
2use std::io::{BufRead, BufReader};
3pub mod bfs;
4pub mod bipartite;
5pub mod connected_component;
6pub mod cycle;
7pub mod depth_first_paths;
8
9#[derive(Debug)]
10pub struct Graph {
11    pub v: usize,               // number of all nodes
12    pub e: usize,               // number of all edges
13    pub nodes: Vec<Vec<usize>>, // adjacency list for every which will
14}
15
16impl Graph {
17    pub fn new(v: usize) -> Self {
18        let mut nodes_vec = Vec::new();
19        for _ in 0..v {
20            nodes_vec.push(Vec::new())
21        }
22        Self {
23            v,
24            e: 0,
25            nodes: nodes_vec,
26        }
27    }
28
29    pub fn add_edge(&mut self, u: usize, w: usize) {
30        self.e += 1;
31        self.nodes[u].push(w);
32        self.nodes[w].push(u);
33    }
34
35    pub fn degree(&self, node: usize) -> usize {
36        self.adj(node).len()
37    }
38
39    pub fn is_edge(&self, u: usize, w: usize) -> bool {
40        self.adj(u).contains(&w)
41    }
42
43    pub(crate) fn adj(&self, node: usize) -> &Vec<usize> {
44        self.nodes.get(node).unwrap()
45    }
46
47    pub fn read_from_file(path: &str) -> Self {
48        let f1: BufReader<File> = BufReader::new(File::open(path).expect("Not able to read file"));
49        let mut it = f1.lines();
50        let n = it.next().unwrap().unwrap().parse::<usize>().unwrap();
51        let mut graph = Graph::new(n);
52        for line in it.map(|line| {
53            let l: Vec<usize> = line
54                .unwrap()
55                .trim()
56                .splitn(2, ' ')
57                .collect::<Vec<&str>>()
58                .into_iter()
59                .map(|x| x.trim().parse::<usize>().unwrap())
60                .collect::<Vec<usize>>();
61            (l[0], l[1])
62        }) {
63            graph.add_edge(line.0, line.1);
64        }
65        graph
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72    #[test]
73    fn test_read_file() {
74        let path = "../tests/graph.txt";
75        let g = Graph::read_from_file(path);
76        let dfs = depth_first_paths::DepthFirstPaths::new(0, &g);
77        println!(
78            "Has Path :: {:?}, Path:: {:?}",
79            dfs.has_path(7),
80            dfs.path(7)
81        );
82    }
83
84    #[test]
85    fn test_read_file2() {
86        let path = "../tests/graph2.txt";
87        let g = Graph::read_from_file(path);
88        let dfs = depth_first_paths::DepthFirstPaths::new(0, &g);
89        println!(
90            "Has Path :: {:?}, Path:: {:?}",
91            dfs.has_path(7),
92            dfs.path(7)
93        );
94    }
95
96    #[test]
97    fn connected_component() {
98        let path = "../tests/graph2.txt";
99        let g = Graph::read_from_file(path);
100        let cc = connected_component::ConnectedComponent::new(&g);
101        assert_eq!(cc.count(), 3924)
102    }
103
104    #[test]
105    fn connected_component2() {
106        let path = "../tests/graph2.txt";
107        let g = Graph::read_from_file(path);
108        let cc = connected_component::ConnectedComponent::new(&g);
109        assert_eq!(cc.id(3905), 233)
110    }
111
112    #[test]
113    fn connected_component3() {
114        let path = "../tests/graph3.txt";
115        let g = Graph::read_from_file(path);
116        let cc = connected_component::ConnectedComponent::new(&g);
117        assert_eq!(cc.count(), 3)
118    }
119
120    #[test]
121    fn bipartite() {
122        let path = "../tests/graph4.txt";
123        let g = Graph::read_from_file(path);
124        let bp = bipartite::Bipartite::new(&g, 0);
125        assert_eq!(bp.is_bipartite(), false)
126    }
127
128    #[ignore]
129    #[test]
130    fn bipartite_large() {
131        let path = "../tests/graph5.txt";
132        let g = Graph::read_from_file(path);
133        let bp = bipartite::Bipartite::new(&g, 0);
134        assert_eq!(bp.is_bipartite(), false)
135    }
136
137    #[ignore]
138    #[test]
139    fn cycle_large() {
140        let path = "../tests/graph5.txt";
141        let g = Graph::read_from_file(path);
142        let bp = cycle::Cycle::new(&g);
143        assert_eq!(bp.is_cycle(), true)
144    }
145}
146
147/*
148input type
1491. Number of nodes (n)
1502. Adjacency list (Relation ship) (u <-> w because undirected)
151*/
algorithmica/graph/mod.rs

algorithmica/graph/
mod.rs
