DFS API now returns edges, skips root

EbTech · EbTech · commit f7e1f7190b3e · 2020-09-20T21:59:13.000-07:00
diff --git a/README.md b/README.md
@@ -69,6 +69,7 @@ Rather than try to persuade you with words, this repository aims to show by exam
 ### [Network flows](src/graph/flow.rs)
 
 - Dinic's blocking maximum flow
+- Minimum cut
 - Hopcroft-Karp bipartite matching
 - Minimum cost maximum flow
 
diff --git a/src/graph/mod.rs b/src/graph/mod.rs
@@ -130,14 +130,18 @@ mod test {
 
     #[test]
     fn test_adj_list() {
-        let mut graph = Graph::new(4, 4);
-        graph.add_edge(0, 1);
+        let mut graph = Graph::new(5, 6);
+        graph.add_edge(2, 3);
+        graph.add_edge(2, 4);
+        graph.add_edge(4, 1);
         graph.add_edge(1, 2);
-        graph.add_edge(1, 3);
-        graph.add_edge(3, 0);
+        graph.add_undirected_edge(0, 2);
 
-        let adj: Vec<(usize, usize)> = graph.adj_list(1).collect();
+        let adj = graph.adj_list(2).collect::<Vec<_>>();
 
-        assert_eq!(adj, vec![(2, 3), (1, 2)]);
+        assert_eq!(adj, vec![(5, 0), (1, 4), (0, 3)]);
+        for (e, v) in adj {
+            assert_eq!(v, graph.endp[e]);
+        }
     }
 }
diff --git a/src/graph/util.rs b/src/graph/util.rs
@@ -61,14 +61,16 @@ impl Graph {
         dist
     }
 
-    pub fn dfs(&self, u: usize) -> DfsIterator {
+    pub fn dfs(&self, root: usize) -> DfsIterator {
+        let mut visited = vec![false; self.num_v()];
+        visited[root] = true;
         let adj_iters = (0..self.num_v())
             .map(|u| self.adj_list(u))
             .collect::<Vec<_>>();
 
         DfsIterator {
-            visited: vec![false; self.num_v()],
-            stack: vec![u],
+            visited,
+            stack: vec![root],
             adj_iters,
         }
     }
@@ -81,32 +83,23 @@ pub struct DfsIterator<'a> {
 }
 
 impl<'a> Iterator for DfsIterator<'a> {
-    type Item = usize;
+    type Item = (usize, usize);
 
-    /// Returns next vertex in the DFS
+    /// Returns next edge and vertex in the depth-first traversal
+    // Refs: https://www.geeksforgeeks.org/iterative-depth-first-traversal/
+    //       https://en.wikipedia.org/wiki/Depth-first_search
     fn next(&mut self) -> Option<Self::Item> {
-        // Sources:
-        // https://www.geeksforgeeks.org/iterative-depth-first-traversal/
-        // https://en.wikipedia.org/wiki/Depth-first_search
-        while let Some(&u) = self.stack.last() {
-            if let Some((_, v)) = self.adj_iters[u].next() {
+        loop {
+            let &u = self.stack.last()?;
+            while let Some((e, v)) = self.adj_iters[u].next() {
                 if !self.visited[v] {
+                    self.visited[v] = true;
                     self.stack.push(v);
+                    return Some((e, v));
                 }
-            } else {
-                self.stack.pop();
-            }
-
-            // Stack may contain same vertex twice. So
-            // we return the popped item only
-            // if it is not visited.
-            if !self.visited[u] {
-                self.visited[u] = true;
-                return Some(u);
             }
+            self.stack.pop();
         }
-
-        None
     }
 }
 
@@ -153,31 +146,38 @@ mod test {
 
     #[test]
     fn test_dfs() {
-        let mut graph = Graph::new(4, 8);
+        let mut graph = Graph::new(4, 6);
         graph.add_edge(0, 2);
         graph.add_edge(2, 0);
         graph.add_edge(1, 2);
         graph.add_edge(0, 1);
         graph.add_edge(3, 3);
         graph.add_edge(2, 3);
 
-        let dfs_search = graph.dfs(2).collect::<Vec<_>>();
-        assert_eq!(dfs_search, vec![2, 3, 0, 1]);
+        let dfs_root = 2;
+        let dfs_traversal = std::iter::once(dfs_root)
+            .chain(graph.dfs(dfs_root).map(|(_, v)| v))
+            .collect::<Vec<_>>();
+
+        assert_eq!(dfs_traversal, vec![2, 3, 0, 1]);
     }
 
     #[test]
     fn test_dfs2() {
-        let mut graph = Graph::new(5, 8);
+        let mut graph = Graph::new(5, 6);
         graph.add_edge(0, 2);
         graph.add_edge(2, 1);
         graph.add_edge(1, 0);
         graph.add_edge(0, 3);
         graph.add_edge(3, 4);
         graph.add_edge(4, 0);
 
-        let dfs_search = graph.dfs(0).collect::<Vec<_>>();
-        //Note this is not the only valid DFS
-        assert_eq!(dfs_search, vec![0, 3, 4, 2, 1]);
+        let dfs_root = 0;
+        let dfs_traversal = std::iter::once(dfs_root)
+            .chain(graph.dfs(dfs_root).map(|(_, v)| v))
+            .collect::<Vec<_>>();
+
+        assert_eq!(dfs_traversal, vec![0, 3, 4, 2, 1]);
     }
 
     #[test]
@@ -190,10 +190,11 @@ mod test {
             }
         }
 
-        let mut dfs_search = graph.dfs(7);
-        let mut dfs_check = vec![];
-        for _ in 0..num_v {
-            dfs_check.push(dfs_search.next().unwrap());
+        let dfs_root = 7;
+        let mut dfs_search = graph.dfs(dfs_root);
+        let mut dfs_check = vec![dfs_root];
+        for _ in 1..num_v {
+            dfs_check.push(dfs_search.next().unwrap().1);
             assert!(dfs_search.stack.len() <= num_v + 1);
         }
 
diff --git a/src/order.rs b/src/order.rs
@@ -80,7 +80,7 @@ impl SparseIndex {
 /// It combines the offline algorithm with square root decomposition, resulting in an
 /// asymptotically suboptimal but simple algorithm with good amortized performance:
 /// N inserts interleaved with Q queries yields O(N sqrt Q + Q log N) time complexity
-/// in general, or O(N + Q log N) if all queries come after all inserts.
+/// in general, or O((N + Q) log N) if all queries come after all inserts.
 // Proof: the Q log N term comes from calls to slice_lower_bound(). As for the N sqrt Q,
 //        note that between successive times when the hull is rebuilt, O(N) work is done,
 //        and the running totals of insertions and queries satisfy del_N (del_Q + 1) > N.
