Repository: petgraph/petgraph (language: rust)

Issue:
Removing a node in a directed GraphMap does not remove incoming edges
When using a directed GraphMap, removing a node does not remove incoming edges to that node. I believe this is a bug—as far as I can tell, the expected invariant is that a node only has an entry in its adjacency list if the neighbor is in the graph and also has the corresponding adjacency. The documentation for remove_node mentions that it removes edges in `O(|V|)`.

This reproduces on master as well as 0.5.1.

### Test Case

```rust
use petgraph; // 0.5.1

fn main() {
    let mut graph = petgraph::graphmap::DiGraphMap::<u32, ()>::new();
    
    graph.add_edge(1, 2, ());
    graph.remove_node(2);
    
    let neighbors: Vec<u32> = graph.neighbors(1).collect();

    assert_eq!(neighbors, []);
}
```

([playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=970bb94ee486e410950f857b6a133619))

### Actual Results

```rust
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[2]`,
 right: `[]`', src/main.rs:11:5
```

### Expected Results

I would expect `2` to be no longer be yielded as a neighbor of `1` once the node `2` has been removed from the graph.

I also hit this when using `petgraph::dot::Dot`, where it manifested as a panic on `Option::unwrap` in the impl of `petgraph::visit::NodeIndexable::to_index`. Backtrace snippet:

```
   3: core::option::Option<T>::unwrap
             at $path/.rustup/toolchains/stable-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/option.rs:386:21
   4: <petgraph::graphmap::GraphMap<N,E,Ty> as petgraph::visit::NodeIndexable>::to_index
             at $path/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.5.1/src/graphmap.rs:933:25
   5: <&G as petgraph::visit::NodeIndexable>::to_index
             at $path/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.5.1/src/visit/macros.rs:129:21
   6: petgraph::dot::Dot<G>::graph_fmt
             at $path/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.5.1/src/dot.rs:159:17
   7: <petgraph::dot::Dot<G> as core::fmt::Debug>::fmt
             at $path/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.5.1/src/dot.rs:198:9
```


Discussion / hints:
Thanks, I'll look into this.

Fix patch:
diff --git a/src/graphmap.rs b/src/graphmap.rs
index 5a0213817..5556a025e 100644
--- a/src/graphmap.rs
+++ b/src/graphmap.rs
@@ -80,6 +80,17 @@ enum CompactDirection {
     Incoming,
 }
 
+impl CompactDirection {
+    /// Return the opposite `CompactDirection`.
+    #[inline]
+    pub fn opposite(self) -> CompactDirection {
+        match self {
+            CompactDirection::Outgoing => CompactDirection::Incoming,
+            CompactDirection::Incoming => CompactDirection::Outgoing,
+        }
+    }
+}
+
 impl From<Direction> for CompactDirection {
     fn from(d: Direction) -> Self {
         match d {
@@ -89,6 +100,15 @@ impl From<Direction> for CompactDirection {
     }
 }
 
+impl From<CompactDirection> for Direction {
+    fn from(d: CompactDirection) -> Self {
+        match d {
+            CompactDirection::Outgoing => Outgoing,
+            CompactDirection::Incoming => Incoming,
+        }
+    }
+}
+
 impl PartialEq<Direction> for CompactDirection {
     fn eq(&self, rhs: &Direction) -> bool {
         (*self as usize) == (*rhs as usize)
@@ -191,11 +211,16 @@ where
             None => return false,
             Some(sus) => sus,
         };
-        for (succ, _) in links {
+        for (succ, dir) in links {
+            let edge = if dir == CompactDirection::Outgoing {
+                Self::edge_key(n, succ)
+            } else {
+                Self::edge_key(succ, n)
+            };
             // remove all successor links
-            self.remove_single_edge(&succ, &n, Incoming);
+            self.remove_single_edge(&succ, &n, dir.opposite());
             // Remove all edge values
-            self.edges.swap_remove(&Self::edge_key(n, succ));
+            self.edges.swap_remove(&edge);
         }
         true
     }
@@ -249,15 +274,12 @@ where
     /// Remove edge relation from a to b
     ///
     /// Return `true` if it did exist.
-    fn remove_single_edge(&mut self, a: &N, b: &N, dir: Direction) -> bool {
+    fn remove_single_edge(&mut self, a: &N, b: &N, dir: CompactDirection) -> bool {
         match self.nodes.get_mut(a) {
             None => false,
             Some(sus) => {
                 if Ty::is_directed() {
-                    match sus
-                        .iter()
-                        .position(|elt| elt == &(*b, CompactDirection::from(dir)))
-                    {
+                    match sus.iter().position(|elt| elt == &(*b, dir)) {
                         Some(index) => {
                             sus.swap_remove(index);
                             true
@@ -293,9 +315,9 @@ where
     /// assert_eq!(g.edge_count(), 0);
     /// ```
     pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
-        let exist1 = self.remove_single_edge(&a, &b, Outgoing);
+        let exist1 = self.remove_single_edge(&a, &b, CompactDirection::Outgoing);
         let exist2 = if a != b {
-            self.remove_single_edge(&b, &a, Incoming)
+            self.remove_single_edge(&b, &a, CompactDirection::Incoming)
         } else {
             exist1
         };


Test patch:
diff --git a/tests/graphmap.rs b/tests/graphmap.rs
index 6891cf78e..bb2b2535c 100644
--- a/tests/graphmap.rs
+++ b/tests/graphmap.rs
@@ -82,6 +82,20 @@ fn remov() {
     assert_eq!(g.neighbors(1).count(), 0);
 }
 
+#[test]
+fn remove_node() {
+    // From #431
+    let mut graph = petgraph::graphmap::DiGraphMap::<u32, ()>::new();
+    graph.add_edge(1, 2, ());
+    graph.remove_node(2);
+
+    let neighbors: Vec<u32> = graph.neighbors(1).collect();
+    assert_eq!(neighbors, []);
+
+    let edges: Vec<(u32, u32, _)> = graph.all_edges().collect();
+    assert_eq!(edges, []);
+}
+
 #[test]
 fn remove_directed() {
     let mut g = GraphMap::<_, _, Directed>::with_capacity(0, 0);