Representation graph as Adjacency List in JavaScript

Question

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)
}
```

• t3chb0t: But what does it do? What is this code for? Does it solve any problem? It's difficult to review something without context.
• Undefitied: it represents a graph
• dfhwze: You only provide methods to add arcs to the graph, not to traverse the graph or perform lookup. And your test shows us expected results, but no input date. The question can not be properly reviewed lacking all this context. Could you include more code to make this a graph and example code?
• Undefitied: I'd like to know that I do understand the pattern of graph representation correctly. I don't have any issues with incorrectly working code, I think I might have an issue with the representation of the idea of how graphs should be implemented.
• dfhwze: I find your comment confusing. You know how a graph works but don't know how to represent it. In which context would you like to represent it, can you give a non-trivial example?

Answer 1

Strictly speaking, the list of vertices is not neccessary because the adjacency list already contains all (connected) vertices and disconnected ones can be represented as [x, null]. If you prefer to keep vertices, you'll have to synchronize them with edges:

• in removeVertex you not only remove the vertex but also all edges connected to it
• in addEdge you add input labels to the vertices list, if not already there (which makes one think that vertices should be a Set)

Minor notes:

In general, as of 2018, it's cleaner to use the class syntax to define classes.

In removeEdge you'd probably want &&, not ||: return startLabel === inputStartLabel && endLabel === inputEndLabel. If the graph is undirected, you also have to check for reversed edges (start == inputEnd && end == inputStart)

You didn't share the input data format and formatDataToAdjacencyList, but anyways, it would look better as a class member, not as an extra function.

• Undefitied: thank you for the answer. If I don't store vertices, does that mean that to get the list of vertices, for example, to iterate through it, I'll need to do O(n+m) loop to get all the vertices? And removeEdge is a good catch, thank you.
• georg: @Undefitied: yes, that would be the price for not having to synchronize them.
• Undefitied: I see, nice to have this part clear. And what do you think about data format, am I using the correct structure for adjacency list?
• georg: @Undefitied: there's no "best" or "correct" data structure. It all depends on the type of the graph and what the most frequent operation (build vs query) is. The list of pairs, which you're using, has an advantage of being simple to program.

Answer 2

edges: [
 ['0', '4'],
 ['1', '2'],
 ['1', '3'],
 ['1', '4'],
 ['2', '3'],
 ['3', '4'],
 ['3', '3'],
 ['0', '1'],
 ['1', '2'],
 ['2', '0'],
]

is not an adjacency list representation. That would be

edges: {
 '0': ['1', '4'],
 '1': ['2', '2', '3', '4'],
 '2': ['0', '3'],
 '3': ['4', '3'],
 '4': []
}

vertices is unnecessary, because the keys of edges give you the vertices.

• Undefitied: Thank you for the response, @PeterTaylor. I was thinking the same as you say before I've got an answer on StackOverflow about it: stackoverflow.com/questions/57645065/… . The guy there says, such structure is adjacency matrix and not the list.
• Peter Taylor: @Undefitied, no, that's wrong too. An adjacency matrix would be [[0, 1, 0, 0, 1], [0, 0, 2, 1, 1], [1, 0, 0, 1, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0]].
• Undefitied: Then, do you think we can go further and replace the second level array with an object? So it would be edges: { '0': { '1': 1, '4': 1 }, '1': { '2': 2, '3': 1, '4': 1 } }.
• Peter Taylor: Sure. It's at least as good as an adjacency list in everything except memory usage, where it's probably a constant factor worse.