I feel quite slow in the understanding of graph representations. So, please, I'd like you to verify that I did understand, at least, the Adjacency List correctly.
So here I'm trying to implement unweighted graph, that supports parallel edges. Whether graph is directed or not, I don't understand how that might affect an implementation, as I will still add edges by pair (start, end) in any case.
-- Update:
To be more specific, I'd like to get a review, of possible problems that my implementation might have, eg:
1) extra operations
2) extra memory
3) incorrect data structure
... and so on, thank you.
--
Here is my code in JavaScript:
1) data format. Below, in the implementation, you'll see a util formatDataToAdjacencyList
. Just assume that it returns such shape of the data (from tests):
const result = formatDataToAdjacencyList(data)
expect(result).toEqual({
edges: [
['0', '4'],
['1', '2'],
['1', '3'],
['1', '4'],
['2', '3'],
['3', '4'],
['3', '3'],
['0', '1'],
['1', '2'],
['2', '0'],
],
vertices: [
'0',
'4',
'1',
'2',
'3',
]
})
2) implementation
function GraphAdjacencyList(data) {
if (data) {
const formattedData = formatDataToAdjacencyList(data)
this.adjacencyList = formattedData.edges
this.vertices = formattedData.vertices
} else {
this.adjacencyList = []
this.vertices = []
}
}
GraphAdjacencyList.prototype.addVertex = function(nodeLabel) {
if (this.vertices.indexOf(nodeLabel) !== -1) {
throw new Error('vertex already exist')
}
this.vertices.push(nodeLabel)
}
GraphAdjacencyList.prototype.removeVertex = function(nodeLabel) {
const index = this.vertices.indexOf(nodeLabel);
if (index === -1) {
throw new Error('vertex not found')
}
this.vertices.splice(index, 1)
}
GraphAdjacencyList.prototype.addEdge = function(startLabel, endLabel) {
this.adjacencyList.push([startLabel, endLabel])
}
GraphAdjacencyList.prototype.removeEdge = function(inputStartLabel, inputEndLabel) {
const index = this.adjacencyList.findIndex(([startLabel, endLabel]) => {
return startLabel === inputStartLabel || endLabel === inputEndLabel
})
if (index === -1) {
throw new Error('edge doesn\'t exist')
}
this.adjacencyList.splice(index, 1)
}
```