skip to Main Content

I’m trying to implement a removeVertex solution for a graph data structure.
Depending on the removeEdge method I use in the class, the result varies and a vertex may or may not get looped over.
I’m trying to understand why that is the case

Base Class and removeVertex method

class Graph {
  constructor(value) {
    this.adjacencyList = { ...value }
  }

  removeVertex(vertex) {
    let vertexEdges = this.adjacencyList[vertex]
    for (let item of vertexEdges) {
      console.log(item)
      this.removeEdge(item, vertex)
    }
    delete this.adjacencyList[vertex]
  }
}

Instantiating the class

const g = new Graph({
  Tokyo: ['Dallas', 'Hong Kong'],
  Dallas: ['Tokyo', 'Aspen', 'Hong Kong', 'Los Angeles'],
  Aspen: ['Dallas'],
  'Hong Kong': ['Tokyo', 'Dallas', 'Los Angeles'],
  'Los Angeles': ['Hong Kong', 'Dallas'],
})

When this verison of removeEdge method is used

  removeEdge(v1, v2) {
    let v1removeIndex = this.adjacencyList[v1].indexOf(v2)
    let v2removeIndex = this.adjacencyList[v2].indexOf(v1)
    if (v1removeIndex !== -1) {
      this.adjacencyList[v1].splice(v1removeIndex, 1)
    }
    if (v2removeIndex !== -1) {
      this.adjacencyList[v2].splice(v2removeIndex, 1)
    }
  }

Result is this:

 Graph {
  adjacencyList: {
    Tokyo: [ 'Dallas' ],
    Dallas: [ 'Tokyo', 'Aspen', **'Hong Kong'**, 'Los Angeles' ],
    Aspen: [ 'Dallas' ],
    'Los Angeles': [ 'Dallas' ]
  }
}

When this version of removeEdge method is used

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    )
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    )
  }

The Result is this:

 Graph {
  adjacencyList: {
    Tokyo: [ 'Dallas' ],
    Dallas: [ 'Tokyo', 'Aspen', 'Los Angeles' ],
    Aspen: [ 'Dallas' ],
    'Los Angeles': [ 'Dallas' ]
  }
}

Notice the absence of "Hong Kong" in Dallas using the removeEdge method with array.filter?
If the "Hong Kong" key is not deleted, the removeEdge method with array.splice will produce the following result

 Graph {
  adjacencyList: {
    Tokyo: [ 'Dallas' ],
    Dallas: [ 'Tokyo', 'Aspen', 'Hong Kong', 'Los Angeles' ],
    Aspen: [ 'Dallas' ],
**    'Hong Kong': [ 'Dallas' ],**
    'Los Angeles': [ 'Dallas' ]
  }
}

Clearly "Dallas" is not looped over for some reason and I am not able to understand why. Could someone please explain?

2

Answers


  1. Chosen as BEST ANSWER

    I theorize array.splice changes the underlying array so the for loop skips the first item thinking it was already looped over. However, if someone can confirm or explain better if this is the case it would really help with my understanding


  2. The indices will change after you splice the array so after the first splice the v2RemoveIndex is no longer valid as it may now be off by one in case it was larger than v1RemoveIndex before. (Also, you mixed up v2 and v1 in indexOf)

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search