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

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.

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.