zrwusa / data-structure-typed

Javascript Data Structure & TypeScript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree, AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack.
https://data-structure-typed-docs.vercel.app
MIT License
114 stars 8 forks source link

Removing a vertex doesn't delete the incoming edges of associated vertices #62

Closed rkrump closed 8 months ago

rkrump commented 8 months ago

Describe the bug It looks like #51 is not fully fixed yet. The _inEdgeMap of the target vertices still contain the invalid edges.

To Reproduce Steps to reproduce the behavior:

  1. Create directed graph with the vertices "Hello" & "Hi"
  2. Add an edge from "Hello" to "Hi"
  3. Delete the vertex "Hello"
  4. incomingEdgesOf on "Hi" still reports the edge from the source vertex "Hello"
import { DirectedGraph } from "graph-typed";

let graph = new DirectedGraph();

graph.addVertex("Hello");
graph.addVertex("Hi");

graph.addEdge("Hello", "Hi");

graph.deleteVertex("Hello");

console.log(graph.incomingEdgesOf("Hi"));

Expected behavior Deleting a vertex results in all associated edges being deleted from all sides.

zrwusa commented 8 months ago

Because of our oversight, we did not remove edges with incoming adjacency nodes when deleting a node. This bug has been fixed in version 1.49.4.