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
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
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 thanv1RemoveIndex
before. (Also, you mixed upv2
andv1
inindexOf
)