Graph edgeSize is not always correct

[maloku]

I think there is a Bug by decreasing edgeSize after removing multiple nodes at the same time. edgeCount of nodes has incorrect value after deleting a neighbor node.

The following test fails:

describe "Another tricky test -- ",->
  it "edgeSize after adding and removing nodes",->
    graph = new Graph();
    expect(graph.addNode "1").toBeDefined()
    expect(graph.addNode "2").toBeDefined()
    expect(graph.addNode "3").toBeDefined()
    expect(graph.addNode "4").toBeDefined()
    expect(graph.addNode "5").toBeDefined()
    expect(graph.addEdge "1", "2").toBeDefined()
    expect(graph.addEdge "2", "4").toBeDefined()
    expect(graph.addEdge "2", "3").toBeDefined()
    expect(graph.addEdge "2", "5").toBeDefined()
    expect(graph.addEdge "5", "4").toBeDefined()
    expect(graph.addEdge "1", "3").toBeDefined()
    ###
    1 -> 2 ->  4
     \   | \   ^
      \  |  \  |
       ˅ ˅   ˅ |
         3     5
    ###

    expect(graph.removeNode "2").toBeDefined()
    expect(graph.removeNode "1").toBeDefined()
    ###
          4
          ^
          |
          |
    3     5
    ###
    expect(graph.edgeSize).toBe 1 ## Bug edgeSize = 0
    expect(graph.nodeSize).toBe 3

[chenglou]

Argh, thanks a lot, you've discovered a conceptual bug here. I was striving to make removeNode O(1) amortized, but finally it's too cumbersome to implement for no practical benefit. Switched it back to traditional O(E).
The upside is that the code's much cleaner.

It's on npm now!