yagraphc/
graph.rs

1use std::collections::HashMap;
2use std::collections::HashSet;
3use std::collections::VecDeque;
4use std::fmt::Debug;
5use std::hash::Hash;
6
7use self::traits::ArithmeticallyWeightedGraph;
8use self::traits::GraphBuilding;
9use self::traits::NodeNotFound;
10use self::traits::Traversable;
11
12pub mod traits;
13
14/// Undirected graph using adjancency list as a nested HashMap.
15///
16/// Recommended for graphs that have vertices with high degree.
17#[derive(Debug, Clone)]
18pub struct UnGraph<T, W> {
19    nodes: HashSet<T>,
20    edges: HashMap<T, HashMap<T, W>>,
21
22    empty: HashMap<T, W>,
23}
24
25impl<T, W> UnGraph<T, W>
26where
27    T: Clone + Copy + Hash + Eq + PartialEq,
28    W: Clone + Copy,
29{
30    /// Initializes an empty undirected graph.
31    pub fn new() -> Self {
32        Self::default()
33    }
34
35    /// Finds basic cycles of the undirected graph.
36    ///
37    /// Basic cycles correspond to generators of the first homology group of the graph.
38    ///
39    ///
40    /// # Examples
41    ///
42    /// ```rust
43    /// use yagraphc::graph::UnGraph;
44    /// use yagraphc::graph::traits::{Traversable, GraphBuilding};
45    ///
46    /// let mut graph = UnGraph::default();
47    ///
48    /// graph.add_edge(1, 2, ());
49    /// graph.add_edge(2, 3, ());
50    /// graph.add_edge(3, 4, ());
51    /// graph.add_edge(4, 1, ());
52    ///
53    /// let cycles = graph.basic_cycles();
54    /// assert_eq!(cycles.len(), 1);
55    /// assert_eq!(cycles[0].len(), 4);
56    ///
57    /// graph.remove_edge(2, 3);
58    /// let cycles = graph.basic_cycles();
59    /// assert_eq!(cycles.len(), 0);
60    /// ```
61    pub fn basic_cycles(&self) -> Vec<Vec<T>> {
62        let mut remaining_edges = self.all_edges();
63
64        let mut spanning_forest = UnGraph::default();
65        let mut visited = HashSet::new();
66
67        for node in self.nodes() {
68            if visited.contains(&node) {
69                continue;
70            }
71
72            let mut queue = VecDeque::new();
73            queue.push_back((node, node));
74
75            while let Some((previous_node, inner_node)) = queue.pop_front() {
76                if visited.contains(&inner_node) {
77                    continue;
78                }
79
80                remaining_edges.remove(&(inner_node, previous_node));
81                remaining_edges.remove(&(previous_node, inner_node));
82                spanning_forest.add_edge(previous_node, inner_node, 1);
83
84                visited.insert(inner_node);
85
86                for (target, _) in self.edges(&inner_node) {
87                    if visited.contains(&target) {
88                        continue;
89                    }
90
91                    queue.push_back((inner_node, target));
92                }
93            }
94        }
95
96        let mut cycles = Vec::new();
97
98        for edge in remaining_edges {
99            if let Some(path) = spanning_forest.find_path(edge.0, edge.1) {
100                cycles.push(path);
101            }
102        }
103
104        cycles
105    }
106
107    /// Gets all edges of the graph as a set.
108    ///
109    /// If edge (a, b) is returned, then (b, a) will not. The ordering of the nodes is random.
110    ///
111    /// # Examples
112    ///
113    /// ```rust
114    /// use yagraphc::graph::UnGraph;
115    /// use yagraphc::graph::traits::{Traversable, GraphBuilding};
116    ///
117    /// let mut graph = UnGraph::default();
118    ///
119    /// graph.add_edge(1, 2, ());
120    /// graph.add_edge(2, 3, ());
121    ///
122    /// let edges = graph.all_edges();
123    /// assert_eq!(edges.len(), 2);
124    pub fn all_edges(&self) -> HashSet<(T, T)> {
125        let mut edges = HashSet::new();
126
127        for (origin, destinations) in &self.edges {
128            for dest in destinations.keys() {
129                if edges.contains(&(*dest, *origin)) {
130                    continue;
131                }
132                edges.insert((*origin, *dest));
133            }
134        }
135
136        edges
137    }
138}
139
140impl<T, W> GraphBuilding<T, W> for UnGraph<T, W>
141where
142    T: Clone + Copy + Hash + Eq + PartialEq,
143    W: Clone + Copy,
144{
145    fn add_edge(&mut self, from: T, to: T, weight: W) {
146        self.edges.entry(from).or_default().insert(to, weight);
147        self.edges.entry(to).or_default().insert(from, weight);
148
149        self.nodes.insert(from);
150        self.nodes.insert(to);
151    }
152
153    fn add_node(&mut self, node: T) -> bool {
154        self.nodes.insert(node)
155    }
156
157    fn remove_edge(&mut self, from: T, to: T) -> Result<(), NodeNotFound> {
158        self.edges.get_mut(&from).ok_or(NodeNotFound)?.remove(&to);
159        self.edges.get_mut(&to).ok_or(NodeNotFound)?.remove(&from);
160
161        Ok(())
162    }
163
164    fn remove_node(&mut self, node: T) -> Result<(), NodeNotFound> {
165        if !self.nodes.remove(&node) {
166            return Err(NodeNotFound);
167        }
168
169        self.edges.remove_entry(&node);
170
171        for edges in self.edges.values_mut() {
172            edges.remove(&node);
173        }
174
175        Ok(())
176    }
177
178    fn has_edge(&self, from: T, to: T) -> bool {
179        self.edges
180            .get(&from)
181            .map_or(false, |edges| edges.contains_key(&to))
182    }
183}
184
185impl<T, W> Traversable<T, W> for UnGraph<T, W>
186where
187    T: Clone + Copy + Hash + Eq + PartialEq,
188    W: Clone + Copy,
189{
190    fn nodes(&self) -> traits::NodeIter<'_, T> {
191        traits::NodeIter {
192            nodes_iter: self.nodes.iter(),
193        }
194    }
195
196    fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound> {
197        self.edges
198            .get(&from)
199            .ok_or(NodeNotFound)?
200            .get(&to)
201            .ok_or(NodeNotFound)
202            .copied()
203    }
204
205    fn edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
206        let edges = self.edges.get(n);
207
208        if let Some(edges) = edges {
209            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
210                edge_iter: edges.iter(),
211            })
212        } else {
213            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
214                edge_iter: self.empty.iter(),
215            })
216        }
217    }
218
219    fn in_edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
220        self.edges(n)
221    }
222
223    /// Computes the connected components of an undirected graph.
224    ///
225    /// Relies simply on BFS to compute the components as opposed to Kosaraju's algorithm.
226    ///
227    /// # Examples
228    ///
229    /// ```rust
230    /// use yagraphc::graph::UnGraph;
231    /// use yagraphc::graph::traits::{GraphBuilding, Traversable};
232    ///
233    /// let mut graph = UnGraph::default();
234    ///
235    /// graph.add_edge(1, 2, ());
236    /// graph.add_edge(2, 3, ());
237    /// graph.add_edge(3, 4, ());
238    ///
239    /// let components = graph.connected_components();
240    /// assert_eq!(components.len(), 1);
241    ///
242    /// graph.add_edge(5, 6, ());
243    ///
244    /// let components = graph.connected_components();
245    /// assert_eq!(components.len(), 2);
246    fn connected_components(&self) -> Vec<Vec<T>>
247    where
248        Self: Sized,
249    {
250        let mut visited = HashSet::new();
251        let mut components = vec![];
252
253        for node in self.nodes() {
254            if visited.contains(&node) {
255                continue;
256            }
257
258            let mut component = vec![node];
259
260            for (inner_node, _) in self.bfs(node) {
261                component.push(inner_node);
262                visited.insert(inner_node);
263            }
264
265            components.push(component);
266        }
267
268        components
269    }
270}
271
272impl<T, W> ArithmeticallyWeightedGraph<T, W> for UnGraph<T, W>
273where
274    T: Clone + Copy + Eq + Hash + PartialEq,
275    W: Clone
276        + Copy
277        + std::ops::Add<Output = W>
278        + std::ops::Sub<Output = W>
279        + PartialOrd
280        + Ord
281        + Default,
282{
283}
284
285impl<T, W> Default for UnGraph<T, W> {
286    fn default() -> Self {
287        UnGraph {
288            nodes: HashSet::new(),
289            edges: HashMap::new(),
290            empty: HashMap::new(),
291        }
292    }
293}
294
295/// Undirected graph using adjancency list as a Vec for each node.
296///
297/// Recommended for graphs that have vertices with low degree.
298#[derive(Debug, Clone)]
299pub struct UnGraphVecEdges<T, W> {
300    nodes: HashSet<T>,
301    edges: HashMap<T, Vec<(T, W)>>,
302
303    empty: Vec<(T, W)>,
304}
305
306impl<T, W> UnGraphVecEdges<T, W>
307where
308    T: Clone + Copy + Hash + Eq + PartialEq,
309    W: Clone + Copy,
310{
311    pub fn new() -> Self {
312        Self::default()
313    }
314
315    /// Finds basic cycles of the undirected graph.
316    ///
317    /// Basic cycles correspond to generators of the first homology group of the graph.
318    ///
319    ///
320    /// # Examples
321    ///
322    /// ```rust
323    /// use yagraphc::graph::UnGraph;
324    /// use yagraphc::graph::traits::{GraphBuilding, Traversable};
325    ///
326    /// let mut graph = UnGraph::default();
327    ///
328    /// graph.add_edge(1, 2, ());
329    /// graph.add_edge(2, 3, ());
330    /// graph.add_edge(3, 4, ());
331    /// graph.add_edge(4, 1, ());
332    ///
333    /// let cycles = graph.basic_cycles();
334    /// assert_eq!(cycles.len(), 1);
335    /// assert_eq!(cycles[0].len(), 4);
336    ///
337    /// graph.remove_edge(2, 3);
338    /// let cycles = graph.basic_cycles();
339    /// assert_eq!(cycles.len(), 0);
340    /// ```
341    pub fn basic_cycles(&self) -> Vec<Vec<T>> {
342        let mut remaining_edges = self.all_edges();
343
344        let mut spanning_forest = UnGraph::default();
345        let mut visited = HashSet::new();
346
347        for node in self.nodes() {
348            if visited.contains(&node) {
349                continue;
350            }
351
352            let mut queue = VecDeque::new();
353            queue.push_back((node, node));
354
355            while let Some((previous_node, inner_node)) = queue.pop_front() {
356                if visited.contains(&inner_node) {
357                    continue;
358                }
359
360                remaining_edges.remove(&(inner_node, previous_node));
361                remaining_edges.remove(&(previous_node, inner_node));
362                spanning_forest.add_edge(previous_node, inner_node, 1);
363
364                visited.insert(inner_node);
365
366                for (target, _) in self.edges(&inner_node) {
367                    if visited.contains(&target) {
368                        continue;
369                    }
370
371                    queue.push_back((inner_node, target));
372                }
373            }
374        }
375
376        let mut cycles = Vec::new();
377
378        for edge in remaining_edges {
379            if let Some(path) = spanning_forest.find_path(edge.0, edge.1) {
380                cycles.push(path);
381            }
382        }
383
384        cycles
385    }
386
387    /// Gets all edges of the graph as a set.
388    ///
389    /// If edge (a, b) is returned, then (b, a) will not. The ordering of the nodes is random.
390    ///
391    /// # Examples
392    ///
393    /// ```rust
394    /// use yagraphc::graph::UnGraphVecEdges;
395    /// use yagraphc::graph::traits::{GraphBuilding, Traversable};
396    ///
397    /// let mut graph = UnGraphVecEdges::default();
398    ///
399    /// graph.add_edge(1, 2, ());
400    /// graph.add_edge(2, 3, ());
401    ///
402    /// let edges = graph.all_edges();
403    /// assert_eq!(edges.len(), 2);
404    pub fn all_edges(&self) -> HashSet<(T, T)> {
405        let mut edges = HashSet::new();
406
407        for (origin, destinations) in &self.edges {
408            for (dest, _) in destinations {
409                if edges.contains(&(*dest, *origin)) {
410                    continue;
411                }
412                edges.insert((*origin, *dest));
413            }
414        }
415
416        edges
417    }
418}
419
420impl<T, W> GraphBuilding<T, W> for UnGraphVecEdges<T, W>
421where
422    T: Clone + Copy + Hash + Eq + PartialEq,
423    W: Clone + Copy,
424{
425    fn add_edge(&mut self, from: T, to: T, weight: W) {
426        self.edges.entry(from).or_default().push((to, weight));
427        self.edges.entry(to).or_default().push((from, weight));
428
429        self.nodes.insert(from);
430        self.nodes.insert(to);
431    }
432
433    fn add_node(&mut self, node: T) -> bool {
434        self.nodes.insert(node)
435    }
436
437    fn remove_edge(&mut self, from: T, to: T) -> Result<(), NodeNotFound> {
438        let edges_beginning_at_from = self.edges.get_mut(&from).ok_or(NodeNotFound)?;
439
440        edges_beginning_at_from.retain(|(target, _)| *target != to);
441
442        let edges_beginning_at_to = self.edges.get_mut(&to).ok_or(NodeNotFound)?;
443
444        edges_beginning_at_to.retain(|(target, _)| *target != from);
445
446        Ok(())
447    }
448
449    fn remove_node(&mut self, node: T) -> Result<(), NodeNotFound> {
450        if !self.nodes.remove(&node) {
451            return Err(NodeNotFound);
452        }
453
454        self.edges.remove_entry(&node);
455
456        for edges in self.edges.values_mut() {
457            edges.retain(|(target, _)| *target != node);
458        }
459
460        Ok(())
461    }
462
463    fn has_edge(&self, from: T, to: T) -> bool {
464        self.edges
465            .get(&from)
466            .map_or(false, |edges| edges.iter().any(|(target, _)| *target == to))
467    }
468}
469
470impl<T, W> Traversable<T, W> for UnGraphVecEdges<T, W>
471where
472    T: Clone + Copy + Hash + Eq + PartialEq,
473    W: Clone + Copy,
474{
475    fn nodes(&self) -> traits::NodeIter<'_, T> {
476        traits::NodeIter {
477            nodes_iter: self.nodes.iter(),
478        }
479    }
480
481    fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound> {
482        self.edges
483            .get(&from)
484            .ok_or(NodeNotFound)?
485            .iter()
486            .find_map(|(x, y)| (*x == to).then_some(*y))
487            .ok_or(NodeNotFound)
488    }
489
490    fn edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
491        let edges = self.edges.get(n);
492
493        if let Some(edges) = edges {
494            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
495                edge_iter: edges.iter(),
496            })
497        } else {
498            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
499                edge_iter: self.empty.iter(),
500            })
501        }
502    }
503
504    fn in_edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
505        self.edges(n)
506    }
507
508    /// Computes the connected components of an undirected graph.
509    ///
510    /// Relies simply on BFS to compute the components as opposed to Kosaraju's algorithm.
511    ///
512    /// # Examples
513    ///
514    /// ```rust
515    /// use yagraphc::graph::UnGraphVecEdges;
516    /// use yagraphc::graph::traits::{GraphBuilding, Traversable};
517    ///
518    /// let mut graph = UnGraphVecEdges::default();
519    ///
520    /// graph.add_edge(1, 2, ());
521    /// graph.add_edge(2, 3, ());
522    /// graph.add_edge(3, 4, ());
523    ///
524    /// let components = graph.connected_components();
525    /// assert_eq!(components.len(), 1);
526    ///
527    /// graph.add_edge(5, 6, ());
528    ///
529    /// let components = graph.connected_components();
530    /// assert_eq!(components.len(), 2);
531    fn connected_components(&self) -> Vec<Vec<T>>
532    where
533        Self: Sized,
534    {
535        let mut visited = HashSet::new();
536        let mut components = vec![];
537
538        for node in self.nodes() {
539            if visited.contains(&node) {
540                continue;
541            }
542
543            let mut component = vec![node];
544
545            for (inner_node, _) in self.bfs(node) {
546                component.push(inner_node);
547                visited.insert(inner_node);
548            }
549
550            components.push(component);
551        }
552
553        components
554    }
555}
556
557impl<T, W> ArithmeticallyWeightedGraph<T, W> for UnGraphVecEdges<T, W>
558where
559    T: Clone + Copy + Eq + Hash + PartialEq,
560    W: Clone
561        + Copy
562        + std::ops::Add<Output = W>
563        + std::ops::Sub<Output = W>
564        + PartialOrd
565        + Ord
566        + Default,
567{
568}
569
570impl<T, W> Default for UnGraphVecEdges<T, W> {
571    fn default() -> Self {
572        UnGraphVecEdges {
573            nodes: HashSet::new(),
574            edges: HashMap::new(),
575            empty: Vec::new(),
576        }
577    }
578}
579
580/// Directed graph using adjancency list as a nested HashMap.
581///
582/// Recommended for graphs that have vertices with high degree.
583#[derive(Debug, Clone)]
584pub struct DiGraph<T, W> {
585    nodes: HashSet<T>,
586    edges: HashMap<T, HashMap<T, W>>,
587    in_edges: HashMap<T, HashMap<T, W>>,
588
589    empty: HashMap<T, W>,
590}
591
592impl<T, W> Default for DiGraph<T, W> {
593    fn default() -> Self {
594        DiGraph {
595            nodes: HashSet::new(),
596            edges: HashMap::new(),
597            in_edges: HashMap::new(),
598            empty: HashMap::new(),
599        }
600    }
601}
602
603impl<T, W> DiGraph<T, W>
604where
605    T: Clone + Copy + Eq + Hash + PartialEq,
606    W: Clone + Copy,
607{
608    pub fn new() -> Self {
609        Self::default()
610    }
611
612    fn bidir_find_path_filter_edges<G>(
613        &self,
614        from: T,
615        to: T,
616        predicate: G,
617    ) -> Option<Vec<(T, Orientation)>>
618    where
619        G: Fn(T, T, Orientation) -> bool,
620    {
621        let mut visited = HashSet::new();
622        let mut pairs = HashMap::new();
623        let mut queue = VecDeque::new();
624
625        queue.push_back((from, from, Orientation::Correct));
626
627        while let Some((prev, current, orientation)) = queue.pop_front() {
628            if visited.contains(&current) {
629                continue;
630            }
631            visited.insert(current);
632            pairs.insert(current, (prev, orientation));
633
634            if current == to {
635                let mut node = (current, orientation);
636
637                let mut path = Vec::new();
638                while node.0 != from {
639                    path.push((node.0, pairs[&node.0].1));
640
641                    node = pairs[&node.0];
642                }
643
644                path.push((node.0, pairs[&node.0].1));
645
646                path.reverse();
647
648                return Some(path);
649            }
650
651            for (target, _) in self.edges(&current) {
652                if visited.contains(&target) || !predicate(current, target, Orientation::Correct) {
653                    continue;
654                }
655
656                queue.push_back((current, target, Orientation::Correct));
657            }
658            for (target, _) in self.in_edges(&current) {
659                if visited.contains(&target) || !predicate(current, target, Orientation::Inverted) {
660                    continue;
661                }
662
663                queue.push_back((current, target, Orientation::Inverted));
664            }
665        }
666
667        None
668    }
669}
670
671#[derive(Debug, Clone, Copy, PartialEq, Eq)]
672enum Orientation {
673    Correct,
674    Inverted,
675}
676
677impl<T, W> GraphBuilding<T, W> for DiGraph<T, W>
678where
679    T: Clone + Copy + Eq + Hash + PartialEq,
680    W: Clone + Copy,
681{
682    fn add_edge(&mut self, from: T, to: T, weight: W) {
683        self.edges.entry(from).or_default().insert(to, weight);
684        self.in_edges.entry(to).or_default().insert(from, weight);
685
686        self.add_node(from);
687        self.add_node(to);
688    }
689
690    fn add_node(&mut self, node: T) -> bool {
691        self.nodes.insert(node)
692    }
693
694    fn remove_edge(&mut self, from: T, to: T) -> Result<(), NodeNotFound> {
695        self.edges.get_mut(&from).ok_or(NodeNotFound)?.remove(&to);
696        self.in_edges
697            .get_mut(&to)
698            .ok_or(NodeNotFound)?
699            .remove(&from);
700
701        Ok(())
702    }
703
704    fn remove_node(&mut self, node: T) -> Result<(), NodeNotFound> {
705        if !self.nodes.remove(&node) {
706            return Err(NodeNotFound);
707        }
708
709        self.edges.remove_entry(&node);
710
711        for edges in self.edges.values_mut() {
712            edges.remove(&node);
713        }
714
715        for edges in self.in_edges.values_mut() {
716            edges.remove(&node);
717        }
718
719        Ok(())
720    }
721
722    fn has_edge(&self, from: T, to: T) -> bool {
723        self.edges
724            .get(&from)
725            .map_or(false, |edges| edges.contains_key(&to))
726    }
727}
728
729impl<T, W> Traversable<T, W> for DiGraph<T, W>
730where
731    T: Clone + Copy + Eq + Hash + PartialEq,
732    W: Clone + Copy,
733{
734    fn nodes(&self) -> traits::NodeIter<'_, T> {
735        traits::NodeIter {
736            nodes_iter: self.nodes.iter(),
737        }
738    }
739
740    fn edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
741        let edges = self.edges.get(n);
742
743        if let Some(edges) = edges {
744            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
745                edge_iter: edges.iter(),
746            })
747        } else {
748            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
749                edge_iter: self.empty.iter(),
750            })
751        }
752    }
753
754    fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound> {
755        self.edges
756            .get(&from)
757            .ok_or(NodeNotFound)?
758            .get(&to)
759            .ok_or(NodeNotFound)
760            .copied()
761    }
762
763    fn in_edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
764        let edges = self.in_edges.get(n);
765
766        if let Some(edges) = edges {
767            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
768                edge_iter: edges.iter(),
769            })
770        } else {
771            traits::EdgeIterType::EdgeIter(traits::EdgeIter {
772                edge_iter: self.empty.iter(),
773            })
774        }
775    }
776}
777
778impl<T, W> ArithmeticallyWeightedGraph<T, W> for DiGraph<T, W>
779where
780    T: Clone + Copy + Eq + Hash + PartialEq,
781    W: Clone
782        + Copy
783        + std::ops::Add<Output = W>
784        + std::ops::Sub<Output = W>
785        + PartialOrd
786        + Ord
787        + Default,
788{
789    /// Runs the Edmonds-Karp algorithm on the graph to find max flow.
790    ///
791    /// Assumes the edge weights are the capacities.
792    ///
793    /// Returns a HashMap with the flow values for each edge.
794    ///
795    /// Please select a number type for W which allows for subtraction
796    /// and negative values, otherwise there may be undefined behavior.
797    ///
798    /// # Examples
799    ///
800    /// ```rust
801    /// use yagraphc::graph::UnGraph;
802    /// use yagraphc::graph::traits::{ArithmeticallyWeightedGraph, GraphBuilding, Traversable};
803    ///
804    /// let mut graph = UnGraph::new();
805    /// graph.add_edge(1, 2, 1000);
806    /// graph.add_edge(2, 4, 1000);
807    /// graph.add_edge(1, 3, 1000);
808    /// graph.add_edge(3, 4, 1000);
809    ///
810    /// graph.add_edge(2, 3, 1);
811    ///
812    /// let flows = graph.edmonds_karp(1, 4);
813    /// assert_eq!(*flows.get(&(1, 2)).unwrap(), 1000);
814    /// assert_eq!(*flows.get(&(1, 3)).unwrap(), 1000);
815    ///
816    /// assert_eq!(*flows.get(&(2, 3)).unwrap_or(&0), 0);
817    fn edmonds_karp(&self, source: T, sink: T) -> HashMap<(T, T), W> {
818        let flows = HashMap::new();
819
820        let mut residual_obtension = ResidualNetwork { flows, graph: self };
821
822        while let Some(path) = self.bidir_find_path_filter_edges(source, sink, |x, y, _| {
823            residual_obtension.get_residual_capacity(x, y) > W::default()
824        }) {
825            let residuals_in_path = path
826                .iter()
827                .zip(&path[1..])
828                .map(|(&(x, _), &(y, _))| residual_obtension.get_residual_capacity(x, y));
829
830            let min_res = residuals_in_path.min().expect("Path should not be empty");
831
832            path.iter().zip(&path[1..]).for_each(|(&(x, _), &(y, _))| {
833                residual_obtension
834                    .flows
835                    .entry((x, y))
836                    .and_modify(|v| *v = *v + min_res)
837                    .or_insert(min_res);
838                residual_obtension
839                    .flows
840                    .entry((y, x))
841                    .and_modify(|v| *v = *v - min_res)
842                    .or_insert(W::default() - min_res);
843            });
844
845            residual_obtension = ResidualNetwork {
846                flows: residual_obtension.flows,
847                graph: self,
848            };
849        }
850
851        residual_obtension.flows
852    }
853}
854
855struct ResidualNetwork<'a, T, W> {
856    flows: HashMap<(T, T), W>,
857    graph: &'a dyn Traversable<T, W>,
858}
859impl<'a, T, W> ResidualNetwork<'a, T, W>
860where
861    T: Clone + Copy + Eq + Hash + PartialEq,
862    W: Clone
863        + Copy
864        + std::ops::Add<Output = W>
865        + std::ops::Sub<Output = W>
866        + PartialOrd
867        + Ord
868        + Default,
869{
870    fn get_residual_capacity(&self, s: T, t: T) -> W {
871        self.graph.edge_weight(s, t).unwrap_or(W::default())
872            - self.flows.get(&(s, t)).copied().unwrap_or(W::default())
873    }
874}
875
876/// Directed graph using adjancency list as a Vec for each node.
877///
878/// Recommended for graphs that have vertices with low degree.
879#[derive(Debug, Clone)]
880pub struct DiGraphVecEdges<T, W> {
881    nodes: HashSet<T>,
882    edges: HashMap<T, Vec<(T, W)>>,
883    in_edges: HashMap<T, Vec<(T, W)>>,
884
885    empty: Vec<(T, W)>,
886}
887
888impl<T, W> Default for DiGraphVecEdges<T, W> {
889    fn default() -> Self {
890        DiGraphVecEdges {
891            nodes: HashSet::new(),
892            edges: HashMap::new(),
893            in_edges: HashMap::new(),
894            empty: Vec::new(),
895        }
896    }
897}
898
899impl<T, W> DiGraphVecEdges<T, W>
900where
901    T: Clone + Copy + Eq + Hash + PartialEq,
902    W: Clone + Copy,
903{
904    pub fn new() -> Self {
905        Self::default()
906    }
907
908    fn bidir_find_path_filter_edges<G>(
909        &self,
910        from: T,
911        to: T,
912        predicate: G,
913    ) -> Option<Vec<(T, Orientation)>>
914    where
915        G: Fn(T, T, Orientation) -> bool,
916    {
917        let mut visited = HashSet::new();
918        let mut pairs = HashMap::new();
919        let mut queue = VecDeque::new();
920
921        queue.push_back((from, from, Orientation::Correct));
922
923        while let Some((prev, current, orientation)) = queue.pop_front() {
924            if visited.contains(&current) {
925                continue;
926            }
927            visited.insert(current);
928            pairs.insert(current, (prev, orientation));
929
930            if current == to {
931                let mut node = (current, orientation);
932
933                let mut path = Vec::new();
934                while node.0 != from {
935                    path.push((node.0, pairs[&node.0].1));
936
937                    node = pairs[&node.0];
938                }
939
940                path.push((node.0, pairs[&node.0].1));
941
942                path.reverse();
943
944                return Some(path);
945            }
946
947            for (target, _) in self.edges(&current) {
948                if visited.contains(&target) || !predicate(current, target, Orientation::Correct) {
949                    continue;
950                }
951
952                queue.push_back((current, target, Orientation::Correct));
953            }
954            for (target, _) in self.in_edges(&current) {
955                if visited.contains(&target) || !predicate(current, target, Orientation::Inverted) {
956                    continue;
957                }
958
959                queue.push_back((current, target, Orientation::Inverted));
960            }
961        }
962
963        None
964    }
965}
966
967impl<T, W> GraphBuilding<T, W> for DiGraphVecEdges<T, W>
968where
969    T: Clone + Copy + Eq + Hash + PartialEq,
970    W: Clone + Copy,
971{
972    fn add_edge(&mut self, from: T, to: T, weight: W) {
973        self.edges.entry(from).or_default().push((to, weight));
974        self.in_edges.entry(to).or_default().push((from, weight));
975
976        self.nodes.insert(from);
977        self.nodes.insert(to);
978    }
979
980    fn add_node(&mut self, node: T) -> bool {
981        self.nodes.insert(node)
982    }
983
984    fn remove_edge(&mut self, from: T, to: T) -> Result<(), NodeNotFound> {
985        self.edges
986            .get_mut(&from)
987            .ok_or(NodeNotFound)?
988            .retain(|(node, _)| *node != to);
989
990        self.in_edges
991            .get_mut(&to)
992            .ok_or(NodeNotFound)?
993            .retain(|(node, _)| *node != from);
994
995        Ok(())
996    }
997
998    fn remove_node(&mut self, node: T) -> Result<(), NodeNotFound> {
999        if !self.nodes.remove(&node) {
1000            return Err(NodeNotFound);
1001        }
1002
1003        self.edges.remove_entry(&node);
1004
1005        for edges in self.edges.values_mut() {
1006            edges.retain(|(target, _)| *target != node);
1007        }
1008
1009        for edges in self.in_edges.values_mut() {
1010            edges.retain(|(target, _)| *target != node);
1011        }
1012
1013        Ok(())
1014    }
1015
1016    fn has_edge(&self, from: T, to: T) -> bool {
1017        self.edges
1018            .get(&from)
1019            .map_or(false, |edges| edges.iter().any(|(node, _)| *node == to))
1020    }
1021}
1022
1023impl<T, W> Traversable<T, W> for DiGraphVecEdges<T, W>
1024where
1025    T: Clone + Copy + Eq + Hash + PartialEq,
1026    W: Clone + Copy,
1027{
1028    fn nodes(&self) -> traits::NodeIter<'_, T> {
1029        traits::NodeIter {
1030            nodes_iter: self.nodes.iter(),
1031        }
1032    }
1033
1034    fn edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
1035        let edges = self.edges.get(n);
1036
1037        if let Some(edges) = edges {
1038            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
1039                edge_iter: edges.iter(),
1040            })
1041        } else {
1042            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
1043                edge_iter: self.empty.iter(),
1044            })
1045        }
1046    }
1047
1048    fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound> {
1049        self.edges
1050            .get(&from)
1051            .ok_or(NodeNotFound)?
1052            .iter()
1053            .find_map(|(x, y)| (*x == to).then_some(*y))
1054            .ok_or(NodeNotFound)
1055    }
1056
1057    fn in_edges(&self, n: &T) -> traits::EdgeIterType<T, W> {
1058        let edges = self.in_edges.get(n);
1059
1060        if let Some(edges) = edges {
1061            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
1062                edge_iter: edges.iter(),
1063            })
1064        } else {
1065            traits::EdgeIterType::EdgeIterVec(traits::EdgeIterVec {
1066                edge_iter: self.empty.iter(),
1067            })
1068        }
1069    }
1070}
1071
1072impl<T, W> ArithmeticallyWeightedGraph<T, W> for DiGraphVecEdges<T, W>
1073where
1074    T: Clone + Copy + Eq + Hash + PartialEq,
1075    W: Clone
1076        + Copy
1077        + std::ops::Add<Output = W>
1078        + std::ops::Sub<Output = W>
1079        + PartialOrd
1080        + Ord
1081        + Default,
1082{
1083    /// Runs the Edmonds-Karp algorithm on the graph to find max flow.
1084    ///
1085    /// Assumes the edge weights are the capacities.
1086    ///
1087    /// Returns a HashMap with the flow values for each edge.
1088    ///
1089    /// Please select a number type for W which allows for subtraction
1090    /// and negative values, otherwise there may be undefined behavior.
1091    ///
1092    /// # Examples
1093    ///
1094    /// ```rust
1095    /// use yagraphc::graph::UnGraph;
1096    /// use yagraphc::graph::traits::{ArithmeticallyWeightedGraph, GraphBuilding, Traversable};
1097    ///
1098    /// let mut graph = UnGraph::new();
1099    /// graph.add_edge(1, 2, 1000);
1100    /// graph.add_edge(2, 4, 1000);
1101    /// graph.add_edge(1, 3, 1000);
1102    /// graph.add_edge(3, 4, 1000);
1103    ///
1104    /// graph.add_edge(2, 3, 1);
1105    ///
1106    /// let flows = graph.edmonds_karp(1, 4);
1107    /// assert_eq!(*flows.get(&(1, 2)).unwrap(), 1000);
1108    /// assert_eq!(*flows.get(&(1, 3)).unwrap(), 1000);
1109    ///
1110    /// assert_eq!(*flows.get(&(2, 3)).unwrap_or(&0), 0);
1111    fn edmonds_karp(&self, source: T, sink: T) -> HashMap<(T, T), W> {
1112        let flows = HashMap::new();
1113
1114        let mut residual_obtension = ResidualNetwork { flows, graph: self };
1115
1116        while let Some(path) = self.bidir_find_path_filter_edges(source, sink, |x, y, _| {
1117            residual_obtension.get_residual_capacity(x, y) > W::default()
1118        }) {
1119            let residuals_in_path = path
1120                .iter()
1121                .zip(&path[1..])
1122                .map(|(&(x, _), &(y, _))| residual_obtension.get_residual_capacity(x, y));
1123
1124            let min_res = residuals_in_path.min().expect("Path should not be empty");
1125
1126            path.iter().zip(&path[1..]).for_each(|(&(x, _), &(y, _))| {
1127                residual_obtension
1128                    .flows
1129                    .entry((x, y))
1130                    .and_modify(|v| *v = *v + min_res)
1131                    .or_insert(min_res);
1132                residual_obtension
1133                    .flows
1134                    .entry((y, x))
1135                    .and_modify(|v| *v = *v - min_res)
1136                    .or_insert(W::default() - min_res);
1137            });
1138
1139            residual_obtension = ResidualNetwork {
1140                flows: residual_obtension.flows,
1141                graph: self,
1142            };
1143        }
1144
1145        residual_obtension.flows
1146    }
1147}
1148
1149#[cfg(test)]
1150mod tests {
1151    use std::vec;
1152
1153    use super::*;
1154
1155    #[test]
1156    fn test_derives() {
1157        let g = UnGraph::<(), ()>::new();
1158        _ = g.clone();
1159        dbg!(g);
1160
1161        let g = DiGraph::<(), ()>::new();
1162        _ = g.clone();
1163        dbg!(g);
1164
1165        let g = UnGraphVecEdges::<(), ()>::new();
1166        _ = g.clone();
1167        dbg!(g);
1168
1169        let g = DiGraphVecEdges::<(), ()>::new();
1170        _ = g.clone();
1171        dbg!(g);
1172    }
1173
1174    #[test]
1175    fn test_dijkstra() {
1176        let mut graph = UnGraph::default();
1177
1178        graph.add_edge(1, 2, 3);
1179        graph.add_edge(2, 3, 10);
1180        graph.add_edge(1, 3, 15);
1181
1182        assert_eq!(graph.dijkstra(1, 3), Some(13));
1183        assert_eq!(graph.dijkstra_with_path(1, 3).unwrap().0, vec![1, 2, 3]);
1184
1185        graph.add_edge(1, 4, 7);
1186        graph.add_edge(4, 3, 5);
1187
1188        assert_eq!(graph.dijkstra(1, 3), Some(12));
1189        assert_eq!(graph.dijkstra_with_path(1, 3).unwrap().0, vec![1, 4, 3]);
1190
1191        assert!(graph.dijkstra(1, 9).is_none());
1192        assert!(graph.dijkstra_with_path(1, 9).is_none());
1193    }
1194
1195    #[test]
1196    fn test_dijkstra_directed() {
1197        let mut graph = DiGraph::default();
1198
1199        graph.add_edge(1, 2, 3);
1200        graph.add_edge(2, 3, 10);
1201        graph.add_edge(1, 3, 15);
1202
1203        assert_eq!(graph.dijkstra(1, 3), Some(13));
1204        assert_eq!(graph.dijkstra(3, 1), None);
1205
1206        graph.add_edge(1, 4, 7);
1207        graph.add_edge(4, 3, 5);
1208
1209        assert_eq!(graph.dijkstra(1, 3), Some(12));
1210        assert_eq!(graph.dijkstra(3, 1), None);
1211    }
1212
1213    #[test]
1214    fn test_bfs() {
1215        let mut graph = UnGraph::default();
1216
1217        graph.add_edge(1, 2, 3);
1218        graph.add_edge(2, 3, 10);
1219
1220        assert_eq!(graph.bfs(1).find(|x| x.0 == 3).unwrap(), (3, 2));
1221
1222        graph.add_edge(1, 3, 15);
1223
1224        assert_eq!(graph.bfs(1).find(|x| x.0 == 3), Some((3, 1)));
1225    }
1226
1227    #[test]
1228    fn test_dfs() {
1229        let mut graph = UnGraph::default();
1230
1231        graph.add_edge(1, 2, 3);
1232        graph.add_edge(2, 3, 10);
1233
1234        assert_eq!(graph.dfs(1).find(|x| x.0 == 3).unwrap(), (3, 2));
1235
1236        graph.add_edge(1, 3, 15);
1237
1238        assert_eq!(graph.dfs(1).count(), 3);
1239    }
1240
1241    #[test]
1242    fn test_bfs2() {
1243        let mut graph = UnGraph::default();
1244
1245        graph.add_edge(1, 2, 3);
1246        graph.add_edge(2, 3, 10);
1247        graph.add_edge(1, 3, 15);
1248        graph.add_edge(3, 4, 4);
1249        graph.add_edge(4, 5, 7);
1250        graph.add_edge(1, 10, 3);
1251
1252        let values: Vec<(i32, usize)> = graph.bfs(1).collect();
1253
1254        assert_eq!(values.len(), 6);
1255    }
1256
1257    #[test]
1258    fn test_find_path() {
1259        let mut graph = UnGraph::default();
1260
1261        graph.add_edge(1, 2, ());
1262        graph.add_edge(2, 3, ());
1263        graph.add_edge(3, 4, ());
1264
1265        graph.add_edge(1, 5, ());
1266        graph.add_edge(5, 3, ());
1267        graph.add_edge(3, 4, ());
1268
1269        let path = graph.find_path(1, 4).unwrap();
1270
1271        assert_eq!(path.len(), 4);
1272
1273        assert!(graph.find_path(1, 7).is_none());
1274    }
1275
1276    #[test]
1277    fn test_find_path_filter_edges() {
1278        let mut graph = UnGraph::default();
1279
1280        graph.add_edge(1, 2, ());
1281        graph.add_edge(2, 3, ());
1282        graph.add_edge(3, 4, ());
1283        graph.add_edge(4, 5, ());
1284
1285        graph.add_edge(1, 7, ());
1286        graph.add_edge(7, 5, ());
1287
1288        let path = graph.find_path(1, 5).unwrap();
1289
1290        assert_eq!(path, vec![1, 7, 5]);
1291
1292        let path = graph
1293            .find_path_filter_edges(1, 5, |x, y| (x, y) != (1, 7))
1294            .unwrap();
1295
1296        assert_eq!(path, vec![1, 2, 3, 4, 5]);
1297    }
1298
1299    #[test]
1300    fn test_dijkstra_str() {
1301        let mut graph = DiGraph::default();
1302
1303        graph.add_edge("a", "b", 123);
1304        graph.add_edge("b", "c", 43);
1305        graph.add_edge("c", "d", 62);
1306
1307        graph.add_edge("a", "d", 253);
1308
1309        assert_eq!(graph.dijkstra("a", "d").unwrap(), 228);
1310    }
1311
1312    #[test]
1313    fn test_a_star() {
1314        let mut graph = DiGraph::default();
1315
1316        graph.add_edge(1, 2, 12);
1317        graph.add_edge(2, 3, 13);
1318        graph.add_edge(3, 4, 8);
1319
1320        graph.add_edge(1, 4, 40);
1321
1322        assert_eq!(graph.a_star(1, 4, |x| 4 - x).unwrap(), 33);
1323        assert!(graph.a_star(1, 10, |x| 10 - x).is_none());
1324    }
1325
1326    #[test]
1327    fn test_a_star_with_path() {
1328        let mut graph = DiGraph::default();
1329
1330        graph.add_edge(1, 2, 12);
1331        graph.add_edge(2, 3, 13);
1332        graph.add_edge(3, 4, 8);
1333
1334        graph.add_edge(1, 4, 40);
1335
1336        assert_eq!(
1337            graph.a_star_with_path(1, 4, |x| 4 - x).unwrap().0,
1338            vec![1, 2, 3, 4]
1339        );
1340        assert!(graph.a_star_with_path(1, 10, |x| 10 - x).is_none());
1341
1342        let mut graph = DiGraph::default();
1343
1344        graph.add_edge(1, 2, 6);
1345        graph.add_edge(2, 3, 10);
1346        graph.add_edge(1, 3, 13);
1347        graph.add_edge(3, 4, 40);
1348
1349        assert_eq!(
1350            graph.a_star_with_path(1, 4, |_| 0).unwrap().0,
1351            vec![1, 3, 4]
1352        );
1353    }
1354
1355    #[test]
1356    fn test_connected_components() {
1357        let mut graph = DiGraph::default();
1358
1359        graph.add_edge(1, 2, 12);
1360        graph.add_edge(2, 3, 13);
1361        graph.add_edge(3, 4, 8);
1362
1363        graph.add_edge(5, 6, 40);
1364
1365        assert_eq!(graph.connected_components().len(), 6);
1366
1367        graph.add_edge(4, 1, 8);
1368
1369        assert_eq!(graph.connected_components().len(), 3);
1370
1371        let mut graph = UnGraph::default();
1372
1373        graph.add_edge(1, 2, 12);
1374        graph.add_edge(2, 3, 13);
1375        graph.add_edge(3, 4, 8);
1376
1377        graph.add_edge(5, 6, 40);
1378
1379        assert_eq!(graph.connected_components().len(), 2);
1380
1381        let mut graph = UnGraphVecEdges::default();
1382
1383        graph.add_edge(1, 2, 12);
1384        graph.add_edge(2, 3, 13);
1385        graph.add_edge(3, 4, 8);
1386
1387        graph.add_edge(5, 6, 40);
1388
1389        assert_eq!(graph.connected_components().len(), 2);
1390    }
1391
1392    #[test]
1393    fn test_connected_components2() {
1394        let mut graph = DiGraph::default();
1395
1396        for i in 0..15 {
1397            for j in (i + 1)..15 {
1398                graph.add_edge(i, j, ())
1399            }
1400        }
1401
1402        assert_eq!(graph.connected_components().len(), 15);
1403
1404        let mut graph = UnGraph::default();
1405
1406        for i in 0..15 {
1407            for j in (i + 1)..15 {
1408                graph.add_edge(i, j, ())
1409            }
1410        }
1411
1412        assert_eq!(graph.connected_components().len(), 1);
1413    }
1414
1415    #[test]
1416    fn test_dfs_post_order() {
1417        let mut graph = UnGraph::default();
1418
1419        graph.add_edge(1, 2, ());
1420        graph.add_edge(1, 3, ());
1421
1422        graph.add_edge(2, 4, ());
1423        graph.add_edge(2, 5, ());
1424
1425        graph.add_edge(3, 6, ());
1426        graph.add_edge(6, 7, ());
1427        graph.add_edge(7, 8, ());
1428
1429        graph.add_edge(5, 9, ());
1430        graph.add_edge(5, 10, ());
1431
1432        let dfs_post_order: Vec<_> = graph.dfs_post_order(1).map(|x| x.0).collect();
1433
1434        assert_eq!(dfs_post_order.len(), 10);
1435    }
1436
1437    #[test]
1438    fn test_cycles() {
1439        let mut graph = UnGraph::default();
1440
1441        graph.add_edge(1, 2, ());
1442        graph.add_edge(2, 3, ());
1443        graph.add_edge(3, 4, ());
1444
1445        let cycles = graph.basic_cycles();
1446        assert_eq!(cycles.len(), 0);
1447
1448        graph.add_edge(4, 1, ());
1449        let cycles = graph.basic_cycles();
1450        assert_eq!(cycles.len(), 1);
1451    }
1452
1453    #[test]
1454    fn test_cycles2() {
1455        let mut graph = UnGraph::default();
1456
1457        graph.add_edge(1, 2, ());
1458        graph.add_edge(2, 3, ());
1459        graph.add_edge(3, 4, ());
1460        graph.add_edge(4, 1, ());
1461
1462        graph.add_edge(2, 5, ());
1463
1464        graph.add_edge(5, 6, ());
1465        graph.add_edge(6, 7, ());
1466        graph.add_edge(7, 5, ());
1467
1468        let cycles = graph.basic_cycles();
1469        assert_eq!(cycles.len(), 2);
1470
1471        graph.remove_edge(6, 7).unwrap();
1472
1473        let cycles = graph.basic_cycles();
1474        assert_eq!(cycles.len(), 1);
1475
1476        let mut graph = UnGraphVecEdges::default();
1477
1478        graph.add_edge(1, 2, ());
1479        graph.add_edge(2, 3, ());
1480        graph.add_edge(3, 4, ());
1481        graph.add_edge(4, 1, ());
1482
1483        graph.add_edge(2, 5, ());
1484
1485        graph.add_edge(5, 6, ());
1486        graph.add_edge(6, 7, ());
1487        graph.add_edge(7, 5, ());
1488
1489        let cycles = graph.basic_cycles();
1490        assert_eq!(cycles.len(), 2);
1491
1492        graph.remove_edge(6, 7).unwrap();
1493
1494        let cycles = graph.basic_cycles();
1495        assert_eq!(cycles.len(), 1);
1496    }
1497
1498    #[test]
1499    fn ungraph_maintenance() {
1500        let mut graph = UnGraph::<i32, ()>::new();
1501        graph.add_node(0);
1502
1503        assert_eq!(graph.nodes().count(), 1);
1504
1505        graph.remove_node(0).unwrap();
1506        assert_eq!(graph.nodes().count(), 0);
1507        assert!(graph.remove_node(0).is_err());
1508
1509        assert_eq!(graph.edges(&0).count(), 0);
1510        assert_eq!(graph.in_edges(&0).count(), 0);
1511
1512        assert!(!graph.has_edge(0, 1));
1513
1514        graph.add_edge(0, 1, ());
1515        assert!(graph.has_edge(0, 1));
1516        graph.remove_node(0).unwrap();
1517        assert!(!graph.has_edge(0, 1));
1518
1519        let mut graph = UnGraphVecEdges::<i32, ()>::new();
1520        graph.add_node(0);
1521
1522        assert_eq!(graph.nodes().count(), 1);
1523
1524        graph.remove_node(0).unwrap();
1525        assert_eq!(graph.nodes().count(), 0);
1526        assert!(graph.remove_node(0).is_err());
1527
1528        assert_eq!(graph.edges(&0).count(), 0);
1529        assert_eq!(graph.in_edges(&0).count(), 0);
1530
1531        assert!(!graph.has_edge(0, 1));
1532
1533        graph.add_edge(0, 1, ());
1534        assert!(graph.has_edge(0, 1));
1535        graph.remove_node(0).unwrap();
1536        assert!(!graph.has_edge(0, 1));
1537    }
1538
1539    #[test]
1540    fn digraph_maintenance() {
1541        let mut graph = DiGraph::<i32, ()>::new();
1542        graph.add_node(0);
1543
1544        assert_eq!(graph.nodes().count(), 1);
1545
1546        graph.remove_node(0).unwrap();
1547        assert_eq!(graph.nodes().count(), 0);
1548        assert!(graph.remove_node(0).is_err());
1549
1550        assert_eq!(graph.edges(&0).count(), 0);
1551        assert_eq!(graph.in_edges(&0).count(), 0);
1552
1553        assert!(!graph.has_edge(0, 1));
1554
1555        graph.add_edge(0, 1, ());
1556        assert!(graph.has_edge(0, 1));
1557        graph.remove_node(0).unwrap();
1558        assert!(!graph.has_edge(0, 1));
1559
1560        graph.add_edge(0, 1, ());
1561        graph.remove_edge(0, 1).unwrap();
1562
1563        assert!(!graph.has_edge(0, 1));
1564        assert!(graph.nodes().any(|x| x == 0));
1565        assert!(graph.nodes().any(|x| x == 1));
1566
1567        graph.add_edge(3, 4, ());
1568        graph.add_edge(4, 5, ());
1569        graph.add_edge(4, 6, ());
1570
1571        assert!(graph.has_edge(3, 4));
1572        assert!(graph.has_edge(4, 5));
1573        assert!(graph.has_edge(4, 6));
1574        assert!(!graph.has_edge(4, 3));
1575        assert!(!graph.has_edge(5, 4));
1576        assert!(!graph.has_edge(6, 4));
1577
1578        assert_eq!(graph.edges(&4).count(), 2);
1579        assert_eq!(graph.in_edges(&4).count(), 1);
1580
1581        graph.remove_node(4).unwrap();
1582
1583        assert!(!graph.has_edge(3, 4));
1584        assert!(!graph.has_edge(4, 5));
1585        assert!(!graph.has_edge(4, 6));
1586
1587        let mut graph = DiGraphVecEdges::<i32, ()>::new();
1588        graph.add_node(0);
1589
1590        assert_eq!(graph.nodes().count(), 1);
1591
1592        graph.remove_node(0).unwrap();
1593        assert_eq!(graph.nodes().count(), 0);
1594        assert!(graph.remove_node(0).is_err());
1595
1596        assert_eq!(graph.edges(&0).count(), 0);
1597        assert_eq!(graph.in_edges(&0).count(), 0);
1598
1599        assert!(!graph.has_edge(0, 1));
1600
1601        graph.add_edge(0, 1, ());
1602        assert!(graph.has_edge(0, 1));
1603        graph.remove_node(0).unwrap();
1604        assert!(!graph.has_edge(0, 1));
1605
1606        graph.add_edge(0, 1, ());
1607        graph.remove_edge(0, 1).unwrap();
1608
1609        assert!(!graph.has_edge(0, 1));
1610        assert!(graph.nodes().any(|x| x == 0));
1611        assert!(graph.nodes().any(|x| x == 1));
1612
1613        graph.add_edge(3, 4, ());
1614        graph.add_edge(4, 5, ());
1615        graph.add_edge(4, 6, ());
1616
1617        assert!(graph.has_edge(3, 4));
1618        assert!(graph.has_edge(4, 5));
1619        assert!(graph.has_edge(4, 6));
1620        assert!(!graph.has_edge(4, 3));
1621        assert!(!graph.has_edge(5, 4));
1622        assert!(!graph.has_edge(6, 4));
1623
1624        assert_eq!(graph.edges(&4).count(), 2);
1625        assert_eq!(graph.in_edges(&4).count(), 1);
1626
1627        graph.remove_node(4).unwrap();
1628
1629        assert!(!graph.has_edge(3, 4));
1630        assert!(!graph.has_edge(4, 5));
1631        assert!(!graph.has_edge(4, 6));
1632    }
1633
1634    #[test]
1635    fn test_bidir_find_path() {
1636        let mut digraph = DiGraph::new();
1637
1638        digraph.add_edge("B", "A", ());
1639        digraph.add_edge("B", "C", ());
1640
1641        let path = digraph
1642            .bidir_find_path_filter_edges("A", "C", |_, _, _| true)
1643            .unwrap();
1644
1645        assert_eq!(
1646            path,
1647            [
1648                ("A", Orientation::Correct),
1649                ("B", Orientation::Inverted),
1650                ("C", Orientation::Correct)
1651            ]
1652        )
1653    }
1654
1655    #[test]
1656    fn test_edmonds_karp() {
1657        let mut g = UnGraph::new();
1658
1659        g.add_edge("A", "B", 1000);
1660        g.add_edge("A", "C", 1000);
1661
1662        g.add_edge("B", "C", 1);
1663
1664        g.add_edge("B", "D", 1000);
1665        g.add_edge("C", "D", 1000);
1666
1667        let flows = g.edmonds_karp("A", "D");
1668
1669        assert_eq!(*flows.get(&("A", "B")).unwrap(), 1000);
1670        assert_eq!(*flows.get(&("A", "C")).unwrap(), 1000);
1671
1672        assert_eq!(*flows.get(&("B", "C")).unwrap_or(&0), 0);
1673
1674        assert_eq!(*flows.get(&("B", "D")).unwrap(), 1000);
1675        assert_eq!(*flows.get(&("C", "D")).unwrap(), 1000);
1676
1677        let mut g = UnGraph::new();
1678
1679        g.add_edge("C", "A", 3);
1680        g.add_edge("C", "D", 1);
1681        g.add_edge("C", "E", 2);
1682
1683        g.add_edge("B", "C", 4);
1684
1685        g.add_edge("A", "B", 3);
1686        g.add_edge("A", "D", 3);
1687
1688        g.add_edge("D", "E", 2);
1689        g.add_edge("D", "F", 6);
1690
1691        g.add_edge("E", "G", 1);
1692        g.add_edge("E", "B", 1);
1693
1694        g.add_edge("F", "G", 9);
1695
1696        let flows = g.edmonds_karp("A", "G");
1697
1698        assert_eq!(*flows.get(&("E", "G")).unwrap_or(&0), 1);
1699        assert_eq!(*flows.get(&("F", "G")).unwrap_or(&0), 6);
1700
1701        let mut g = UnGraphVecEdges::new();
1702
1703        g.add_edge("C", "A", 3);
1704        g.add_edge("C", "D", 1);
1705        g.add_edge("C", "E", 2);
1706
1707        g.add_edge("B", "C", 4);
1708
1709        g.add_edge("A", "B", 3);
1710        g.add_edge("A", "D", 3);
1711
1712        g.add_edge("D", "E", 2);
1713        g.add_edge("D", "F", 6);
1714
1715        g.add_edge("E", "G", 1);
1716        g.add_edge("E", "B", 1);
1717
1718        g.add_edge("F", "G", 9);
1719
1720        let flows = g.edmonds_karp("A", "G");
1721
1722        assert_eq!(*flows.get(&("E", "G")).unwrap_or(&0), 1);
1723        assert_eq!(*flows.get(&("F", "G")).unwrap_or(&0), 6);
1724    }
1725
1726    #[test]
1727    fn test_edmonds_karp_directed() {
1728        let mut g = DiGraph::new();
1729
1730        g.add_edge("C", "A", 3);
1731        g.add_edge("C", "D", 1);
1732        g.add_edge("C", "E", 2);
1733
1734        g.add_edge("B", "C", 4);
1735
1736        g.add_edge("A", "B", 3);
1737        g.add_edge("A", "D", 3);
1738
1739        g.add_edge("D", "E", 2);
1740        g.add_edge("D", "F", 6);
1741
1742        g.add_edge("E", "G", 1);
1743        g.add_edge("E", "B", 1);
1744
1745        g.add_edge("F", "G", 9);
1746
1747        let flows = g.edmonds_karp("A", "G");
1748
1749        assert_eq!(*flows.get(&("E", "G")).unwrap_or(&0), 1);
1750        assert_eq!(*flows.get(&("F", "G")).unwrap_or(&0), 4);
1751
1752        // Same test but with DiGraphVecEdges.
1753        let mut g = DiGraphVecEdges::new();
1754
1755        g.add_edge("C", "A", 3);
1756        g.add_edge("C", "D", 1);
1757        g.add_edge("C", "E", 2);
1758
1759        g.add_edge("B", "C", 4);
1760
1761        g.add_edge("A", "B", 3);
1762        g.add_edge("A", "D", 3);
1763
1764        g.add_edge("D", "E", 2);
1765        g.add_edge("D", "F", 6);
1766
1767        g.add_edge("E", "G", 1);
1768        g.add_edge("E", "B", 1);
1769
1770        g.add_edge("F", "G", 9);
1771
1772        let flows = g.edmonds_karp("A", "G");
1773
1774        println!("{:#?}", flows);
1775
1776        assert_eq!(*flows.get(&("E", "G")).unwrap_or(&0), 1);
1777        assert_eq!(*flows.get(&("F", "G")).unwrap_or(&0), 4);
1778    }
1779}
yagraphc/graph.rs

yagraphc/
graph.rs
