librualg/graph/
mod.rs

1use std::collections::{BTreeSet, VecDeque, BTreeMap, BinaryHeap};
2use std::option::Option::Some;
3use std::cmp::{Ordering};
4use crate::dsu::{DSU, DSUNum};
5
6#[derive(Copy, Clone, PartialOrd, PartialEq)]
7enum Color {
8    White = 0,
9    Grey = 1,
10    Black = 2
11}
12
13impl Default for Color {
14    fn default() -> Self {
15        Color::White
16    }
17}
18
19pub struct VertexProperties<Indent> where Indent: Eq + Ord + Clone {
20    parent: Option<Indent>,
21    #[allow(dead_code)]
22    color: Color,
23    #[allow(dead_code)]
24    time_in: Option<u32>,
25    #[allow(dead_code)]
26    time_out: Option<u32>
27}
28
29#[derive(Clone)]
30struct Edge <Indent> where Indent: Eq + Ord + Clone {
31    to: Indent,
32    weight: f32,
33}
34
35pub struct Graph <Indent> where Indent: Eq + Ord + Clone {
36    adj: BTreeMap<Indent, Vec<Edge<Indent>>>,
37}
38
39impl<Indent> Default for Graph<Indent> where Indent: Eq + Ord + Clone {
40    fn default() -> Self {
41        Graph { adj: BTreeMap::new() }
42    }
43}
44
45impl <Indent> Graph <Indent> where Indent: Eq + Ord + Clone {
46    pub fn new() -> Self {
47        Graph::default()
48    }
49
50    /// BFS (Breadth-First Search) algorithm.
51    /// Returns an ancestor vector along the graph traversal path
52    ///```
53    /// use librualg::graph::Graph;
54    ///
55    /// let mut graph = Graph::new();
56    /// graph.add_oriented_edge(1, 2, 0.0);
57    /// graph.add_oriented_edge(2, 3, 0.0);
58    /// graph.add_oriented_edge(2, 4, 0.0);
59    /// graph.add_oriented_edge(2, 5, 0.0);
60    /// graph.add_oriented_edge(4, 8, 0.0);
61    /// graph.add_oriented_edge(8, 17, 0.0);
62    /// let parents = graph.bfs(1);
63    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
64    /// assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
65    /// ```
66
67    pub fn bfs(&self, from: Indent) -> BTreeMap::<Indent, VertexProperties<Indent>> {
68        let mut queue = VecDeque::new();
69        let mut parents = BTreeMap::<Indent, VertexProperties<Indent>>::new();
70        let mut visited = BTreeSet::new();
71
72        if self.adj.get(&from).is_some() {
73            queue.push_back(&from);
74            visited.insert(&from);
75            parents.insert(Clone::clone(&from), VertexProperties {parent: None, time_in: None, time_out: None, color: Color::White});
76            while let Some(vertex) = queue.pop_front(){
77                if self.adj.get(&vertex).is_some() {
78                    for edge in self.adj.get(&vertex).unwrap().iter() {
79                        if !visited.contains(&edge.to) {
80                            parents.insert(edge.to.clone(), VertexProperties {parent: Some(vertex.clone()), time_in: None, time_out: None, color: Color::White});
81                            queue.push_back(&edge.to);
82                            visited.insert(&edge.to);
83                        }
84                    }
85                }
86            }
87        }
88        parents
89    }
90
91    fn _dfs(&self, from: Indent, timer: &mut u32,  parents: &mut BTreeMap::<Indent, VertexProperties<Indent>>, colors: &mut BTreeMap::<Indent, Color>) {
92        *timer += 1;
93        colors.insert(from.clone(), Color::Grey);
94        if self.adj.get(&from).is_some() {
95            for edge in self.adj.get(&from).unwrap().iter() {
96                if colors.get(&edge.to).is_none() {
97                    parents.insert(edge.to.clone(), VertexProperties{parent: Some(from.clone()), time_in: None, time_out: None, color: Color::White});
98                    self._dfs(edge.to.clone(), timer, parents, colors);
99                }
100            }
101        }
102        *(colors.get_mut(&from).unwrap()) = Color::Black;
103        *timer += 1;
104        parents.get_mut(&from).unwrap().time_out = Some(*timer);
105        parents.get_mut(&from).unwrap().color = Color::Black;
106    }
107
108    /// DFS (Depth-First Search) algorithm.
109    /// Returns an ancestor vector along the graph traversal path
110    ///```
111    /// use librualg::graph::Graph;
112    ///
113    /// let mut graph = Graph::new();
114    /// graph.add_oriented_edge(1, 2, 0.0);
115    /// graph.add_oriented_edge(2, 3, 0.0);
116    /// graph.add_oriented_edge(3, 5, 0.0);
117    ///
118    /// let res = graph.dfs(1);
119    /// assert_eq!(graph.search_path(5, &res).unwrap(), vec![1, 2, 3, 5]);
120    /// ```
121
122    pub fn dfs(&self, from: Indent) -> BTreeMap::<Indent, VertexProperties<Indent>> {
123        let mut parents = BTreeMap::<Indent, VertexProperties<Indent>>::new();
124        let mut colors = BTreeMap::<Indent, Color>::new();
125        let mut timer = 0;
126        parents.insert(from.clone(), VertexProperties{parent: None, time_in: Some(timer), time_out: None, color: Color::White});
127        self._dfs(from, &mut timer, &mut parents, &mut colors);
128        parents
129    }
130
131    /// Dijkstra algorithm.
132    /// Returns an ancestor vector along the graph traversal path and distances to the other vertexs
133    ///```
134    /// use librualg::graph::Graph;
135    ///
136    /// let mut graph = Graph::new();
137    /// graph.add_oriented_edge(1, 2, 2.0);
138    /// graph.add_oriented_edge(2, 3, 5.0);
139    /// graph.add_oriented_edge(3, 5, 7.0);
140    /// graph.add_oriented_edge(1, 5, 19.0);
141    ///
142    /// let (parents, distances) = graph.dijkstra(1);
143    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 3, 5]);
144    /// assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
145    /// assert_eq!(*distances.get(&5).unwrap(), 14.0);
146    /// ```
147
148
149    pub fn dijkstra(&self, from: Indent) -> (BTreeMap::<Indent, VertexProperties<Indent>>, BTreeMap::<Indent, f32>) {
150        let mut parents = BTreeMap::<Indent, VertexProperties<Indent>>::new();
151        let mut visited = BTreeSet::<Indent>::new();
152        let mut distances = BTreeMap::<Indent, f32>::new();
153
154        struct D<Indent> {
155            node: Indent,
156            dist: f32,
157        }
158
159        impl <Indent> std::cmp::PartialEq for D<Indent> {
160            fn eq(&self, other: &D<Indent>) -> bool {
161                self.dist == other.dist
162            }
163        }
164
165        impl <Indent> Eq for D<Indent> {}
166
167        impl <Indent> std::cmp::Ord for D<Indent> {
168            fn cmp(&self, other: &Self) -> Ordering {
169                other.dist.partial_cmp(&self.dist).unwrap()
170            }
171        }
172
173        impl <Indent> std::cmp::PartialOrd for D <Indent> {
174            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
175                Some(other.dist.partial_cmp(&self.dist).unwrap())
176            }
177        }
178
179        let mut heap = BinaryHeap::<D<Indent>>::new();
180        distances.insert(from.clone(), 0.0);
181        heap.push(D{ node: from, dist: 0.0});
182        while !heap.is_empty() {
183            let d = heap.pop().unwrap();
184            visited.insert(d.node.clone());
185            if self.adj.get(&d.node).is_some() {
186                for edge in self.adj.get(&d.node).unwrap() {
187                    if !visited.contains(&edge.to) && edge.weight + d.dist < *distances.get(&edge.to).unwrap_or(&f32::MAX) {
188                        parents.insert(edge.to.clone(), VertexProperties{parent: Some(d.node.clone()), time_in: None, time_out: None, color: Color::White});
189                        distances.insert(edge.to.clone(), edge.weight + d.dist);
190                        heap.push(D{node: edge.to.clone(), dist: *distances.get(&edge.to).unwrap()});
191                    }
192                }
193            }
194        }
195        (parents, distances)
196    }
197
198    /// Get connected components
199    ///```
200    /// use librualg::graph::Graph;
201    ///
202    /// let mut graph = Graph::new();
203    /// graph.add_oriented_edge(1, 2, 0.0);
204    /// graph.add_oriented_edge(2, 3, 0.0);
205    /// graph.add_oriented_edge(3, 4, 0.0);
206    ///
207    /// graph.add_oriented_edge(5, 6, 0.0);
208    /// graph.add_oriented_edge(6, 7, 0.0);
209    ///
210    /// graph.add_oriented_edge(8, 9, 0.0);
211    /// graph.add_oriented_edge(9, 10, 0.0);
212    /// graph.add_oriented_edge(10, 11, 0.0);
213    ///
214    /// let components = graph.connected_components();
215    /// assert_eq!(components[0], [1, 2, 3, 4]);
216    /// assert_eq!(components[1], [5, 6, 7]);
217    /// assert_eq!(components[2], [8, 9, 10, 11]);
218    /// ```
219
220    pub fn connected_components(&self) -> Vec<Vec<Indent>> {
221        let mut components = vec![];
222        let mut visited = BTreeSet::new();
223        for vertex in self.adj.keys() {
224            if !visited.contains(vertex) {
225                let mut queue = VecDeque::new();
226                let mut vec = vec![];
227                visited.insert(vertex);
228                queue.push_back(vertex);
229                while let Some(vertex) = queue.pop_front(){
230                    vec.push(vertex.clone());
231                    if self.adj.get(&vertex).is_some() {
232                        for edge in self.adj.get(&vertex).unwrap().iter() {
233                            if !visited.contains(&edge.to) {
234                                queue.push_back(&edge.to);
235                                visited.insert(&edge.to);
236                            }
237                        }
238                    }
239                }
240                components.push(vec)
241            }
242        }
243        components
244    }
245
246    /// Get strongly connected components
247    /// ```
248    /// use librualg::graph::Graph;
249    ///
250    /// let mut graph = Graph::new();
251    /// graph.add_oriented_edge("a", "b", 0.0);
252    /// graph.add_oriented_edge("b", "f", 0.0);
253    /// graph.add_oriented_edge("e", "a", 0.0);
254    /// graph.add_oriented_edge("b", "e", 0.0);
255    /// graph.add_oriented_edge("e", "f", 0.0);
256    ///
257    /// graph.add_oriented_edge("b", "c", 0.0);
258    /// graph.add_oriented_edge("f", "g", 0.0);
259    /// graph.add_oriented_edge("g", "f", 0.0);
260    /// graph.add_oriented_edge("c", "g", 0.0);
261    ///
262    /// graph.add_oriented_edge("c", "d", 0.0);
263    /// graph.add_oriented_edge("d", "c", 0.0);
264    /// graph.add_oriented_edge("d", "h", 0.0);
265    /// graph.add_oriented_edge("h", "d", 0.0);
266    /// graph.add_oriented_edge("h", "g", 0.0);
267    ///
268    /// let components = graph.strongly_connected_components();
269    /// assert_eq!(components[0], ["a", "b", "e"]);
270    /// assert_eq!(components[1], ["c", "d", "h"]);
271    /// assert_eq!(components[2], ["f", "g"]);
272    ///```
273
274    pub fn strongly_connected_components(&self) -> Vec<Vec<Indent>> {
275        let mut components = vec![];
276        let mut graph_transp = Graph::new();
277        for (vertex, edges) in &self.adj {
278            for edge in edges {
279                graph_transp.add_oriented_edge(edge.to.clone(), vertex.clone(), edge.weight);
280            }
281        }
282        let mut visited = BTreeSet::new();
283        let mut orders = Vec::with_capacity(self.adj.len());
284        for vertex in self.adj.keys(){
285            if !visited.contains(vertex) {
286                for (vertex, _) in self.dfs(vertex.clone()){
287                    if !visited.contains(&vertex) {
288                        visited.insert(vertex.clone());
289                        orders.push(vertex.clone());
290                    }
291                }
292            }
293        }
294        visited.clear();
295        for vertex in &orders {
296            if !visited.contains(vertex) {
297                let mut vec = vec![];
298                for (vertex, _) in graph_transp.dfs(vertex.clone()) {
299                    if !visited.contains(&vertex) {
300                        visited.insert(vertex.clone());
301                        vec.push(vertex);
302                    }
303                }
304                components.push(vec);
305            }
306        }
307        components
308    }
309
310    /// Topologic sort
311    /// ```
312    /// use librualg::graph::Graph;
313    /// let mut graph = Graph::new();
314    /// graph.add_oriented_edge("a", "b", 0.0);
315    /// graph.add_oriented_edge("a", "c", 0.0);
316    /// graph.add_oriented_edge("a", "e", 0.0);
317    /// graph.add_oriented_edge("a", "d", 0.0);
318    /// graph.add_oriented_edge("b", "d", 0.0);
319    /// graph.add_oriented_edge("c", "d", 0.0);
320    /// graph.add_oriented_edge("c", "e", 0.0);
321    ///
322    /// assert_eq!(graph.topological_sort(), vec!["a", "b", "c", "d", "e"]);
323    ///```
324
325    pub fn topological_sort(&self) -> Vec<Indent> {
326        let mut visited = BTreeSet::new();
327        let mut topology_vec = Vec::with_capacity(self.adj.len());
328        for vertex in self.adj.keys() {
329            if !visited.contains(vertex) {
330                for (vertex, _) in self.dfs(vertex.clone()).iter(){
331                    if !visited.contains(vertex) {
332                        visited.insert(vertex.clone());
333                        topology_vec.push(vertex.clone());
334                    }
335                }
336            }
337        }
338        topology_vec
339    }
340
341    /// Kruskal's algorithm
342    /// ```
343    /// use librualg::graph::Graph;
344    ///
345    /// let mut graph = Graph::new();
346    /// graph.add_oriented_edge('A', 'B', 7.0);
347    /// graph.add_oriented_edge('B', 'A', 7.0);
348    /// graph.add_oriented_edge('A', 'D', 5.0);
349    /// graph.add_oriented_edge('D', 'A', 5.0);
350    /// let tree = graph.kruskal();
351    /// ```
352
353    pub fn kruskal(&self) -> Graph<Indent> {
354
355        struct D<Indent> {
356            from: Indent,
357            to: Indent,
358            dist: f32,
359        }
360
361        impl <Indent> std::cmp::PartialEq for D<Indent> {
362            fn eq(&self, other: &D<Indent>) -> bool {
363                self.dist == other.dist
364            }
365        }
366
367        impl <Indent> Eq for D<Indent> {}
368
369        impl <Indent> std::cmp::Ord for D<Indent> {
370            fn cmp(&self, other: &Self) -> Ordering {
371                other.dist.partial_cmp(&self.dist).unwrap()
372            }
373        }
374
375        impl <Indent> std::cmp::PartialOrd for D <Indent> {
376            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
377                Some(other.dist.partial_cmp(&self.dist).unwrap())
378            }
379        }
380
381        let mut graph: Graph<Indent> = Graph::new();
382        let mut heap = BinaryHeap::new();
383        let mut dsu = DSU::new();
384        for (from, edges) in &self.adj {
385            dsu.make_set(from.clone());
386            for edge in edges {
387                heap.push(D{
388                    from: from.clone(),
389                    to: edge.to.clone(),
390                    dist: edge.weight
391                });
392            }
393        }
394
395        while let Some (value) = heap.pop() {
396            if dsu.find_set(value.from.clone()) != dsu.find_set(value.to.clone()) {
397                dsu.union_sets(value.from.clone(), value.to.clone());
398                graph.add_oriented_edge(value.from.clone(), value.to.clone(), value.dist);
399                graph.add_oriented_edge(value.to.clone(), value.from.clone(), value.dist);
400            }
401        }
402        graph
403    }
404
405    /// Adds a new oriented edge to the graph
406    pub fn add_oriented_edge(&mut self, from: Indent, to: Indent, weight: f32) {
407        match self.adj.get_mut(&from) {
408            Some(ref mut vertex) => {
409                vertex.push(Edge { to, weight});
410            }
411            None => {
412                let seq = vec![Edge { to, weight}];
413                self.adj.insert(from, seq);
414            }
415        }
416    }
417
418    /// Returns the path in the graph between two vertices based on the ancestor vector
419    /// Returns None if the path does not exist
420    /// ```
421    /// use librualg::graph::Graph;
422    ///
423    /// let mut graph = Graph::new();
424    /// graph.add_oriented_edge(1, 2, 0.0);
425    /// graph.add_oriented_edge(2, 3, 0.0);
426    /// graph.add_oriented_edge(2, 4, 0.0);
427    /// graph.add_oriented_edge(2, 5, 0.0);
428    /// graph.add_oriented_edge(4, 8, 0.0);
429    /// graph.add_oriented_edge(8, 17, 0.0);
430    /// let parents = graph.bfs(1);
431    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
432    /// assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
433    ///
434    /// let parents = graph.bfs(101);
435    /// assert_eq!(graph.search_path(101, &parents), None);
436    /// ```
437
438    pub fn search_path(&self, mut target: Indent, parents: &BTreeMap<Indent, VertexProperties<Indent>>) -> Option<Vec<Indent>> {
439        if !parents.contains_key(&target) {
440            return None;
441        }
442        let mut path = vec![target.clone()];
443        while let Some(next) = parents.get(&target) {
444            if next.parent.is_none() {
445                break;
446            }
447            path.push(next.parent.clone().unwrap());
448            target = next.parent.clone().unwrap();
449        }
450        path.reverse();
451        Some(path)
452    }
453}
454
455#[derive(Clone, Copy, Default)]
456pub struct VertexNumProperties {
457    parent: Option<usize>,
458    #[allow(dead_code)]
459    color: Color,
460    #[allow(dead_code)]
461    time_in: Option<usize>,
462    #[allow(dead_code)]
463    time_out: Option<usize>
464}
465
466#[derive(Clone, Copy)]
467struct EdgeNum  {
468    to: usize,
469    weight: f32,
470}
471
472pub struct GraphNum  {
473    adj: Vec::<Option<Vec<EdgeNum>>>,
474}
475
476impl GraphNum {
477    pub fn new(n: usize) -> Self {
478        GraphNum {
479            adj: vec![None; n + 1]
480        }
481    }
482
483    /// Adds a new vertex to the graph
484    pub fn add_vertex(&mut self, vertex: usize) {
485        self.adj[vertex] = Some(Vec::new());
486    }
487    /// Adds a new oriented edge to the graph
488    pub fn add_oriented_edge(&mut self, from: usize, to: usize, weight: f32) {
489        self.adj[from].as_mut().unwrap().push(EdgeNum{ to, weight });
490    }
491
492    /// BFS (Breadth-First Search) algorithm.
493    /// Returns an ancestor vector along the graph traversal path
494    ///```
495    /// use librualg::graph::GraphNum;
496    ///
497    /// let mut graph = GraphNum::new(20);
498    /// graph.add_vertex(1);
499    /// graph.add_vertex(2);
500    /// graph.add_vertex(3);
501    /// graph.add_vertex(4);
502    /// graph.add_vertex(5);
503    /// graph.add_vertex(8);
504    /// graph.add_vertex(17);
505    /// graph.add_oriented_edge(1, 2, 0.0);
506    /// graph.add_oriented_edge(2, 3, 0.0);
507    /// graph.add_oriented_edge(2, 4, 0.0);
508    /// graph.add_oriented_edge(2, 5, 0.0);
509    /// graph.add_oriented_edge(4, 8, 0.0);
510    /// graph.add_oriented_edge(8, 17, 0.0);
511    /// let parents = graph.bfs(1);
512    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
513    /// assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
514    ///
515    /// graph.add_oriented_edge(17, 1, 0.0);
516    /// let parents = graph.bfs(1);
517    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
518    ///  assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
519    ///
520    /// let parents = graph.bfs(11);
521    /// assert_eq!(graph.search_path(11, &parents), None);
522    ///```
523
524    pub fn bfs(&self, from: usize) -> Vec<VertexNumProperties> {
525        let mut queue = VecDeque::new();
526        let mut parents = vec![VertexNumProperties::default(); self.adj.len()];
527        let mut visited = vec![false; self.adj.len()];
528
529        if self.adj[from].is_some() {
530            queue.push_back(from);
531            visited[from] = true;
532            parents[from] = VertexNumProperties {parent: None, time_in: None, time_out: None, color: Color::White};
533            while let Some(vertex) = queue.pop_front(){
534                if self.adj[vertex].is_some() {
535                    for edge in self.adj[vertex].as_ref().unwrap().iter() {
536                        if !visited[edge.to] {
537                            parents[edge.to] = VertexNumProperties {parent: Some(vertex.clone()), time_in: None, time_out: None, color: Color::White};
538                            queue.push_back(edge.to);
539                            visited[edge.to] = true;
540                        }
541                    }
542                }
543            }
544        }
545        parents
546    }
547
548    fn _dfs(&self, from: usize, timer: &mut usize,  parents: &mut Vec<VertexNumProperties>, colors: &mut Vec<Color>) {
549        *timer += 1;
550        colors[from] = Color::Grey;
551        if self.adj[from].is_some() {
552            for edge in self.adj[from].as_ref().unwrap().iter() {
553                if colors[edge.to] == Color::White {
554                    parents[edge.to] = VertexNumProperties{parent: Some(from.clone()), time_in: None, time_out: None, color: Color::White};
555                    self._dfs(edge.to, timer, parents, colors);
556                }
557            }
558        }
559        colors[from] = Color::Black;
560        *timer += 1;
561        parents[from].time_out = Some(*timer);
562        parents[from].color = Color::Black;
563    }
564
565    /// DFS (Depth-First Search) algorithm.
566    /// Returns an ancestor vector along the graph traversal path
567    ///```
568    /// use librualg::graph::GraphNum;
569    ///
570    /// let mut graph = GraphNum::new(10);
571    ///
572    /// graph.add_vertex(1);
573    /// graph.add_vertex(2);
574    /// graph.add_vertex(3);
575    /// graph.add_vertex(5);
576    /// graph.add_oriented_edge(1, 2, 0.0);
577    /// graph.add_oriented_edge(2, 3, 0.0);
578    /// graph.add_oriented_edge(3, 5, 0.0);
579    ///
580    /// let res = graph.dfs(1);
581    /// assert_eq!(graph.search_path(5, &res).unwrap(), vec![1, 2, 3, 5]);
582    /// ```
583
584    pub fn dfs(&self, from: usize) -> Vec<VertexNumProperties> {
585        let mut parents = vec![VertexNumProperties::default(); self.adj.len()];
586        let mut colors = vec![Color::White; self.adj.len()];
587        let mut timer = 0;
588        parents[from] = VertexNumProperties{parent: None, time_in: Some(timer), time_out: None, color: Color::White};
589        self._dfs(from, &mut timer, &mut parents, &mut colors);
590        parents
591    }
592
593    /// Dijkstra algorithm.
594    /// Returns an ancestor vector along the graph traversal path and distances to the other vertexs
595    ///```
596    /// use librualg::graph::GraphNum;
597    ///
598    /// let mut graph = GraphNum::new(10);
599    ///
600    /// graph.add_vertex(1);
601    /// graph.add_vertex(2);
602    /// graph.add_vertex(3);
603    /// graph.add_vertex(5);
604    /// graph.add_vertex(7);
605    ///
606    /// graph.add_oriented_edge(1, 2, 2.0);
607    /// graph.add_oriented_edge(2, 3, 5.0);
608    /// graph.add_oriented_edge(3, 5, 7.0);
609    /// graph.add_oriented_edge(1, 5, 19.0);
610    ///
611    /// let (parents, distances) = graph.dijkstra(1);
612    /// assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 3, 5]);
613    /// assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
614    /// assert_eq!(distances[5].unwrap(), 14.0);
615    /// assert_eq!(distances[7], None);
616    /// ```
617    pub fn dijkstra(&self, from: usize) -> (Vec<VertexNumProperties>, Vec<Option<f32>>) {
618        let mut parents = vec![VertexNumProperties::default(); self.adj.len()];
619        let mut visited = vec![false; self.adj.len()];
620        let mut distances = vec![None; self.adj.len()];
621
622        struct D {
623            node: usize,
624            dist: f32,
625        }
626        impl std::cmp::PartialEq for D {
627            fn eq(&self, other: &D) -> bool {
628                self.dist == other.dist
629            }
630        }
631
632        impl Eq for D {}
633
634        impl std::cmp::Ord for D {
635            fn cmp(&self, other: &Self) -> Ordering {
636                other.dist.partial_cmp(&self.dist).unwrap()
637            }
638        }
639
640        impl std::cmp::PartialOrd for D {
641            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
642                Some(other.dist.partial_cmp(&self.dist).unwrap())
643            }
644        }
645
646        let mut heap = BinaryHeap::<D>::new();
647        distances[from] = Some(0.0);
648        heap.push(D{ node: from, dist: 0.0});
649        while !heap.is_empty() {
650            let d = heap.pop().unwrap();
651            visited[d.node] = true;
652            if self.adj[d.node].as_ref().is_some() {
653                for edge in self.adj[d.node].as_ref().unwrap() {
654                    if !visited[edge.to] && edge.weight + d.dist < distances[edge.to].unwrap_or(f32::MAX) {
655                        parents[edge.to] = VertexNumProperties{parent: Some(d.node.clone()), time_in: None, time_out: None, color: Color::White};
656                        distances[edge.to] = Some(edge.weight + d.dist);
657                        heap.push(D{node: edge.to.clone(), dist: distances[edge.to].unwrap()});
658                    }
659                }
660            }
661        }
662        (parents, distances)
663    }
664
665    /// Get connected components
666    ///```
667    /// use librualg::graph::GraphNum;
668    ///
669    /// let mut graph = GraphNum::new(20);
670    /// graph.add_vertex(1);
671    /// graph.add_vertex(2);
672    /// graph.add_vertex(3);
673    /// graph.add_vertex(4);
674    /// graph.add_vertex(5);
675    /// graph.add_vertex(6);
676    /// graph.add_vertex(7);
677    /// graph.add_vertex(8);
678    /// graph.add_vertex(9);
679    /// graph.add_vertex(10);
680    /// graph.add_vertex(11);
681    /// graph.add_oriented_edge(1, 2, 0.0);
682    /// graph.add_oriented_edge(2, 3, 0.0);
683    /// graph.add_oriented_edge(3, 4, 0.0);
684    ///
685    /// graph.add_oriented_edge(5, 6, 0.0);
686    /// graph.add_oriented_edge(6, 7, 0.0);
687    ///
688    /// graph.add_oriented_edge(8, 9, 0.0);
689    /// graph.add_oriented_edge(9, 10, 0.0);
690    /// graph.add_oriented_edge(10, 11, 0.0);
691    ///
692    /// let components = graph.connected_components();
693    /// assert_eq!(components[0], [1, 2, 3, 4]);
694    /// assert_eq!(components[1], [5, 6, 7]);
695    /// assert_eq!(components[2], [8, 9, 10, 11]);
696    /// ```
697    pub fn connected_components(&self) -> Vec<Vec<usize>> {
698        let mut components = vec![];
699        let mut visited = vec![false; self.adj.len()];
700        for (vertex, edges) in self.adj.iter().enumerate() {
701            if let Some(_) = edges {
702                if !visited[vertex] {
703                    let mut queue = VecDeque::new();
704                    let mut vec = vec![];
705                    visited[vertex] = true;
706                    queue.push_back(vertex);
707                    while let Some(vertex) = queue.pop_front(){
708                        vec.push(vertex);
709                        if self.adj[vertex].is_some() {
710                            for edge in self.adj[vertex].as_ref().unwrap() {
711                                if !visited[edge.to] {
712                                    queue.push_back(edge.to);
713                                    visited[edge.to] = true;
714                                }
715                            }
716                        }
717                    }
718                    components.push(vec)
719                }
720            }
721        }
722        components
723    }
724
725    pub fn strongly_connected_components(&self) -> Vec<Vec<usize>> {
726        let mut components = vec![];
727        let mut graph_transp = GraphNum::new(self.adj.len() - 1);
728        for (vertex, edges) in self.adj.iter().enumerate() {
729            if let Some(_) = edges {
730                graph_transp.add_vertex(vertex);
731            }
732        }
733        for (vertex, edges) in self.adj.iter().enumerate() {
734            if let Some(edges) = edges {
735                for edge in edges {
736                    graph_transp.add_oriented_edge(edge.to, vertex, edge.weight);
737                }
738            }
739        }
740        let mut visited = vec![false; self.adj.len()];
741        let mut orders = Vec::with_capacity(self.adj.len());
742        for (vertex, edges) in self.adj.iter().enumerate() {
743            if let Some(_) = edges {
744                if !visited[vertex] {
745                    for (vertex, property) in self.dfs(vertex).iter().enumerate(){
746                        if self.adj[vertex].is_some() {
747                            if !visited[vertex] && property.color == Color::Black {
748                                visited[vertex] = true;
749                                orders.push(vertex);
750                            }
751                        }
752                    }
753                }
754            }
755        }
756        let mut visited = vec![false; self.adj.len()];
757        for vertex in orders {
758            if !visited[vertex] {
759                let mut vec = vec![];
760                for (vertex, property) in graph_transp.dfs(vertex).iter().enumerate() {
761                    if graph_transp.adj[vertex].is_some() && property.color == Color::Black {
762                        if !visited[vertex] {
763                            visited[vertex] = true;
764                            vec.push(vertex);
765                        }
766                    }
767                }
768                components.push(vec);
769            }
770        }
771        components
772    }
773
774    pub fn topological_sort(&self) -> Vec<usize> {
775        let mut visited = vec![false; self.adj.len()];
776        let mut topology_vec = Vec::with_capacity(self.adj.len());
777        for (vertex, edges) in self.adj.iter().enumerate() {
778            if let Some(_) = edges {
779                if !visited[vertex] {
780                    for (vertex, property) in self.dfs(vertex).iter().enumerate() {
781                        if !visited[vertex] && property.color == Color::Black {
782                            visited[vertex] = true;
783                            topology_vec.push(vertex);
784                        }
785                    }
786                }
787            }
788        }
789        topology_vec
790    }
791
792    /// Kruskal's algorithm
793    /// ```
794    /// use librualg::graph::GraphNum;
795    ///
796    /// let mut graph = GraphNum::new(20);
797    ///
798    /// graph.add_vertex(1);
799    /// graph.add_vertex(2);
800    /// graph.add_vertex(3);
801    /// graph.add_vertex(4);
802    /// graph.add_vertex(5);
803    /// graph.add_vertex(6);
804    /// graph.add_vertex(7);
805    ///
806    /// graph.add_oriented_edge(1, 2, 7.0);
807    /// graph.add_oriented_edge(2, 1, 7.0);
808    /// graph.add_oriented_edge(1, 4, 5.0);
809    /// graph.add_oriented_edge(4, 1, 5.0);
810    /// graph.add_oriented_edge(2, 3, 8.0);
811    /// graph.add_oriented_edge(3, 2, 8.0);
812    /// graph.add_oriented_edge(2, 5, 7.0);
813    /// graph.add_oriented_edge(5, 2, 7.0);
814    /// graph.add_oriented_edge(2, 4, 9.0);
815    /// graph.add_oriented_edge(4, 2, 9.0);
816    /// graph.add_oriented_edge(3, 5, 5.0);
817    /// graph.add_oriented_edge(5, 3, 5.0);
818    /// graph.add_oriented_edge(5, 7, 9.0);
819    /// graph.add_oriented_edge(7, 5, 9.0);
820    /// graph.add_oriented_edge(5, 6, 8.0);
821    /// graph.add_oriented_edge(6, 5, 8.0);
822    /// graph.add_oriented_edge(5, 4, 15.0);
823    /// graph.add_oriented_edge(4, 5, 15.0);
824    /// graph.add_oriented_edge(6, 7, 11.0);
825    /// graph.add_oriented_edge(7, 6, 11.0);
826    /// graph.add_oriented_edge(6, 4, 6.0);
827    /// graph.add_oriented_edge(4, 6, 6.0);
828    /// let tree = graph.kruskal();
829    /// assert_eq!(vec![1, 2, 5, 7], tree.search_path(7, &tree.bfs(1)).unwrap());
830    /// assert_eq!(vec![1, 2, 5, 3], tree.search_path(3, &tree.bfs(1)).unwrap());
831    /// ```
832
833    pub fn kruskal(&self) -> GraphNum {
834        struct D {
835            from: usize,
836            to: usize,
837            dist: f32,
838        }
839
840        impl std::cmp::PartialEq for D {
841            fn eq(&self, other: &D) -> bool {
842                self.dist == other.dist
843            }
844        }
845
846        impl Eq for D {}
847
848        impl std::cmp::Ord for D {
849            fn cmp(&self, other: &Self) -> Ordering {
850                other.dist.partial_cmp(&self.dist).unwrap()
851            }
852        }
853
854        impl std::cmp::PartialOrd for D {
855            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
856                Some(other.dist.partial_cmp(&self.dist).unwrap())
857            }
858        }
859
860        let mut graph: GraphNum = GraphNum::new(self.adj.len() + 1);
861        let mut heap = BinaryHeap::new();
862        let mut dsu = DSUNum::new(graph.adj.len());
863        for (from, edges) in self.adj.iter().enumerate() {
864            if let Some(edges) = edges {
865                graph.add_vertex(from);
866                dsu.make_set(from);
867                for edge in edges {
868                    heap.push(D{
869                        from,
870                        to: edge.to,
871                        dist: edge.weight
872                    });
873                }
874            }
875        }
876
877        while let Some (value) = heap.pop() {
878            if dsu.find_set(value.from) != dsu.find_set(value.to) {
879                dsu.union_sets(value.from, value.to);
880                graph.add_oriented_edge(value.from, value.to, value.dist);
881                graph.add_oriented_edge(value.to, value.from, value.dist);
882            }
883        }
884        graph
885    }
886
887    pub fn search_path(&self, mut target: usize, parents: &[VertexNumProperties]) -> Option<Vec<usize>> {
888        if parents[target].parent.is_none() {
889            return None;
890        }
891        let mut path = vec![target];
892        while let Some(next) = parents[target].parent{
893            path.push(next);
894            target = next;
895        }
896        path.reverse();
897        Some(path)
898    }
899}
900
901#[test]
902fn test_bfs() {
903    let mut graph = Graph::<usize>::new();
904    graph.add_oriented_edge(1, 2, 0.0);
905    graph.add_oriented_edge(2, 3, 0.0);
906    graph.add_oriented_edge(2, 4, 0.0);
907    graph.add_oriented_edge(2, 5, 0.0);
908    graph.add_oriented_edge(4, 8, 0.0);
909    graph.add_oriented_edge(8, 17, 0.0);
910    let parents = graph.bfs(1);
911    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
912    assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
913
914    graph.add_oriented_edge(17, 1, 0.0);
915    let parents = graph.bfs(1);
916    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
917    assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
918
919    let parents = graph.bfs(101);
920    assert_eq!(graph.search_path(101, &parents), None);
921}
922
923#[test]
924fn test_bfs_with_string() {
925    let mut graph = Graph::<String>::new();
926    graph.add_oriented_edge("1".to_string(), "2".to_string(), 0.0);
927    graph.add_oriented_edge("2".to_string(), "3".to_string(), 0.0);
928    graph.add_oriented_edge("2".to_string(), "4".to_string(), 0.0);
929    graph.add_oriented_edge("2".to_string(), "5".to_string(), 0.0);
930    graph.add_oriented_edge("4".to_string(), "8".to_string(), 0.0);
931    graph.add_oriented_edge("8".to_string(), "17".to_string(), 0.0);
932    let parents = graph.bfs("1".to_string());
933    assert_eq!(graph.search_path("5".to_string(), &parents).unwrap(), vec!["1".to_string(), "2".to_string(), "5".to_string()]);
934}
935
936#[test]
937fn test_dfs() {
938    let mut graph = Graph::new();
939    graph.add_oriented_edge(1, 2, 0.0);
940    graph.add_oriented_edge(2, 3, 0.0);
941    graph.add_oriented_edge(3, 5, 0.0);
942
943    let res = graph.dfs(1);
944    assert_eq!(graph.search_path(5, &res).unwrap(), vec![1, 2, 3, 5]);
945}
946
947#[test]
948fn test_dijkstra() {
949    let mut graph = Graph::new();
950    graph.add_oriented_edge(1, 2, 2.0);
951    graph.add_oriented_edge(2, 3, 5.0);
952    graph.add_oriented_edge(3, 5, 7.0);
953    graph.add_oriented_edge(1, 5, 19.0);
954
955    let (parents, distances) = graph.dijkstra(1);
956    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 3, 5]);
957    assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
958    assert_eq!(*distances.get(&5).unwrap(), 14.0);
959
960
961    let mut graph = Graph::new();
962    graph.add_oriented_edge(1, 2, 2.0);
963    graph.add_oriented_edge(2, 3, 5.0);
964    graph.add_oriented_edge(3, 1, 7.0);
965
966    let (parents, distances) = graph.dijkstra(1);
967    assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
968    assert_eq!(*distances.get(&3).unwrap(), 7.0);
969}
970
971#[test]
972fn test_connected_components() {
973    let mut graph = Graph::new();
974    graph.add_oriented_edge(1, 2, 0.0);
975    graph.add_oriented_edge(2, 3, 0.0);
976    graph.add_oriented_edge(3, 4, 0.0);
977
978    graph.add_oriented_edge(5, 6, 0.0);
979    graph.add_oriented_edge(6, 7, 0.0);
980
981    graph.add_oriented_edge(8, 9, 0.0);
982    graph.add_oriented_edge(9, 10, 0.0);
983    graph.add_oriented_edge(10, 11, 0.0);
984
985    let components = graph.connected_components();
986    assert_eq!(components[0], [1, 2, 3, 4]);
987    assert_eq!(components[1], [5, 6, 7]);
988    assert_eq!(components[2], [8, 9, 10, 11]);
989    assert_eq!(components.len(), 3);
990}
991
992#[test]
993fn test_strongly_connected_components() {
994    let mut graph = Graph::new();
995    graph.add_oriented_edge("a", "b", 0.0);
996    graph.add_oriented_edge("b", "f", 0.0);
997    graph.add_oriented_edge("e", "a", 0.0);
998    graph.add_oriented_edge("b", "e", 0.0);
999    graph.add_oriented_edge("e", "f", 0.0);
1000
1001    graph.add_oriented_edge("b", "c", 0.0);
1002    graph.add_oriented_edge("f", "g", 0.0);
1003    graph.add_oriented_edge("g", "f", 0.0);
1004    graph.add_oriented_edge("c", "g", 0.0);
1005
1006    graph.add_oriented_edge("c", "d", 0.0);
1007    graph.add_oriented_edge("d", "c", 0.0);
1008    graph.add_oriented_edge("d", "h", 0.0);
1009    graph.add_oriented_edge("h", "d", 0.0);
1010    graph.add_oriented_edge("h", "g", 0.0);
1011
1012    graph.add_oriented_edge("k", "m", 0.0);
1013    graph.add_oriented_edge("m", "k", 0.0);
1014
1015    let components = graph.strongly_connected_components();
1016    assert_eq!(components[0], ["a", "b", "e"]);
1017    assert_eq!(components[1], ["c", "d", "h"]);
1018    assert_eq!(components[2], ["f", "g"]);
1019    assert_eq!(components[3], ["k", "m"]);
1020    assert_eq!(components.len(), 4);
1021}
1022
1023#[test]
1024fn topology_sort() {
1025    let mut graph = Graph::new();
1026    graph.add_oriented_edge("a", "b", 0.0);
1027    graph.add_oriented_edge("a", "c", 0.0);
1028    graph.add_oriented_edge("a", "e", 0.0);
1029    graph.add_oriented_edge("a", "d", 0.0);
1030    graph.add_oriented_edge("b", "d", 0.0);
1031    graph.add_oriented_edge("c", "d", 0.0);
1032    graph.add_oriented_edge("c", "e", 0.0);
1033
1034    assert_eq!(graph.topological_sort(), vec!["a", "b", "c", "d", "e"]);
1035
1036    graph.add_oriented_edge("x", "y", 0.0);
1037    graph.add_oriented_edge("y", "z", 0.0);
1038
1039    assert_eq!(graph.topological_sort(), vec!["a", "b", "c", "d", "e", "x", "y", "z"]);
1040}
1041
1042#[test]
1043fn test_kruskal() {
1044    let mut graph = Graph::new();
1045    graph.add_oriented_edge('A', 'B', 7.0);
1046    graph.add_oriented_edge('B', 'A', 7.0);
1047    graph.add_oriented_edge('A', 'D', 5.0);
1048    graph.add_oriented_edge('D', 'A', 5.0);
1049    graph.add_oriented_edge('B', 'C', 8.0);
1050    graph.add_oriented_edge('C', 'B', 8.0);
1051    graph.add_oriented_edge('B', 'E', 7.0);
1052    graph.add_oriented_edge('E', 'B', 7.0);
1053    graph.add_oriented_edge('B', 'D', 9.0);
1054    graph.add_oriented_edge('D', 'B', 9.0);
1055    graph.add_oriented_edge('C', 'E', 5.0);
1056    graph.add_oriented_edge('E', 'C', 5.0);
1057    graph.add_oriented_edge('E', 'G', 9.0);
1058    graph.add_oriented_edge('G', 'E', 9.0);
1059    graph.add_oriented_edge('E', 'F', 8.0);
1060    graph.add_oriented_edge('F', 'E', 8.0);
1061    graph.add_oriented_edge('E', 'D', 15.0);
1062    graph.add_oriented_edge('D', 'E', 15.0);
1063    graph.add_oriented_edge('F', 'G', 11.0);
1064    graph.add_oriented_edge('G', 'F', 11.0);
1065    graph.add_oriented_edge('F', 'D', 6.0);
1066    graph.add_oriented_edge('D', 'F', 6.0);
1067    let tree = graph.kruskal();
1068    assert_eq!(vec!['A', 'B', 'E', 'G'], tree.search_path('G', &tree.bfs('A')).unwrap());
1069    assert_eq!(vec!['A', 'B', 'E', 'C'], tree.search_path('C', &tree.bfs('A')).unwrap());
1070}
1071
1072#[test]
1073fn test_bfs_num() {
1074    let mut graph = GraphNum::new(20);
1075    graph.add_vertex(1);
1076    graph.add_vertex(2);
1077    graph.add_vertex(3);
1078    graph.add_vertex(4);
1079    graph.add_vertex(5);
1080    graph.add_vertex(8);
1081    graph.add_vertex(17);
1082    graph.add_oriented_edge(1, 2, 0.0);
1083    graph.add_oriented_edge(2, 3, 0.0);
1084    graph.add_oriented_edge(2, 4, 0.0);
1085    graph.add_oriented_edge(2, 5, 0.0);
1086    graph.add_oriented_edge(4, 8, 0.0);
1087    graph.add_oriented_edge(8, 17, 0.0);
1088    let parents = graph.bfs(1);
1089    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
1090    assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
1091
1092    graph.add_oriented_edge(17, 1, 0.0);
1093    let parents = graph.bfs(1);
1094    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
1095    assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);
1096
1097    let parents = graph.bfs(11);
1098    assert_eq!(graph.search_path(11, &parents), None);
1099}
1100
1101#[test]
1102fn test_dfs_num() {
1103    let mut graph = GraphNum::new(10);
1104    graph.add_vertex(1);
1105    graph.add_vertex(2);
1106    graph.add_vertex(3);
1107    graph.add_vertex(5);
1108    graph.add_oriented_edge(1, 2, 0.0);
1109    graph.add_oriented_edge(2, 3, 0.0);
1110    graph.add_oriented_edge(3, 5, 0.0);
1111
1112    let res = graph.dfs(1);
1113    assert_eq!(graph.search_path(5, &res).unwrap(), vec![1, 2, 3, 5]);
1114}
1115
1116#[test]
1117fn test_dijkstra_num() {
1118    let mut graph = GraphNum::new(10);
1119
1120    graph.add_vertex(1);
1121    graph.add_vertex(2);
1122    graph.add_vertex(3);
1123    graph.add_vertex(5);
1124    graph.add_vertex(7);
1125
1126    graph.add_oriented_edge(1, 2, 2.0);
1127    graph.add_oriented_edge(2, 3, 5.0);
1128    graph.add_oriented_edge(3, 5, 7.0);
1129    graph.add_oriented_edge(1, 5, 19.0);
1130
1131    let (parents, distances) = graph.dijkstra(1);
1132    assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 3, 5]);
1133    assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
1134    assert_eq!(distances[5].unwrap(), 14.0);
1135    assert_eq!(distances[7], None);
1136}
1137
1138#[test]
1139fn test_connected_components_num() {
1140    let mut graph = GraphNum::new(20);
1141    graph.add_vertex(1);
1142    graph.add_vertex(2);
1143    graph.add_vertex(3);
1144    graph.add_vertex(4);
1145    graph.add_vertex(5);
1146    graph.add_vertex(6);
1147    graph.add_vertex(7);
1148    graph.add_vertex(8);
1149    graph.add_vertex(9);
1150    graph.add_vertex(10);
1151    graph.add_vertex(11);
1152    graph.add_oriented_edge(1, 2, 0.0);
1153    graph.add_oriented_edge(2, 3, 0.0);
1154    graph.add_oriented_edge(3, 4, 0.0);
1155
1156    graph.add_oriented_edge(5, 6, 0.0);
1157    graph.add_oriented_edge(6, 7, 0.0);
1158
1159    graph.add_oriented_edge(8, 9, 0.0);
1160    graph.add_oriented_edge(9, 10, 0.0);
1161    graph.add_oriented_edge(10, 11, 0.0);
1162
1163    let components = graph.connected_components();
1164    assert_eq!(components[0], [1, 2, 3, 4]);
1165    assert_eq!(components[1], [5, 6, 7]);
1166    assert_eq!(components[2], [8, 9, 10, 11]);
1167    assert_eq!(components.len(), 3);
1168}
1169
1170#[test]
1171fn test_strongly_connected_components_num() {
1172    let mut graph = GraphNum::new(10);
1173    graph.add_vertex(1);
1174    graph.add_vertex(2);
1175    graph.add_vertex(3);
1176    graph.add_vertex(4);
1177    graph.add_vertex(5);
1178    graph.add_vertex(6);
1179    graph.add_vertex(7);
1180    graph.add_vertex(8);
1181
1182    graph.add_oriented_edge(1, 2, 0.0);
1183    graph.add_oriented_edge(2, 6, 0.0);
1184    graph.add_oriented_edge(5, 1, 0.0);
1185    graph.add_oriented_edge(2, 5, 0.0);
1186    graph.add_oriented_edge(5, 6, 0.0);
1187
1188    graph.add_oriented_edge(2, 3, 0.0);
1189    graph.add_oriented_edge(6, 7, 0.0);
1190    graph.add_oriented_edge(7, 6, 0.0);
1191    graph.add_oriented_edge(3, 7, 0.0);
1192
1193    graph.add_oriented_edge(3, 4, 0.0);
1194    graph.add_oriented_edge(4, 3, 0.0);
1195    graph.add_oriented_edge(4, 8, 0.0);
1196    graph.add_oriented_edge(8, 4, 0.0);
1197    graph.add_oriented_edge(8, 7, 0.0);
1198
1199    let components = graph.strongly_connected_components();
1200    assert_eq!(components[0], [1, 2, 5]);
1201    assert_eq!(components[1], [3, 4, 8]);
1202    assert_eq!(components[2], [6, 7]);
1203}
1204
1205#[test]
1206fn topology_sort_num() {
1207    let mut graph = GraphNum::new(10);
1208
1209    graph.add_vertex(1);
1210    graph.add_vertex(2);
1211    graph.add_vertex(3);
1212    graph.add_vertex(4);
1213    graph.add_vertex(5);
1214
1215    graph.add_oriented_edge(1, 2, 0.0);
1216    graph.add_oriented_edge(1, 3, 0.0);
1217    graph.add_oriented_edge(1, 5, 0.0);
1218    graph.add_oriented_edge(1, 4, 0.0);
1219    graph.add_oriented_edge(2, 4, 0.0);
1220    graph.add_oriented_edge(3, 4, 0.0);
1221    graph.add_oriented_edge(3, 5, 0.0);
1222
1223    assert_eq!(graph.topological_sort(), vec![1, 2, 3, 4, 5]);
1224
1225    graph.add_vertex(6);
1226    graph.add_vertex(7);
1227    graph.add_vertex(8);
1228    graph.add_oriented_edge(6, 7, 0.0);
1229    graph.add_oriented_edge(7, 8, 0.0);
1230
1231    assert_eq!(graph.topological_sort(), vec![1, 2, 3, 4, 5, 6, 7, 8]);
1232}
1233
1234#[test]
1235fn test_kruskal_num() {
1236    let mut graph = GraphNum::new(20);
1237    graph.add_vertex(1);
1238    graph.add_vertex(2);
1239    graph.add_vertex(3);
1240    graph.add_vertex(4);
1241    graph.add_vertex(5);
1242    graph.add_vertex(6);
1243    graph.add_vertex(7);
1244
1245
1246    graph.add_oriented_edge(1, 2, 7.0);
1247    graph.add_oriented_edge(2, 1, 7.0);
1248    graph.add_oriented_edge(1, 4, 5.0);
1249    graph.add_oriented_edge(4, 1, 5.0);
1250    graph.add_oriented_edge(2, 3, 8.0);
1251    graph.add_oriented_edge(3, 2, 8.0);
1252    graph.add_oriented_edge(2, 5, 7.0);
1253    graph.add_oriented_edge(5, 2, 7.0);
1254    graph.add_oriented_edge(2, 4, 9.0);
1255    graph.add_oriented_edge(4, 2, 9.0);
1256    graph.add_oriented_edge(3, 5, 5.0);
1257    graph.add_oriented_edge(5, 3, 5.0);
1258    graph.add_oriented_edge(5, 7, 9.0);
1259    graph.add_oriented_edge(7, 5, 9.0);
1260    graph.add_oriented_edge(5, 6, 8.0);
1261    graph.add_oriented_edge(6, 5, 8.0);
1262    graph.add_oriented_edge(5, 4, 15.0);
1263    graph.add_oriented_edge(4, 5, 15.0);
1264    graph.add_oriented_edge(6, 7, 11.0);
1265    graph.add_oriented_edge(7, 6, 11.0);
1266    graph.add_oriented_edge(6, 4, 6.0);
1267    graph.add_oriented_edge(4, 6, 6.0);
1268    let tree = graph.kruskal();
1269    assert_eq!(vec![1, 2, 5, 7], tree.search_path(7, &tree.bfs(1)).unwrap());
1270    assert_eq!(vec![1, 2, 5, 3], tree.search_path(3, &tree.bfs(1)).unwrap());
1271}
librualg/graph/mod.rs

librualg/graph/
mod.rs
