You've successfully subscribed to developer.school
Great! Next, complete checkout for full access to developer.school
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Intro to Graphs - Adjacency Matrices and Lists

Get a birds-eye-view of the most common and useful data structures out there, graphs.

Dynamis Development
Dynamis Development

With data structures like trees we had a very clear cut order and direction to our nodes and edges, but with graphs we get to throw away the rule-book and embrace the chaos of the more flexible structure that most of our databases and networks are based on.

What's a Graph?


Graphs allow us to create a set of far more flexible and meaningful connections between data. They have two properties that allow us to do some very cool things, weight and direction.

A graph can either be use unidirectional or bidirectional edges. Facebook is based on bidirectional connections, if you're friends with someone then you both get each other's posts in your feeds. Twitter, on the other hand, is unidirectional, just because you follow Alligator.io doesn't mean they can see your posts unless if they follow you back.

A graph can also be weighted or unweighted, meaning an edge can have a value representing the strength of the connection. Let's say you have two friends, one that posts often and the other you interact with a lot through comments, likes, et cetera. With a weighted graph we could count those interactions with each person, average them out, and use that value to structure your feed with a good mix of new content and content you're more likely to enjoy.

Likewise, if we have a system like google maps we don't just want the shortest distance but we need to take into account the direction of roads and take the one with the least traffic and highest speeds.


Adjacency Matrix


There are two main methods for creating graphs, an adjacency matrix and an adjacency list, both have their own pros and cons.
An adjacency matrix is just a grid comparing every node to every other nodes, where they intersect is the weight for that connection, or in unweighted graphs just a 1 or 0.


An adjacency matrix is better for graphs that are dense with many connections between nodes, but come with the drawback of needing O(n^2) space. Every time you create a new vertice you also need a new row with a place for every vertice. Where an adjacency matrix lacks speed in creating and destroying vertices, it excels at reading and updating entries.

Imagine if you're creating a navigation system for the bus routes of a city. Most stops are connected to most other stop in some way, being able to put a weight on each route could be better done with a matrix. Since it's also more static, since you'll rarely be creating or destroying roads, slow row management isn't a problem but read and update speeds are essential.

Adjacency List


An adjacency list is a much more familiar and common approach. We have hash map, an object in JS, where each value has an array of pointers to the vertice they're connected to.

This is better for something like Wikipedia, where most entries are not going to be connected to even a percentage of the other entries. This is generally the more common technique for what we imagine graphs being used for, like social media.

Adjacency Matrix

Since an adjacency matrix is a row for each vertice, and each row has as many items as the number of vertices, then we'll need a way of creating those arrays and tracking the indexes for each stop. We'll do this by storing the entries in matrix and copying the values into the vertices array, to keep track of their position.

Every time we add a stop we need to add a new key with and array of zeros with the length of vertices. Just push our new item onto our array and loop over the previous items to add a column for the new stop and we're done.

class Matrix {
    constructor() {
        this.matrix = {}
        this.vertices = []
    }
    addStop(stop){
        this.matrix[stop] = Array.from({length: this.vertices.length + 1}, () => 0);
        this.vertices.push(stop)
        this.vertices.forEach(item => {
            if(this.matrix[item].length < this.vertices.length) this.matrix[item].push(0)
        });
    }
}

const matrix = new Matrix()
matrix.addStop('Caiman Ave')
matrix.addStop('Gator Blvd')
matrix.addStop('Crocodile St')

// "Caiman Ave": [0, 0, 0]
// "Crocodile St": [0, 0, 0]
// "Gator Blvd": [0, 0, 0]
console.log(matrix)

Creating an entry is even easier, after we get the indexes of the items we're looking to connect we can use double brackets , [][], to select the right item in the matrix then the right position in its array and set it to our weight. We're making a bidirectional graph so we'll have to do this with both vertices.

addRoute(v1, v2, traffic) {
    if(v1 == v2) return 'Stop cannot refer to itself'
    let indexV1 = this.vertices.indexOf(v1)
    let indexV2 = this.vertices.indexOf(v2)
    this.matrix[v1][indexV2] = traffic
    this.matrix[v2][indexV1] = traffic
}
matrix.addRoute('Caiman Ave', 'Gator Blvd', 5)
matrix.addRoute('Gator Blvd', 'Crocodile St', 9)
matrix.addRoute('Caiman Ave', 'Crocodile St', 4)

// "Caiman Ave": [0, 5, 4]
// "Crocodile St": [4, 9, 0]
// "Gator Blvd": [5, 0, 9]
console.log(matrix)

To remove a stop isn't as simple as deleting its key, we also need to remove every place and reference to it in other entries. For every item we want to splice out the entry with our stops index. After we remove it from the vertices we can delete the key itself.

removeStop(stop) {
    let routeIndex = this.vertices.indexOf(stop);

    this.vertices.forEach(vertice => {
        this.matrix[vertice].splice(routeIndex, 1);
    });

    this.vertices.splice(routeIndex, 1);
    delete this.matrix[stop];
}

matrix.removeStop('Gator Blvd');

// "Caiman Ave": [0, 4]
// "Crocodile St": [4, 0]
console.log(matrix);

Being able to store a bunch of routes doesn't do any good if you can't get any of them. For every entry on our vertice we want to get both the stop at that index and the weight, which we can just throw into a object in our stops array.

getRoutes(stop) {
    const stops = []

    this.matrix[stop].forEach((weight, i) => {
        if(weight > 0) {
            let vertice = this.vertices[i]
            stops.push({
                stop: vertice,
                traffic: weight
            });
        };
    });

    return stops
}

// { stop: "Gator Blvd", traffic: 5 }
// { stop: "Crocodile St", traffic: 4 }
console.log(matrix.getRoutes('Caiman Ave'))

Adjacency List

An adjacency list is a much simpler and more intuitive way of creating a graph, since we only have to account for exactly what we need.  

Adding and connecting users is really as simple as creating a key with an object and pushing the pointers and weights of each onto each user. We'll be referencing the names but in an production app you'd be using actual IDs.

class Graph {
    constructor() {
        this.users = {}
    }
    addUser(user){
        if(!this.users[user]) this.users[user] = []
        else throw new Error(`${user} already exists`)
    }
    addFriend(v1, v2, weight){
        if(!this.users[v1] || !this.users[v2]) throw new Error('User not found')
            
        this.users[v1].push({v: v2, w: weight})
        this.users[v2].push({v: v1, w: weight})
    }
}

const graph = new Graph()
graph.addUser('Josh')
graph.addUser('Seb')
graph.addUser('Will')
graph.addFriend('Josh', 'Will', 5)
graph.addFriend('Seb', 'Will', 1)
graph.addFriend('Seb', 'Josh', 6)
console.log(graph)


To break a connection we need to go to each user and filter out the references to the other. To remove a user and all of their connections, we can use removeFriend on the last item in its array and keep doing that until there aren't any friends left. Then delete the that users key from the list.

removeFriend(v1, v2) {
    if(!this.users[v1] || !this.users[v2]) throw new Error('User not found')

    this.users[v1] = this.users[v1].filter(v => v !== v2.v)
    this.users[v2.v] = this.users[v2.v].filter(v => v.v !== v1)
}
removeUser(user) {
    if(!this.users[user]) throw new Error('User not found')

    while(this.users[user].length) {
        const end = this.users[user].pop()
        this.removeFriend(user, end)
    };

    delete this.users[user]
}

graph.removeFriend('Will')
console.log(graph)


Getting all of a users friends is pretty trivial, just loop collect and return them in an array.

getFriends(user) {
    const friends = []
    this.users[user].forEach(friend => friends.push(friend.v))
    return friends
}

Closing Thoughts

Of course, the exact implementation can differ greatly depending on your particular project. This was more of a crash course on the concept of graphs rather than an exact procedure that needs to be memorized and studied.

Dynamis Development

Tutorials, articles, and a love for React and memes. Articles - http://alligator.io/author/joshua board Channel - http://tinyurl.com/yb4h7quu Reddit - r/DynamisDevelopment