JavaScript Graph Data Structure

Kyle Shevlin
InstructorKyle Shevlin

Share this video with your friends

Send Tweet
Published 4 years ago
Updated a year ago

A graph is a data structure comprised of a set of nodes, also known as vertices, and a set of edges. Each node in a graph may point to any other node in the graph. This is very useful for things like describing networks, creating related nonhierarchical data, and as we will see in the lesson, describing the relationships within one's family.

Instructor: [00:00] A graph is a collection made up of nodes, also known as vertices, that may or may not be connected to other nodes. These connections are called edges. To build our graph, we're going to start by creating our node factory function.

[00:16] When we create a node, we need to give it a value that we can use to identify it. We'll call it a key. We'll describe adjacent nodes in our graph as neighbors, as there is no hierarchy implied by the data structure.

[00:29] Lastly, we need a way to add neighbors to our node, so we'll add an addNeighbor method that pushes a node into our neighbors array.

[00:37] Now we can create our graph factory function. createGraph receives an argument, directed. A directed graph's edges point in one particular direction, from one node to another. In order for two nodes to have symmetric edges, they must both point to each other.

[00:54] In an undirected graph, we assume the symmetry of edges. We'll set directed to false by default. We'll return it in the object created by our factory function.

[01:06] A graph is a collection of nodes and a collection of edges, so we'll create arrays for both of them in closure. We'll pass these references to our returned object as well.

[01:17] Now we'll start adding methods to our graph. The first will be the addNode method. addNode receives a key as an argument and uses our createNode function to add a node to the nodes array.

[01:30] We also want to be able to get nodes from our graph. We'll add a getNode method. getNode will search for a matching key and return the first one. We'll use array's find method to accomplish this.

[01:43] Next, we need to be able to add edges between nodes. We'll create an addEdge method. addEdge receives two arguments, a key for the first node and a key for the second node. We'll use our getNode method to get those two nodes.

[01:59] We then will add Node 2 as a neighbor to Node 1. This happens regardless of whether the graph is directed or undirected. The same goes for pushing our edge into the edges array. We'll simply pass a string of our two keys, adding a delimiter between them.

[02:18] If the graph is undirected, we also want to add Node 1 as a neighbor of Node 2. We're not going to worry about adding a second edge because we don't want the number of edges in our graph to be misrepresented. If we were to add an edge here, we'd have to implement a way of resolving both edges as one were we ever to count them and provide an edge's length property.

[02:41] Now that we can add nodes and edges, we'd probably like to be able to visualize our graph. We'll create a print method that will print out our nodes and neighbors in the console. We want to return a string derived from our nodes. I'm going to map over our nodes, gather some data about them, and return a result.

[03:01] We'll start by destructuring the key and neighbors from each node. The string we're going to return will always start with the key. If there are any neighbors, we want to map over each one of them and concatenate that neighbor's key into our result.

[03:19] Once that's done, we can return the result. We'll call a join with a new line on our array of strings. Now we can create a graph and try it out. I'm going to create a directed graph of the Shevlin family -- me, my wife, and our two cats, Krios and Tali. This graph will describe who loves whom in this household.

[03:43] My wife and I love each other very much. We can add an edge between us going in both directions. We love our cats, her a tad more than me. I'm more of a dog person. We have no way of weighting our edges in this graph. Instead, we'll just add edges from me to both our cats and from Anna to both our cats.

[04:03] Next, our cats have very little love for each other. They tolerate one another, but they do fight from time to time. We won't put any edges there.

[04:11] Krios does love Anna. Tali shows some affection towards me. We'll add edges there. Now if we call the print method on our graph and run it in the terminal, we should see a printout of my family's relationships.

tsvika
tsvika
~ 3 years ago

Why don't you use es6 classes?

tsvika
tsvika
~ 3 years ago

Why don't you use es6 classes?

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

No reason. Just wanted to use factory functions. Use what sparks joy 😁.

Marwan
Marwan
~ 3 years ago

I really enjoy your videos, they're unique in the sort of things you present. Most, if not all, videos i've seen talk about the same thing one way or another. This is like crossing dimensions. Thank you

Christopher Ueda
Christopher Ueda
~ 3 years ago

Really enjoyed this lesson. I didn't know what a graph was until now! I did notice a discrepancy between the use of addChildren and addNeighbor functions in both the video, the codesandbox and the transcription. I usually watch the video once then go through the transcription a second time to make sure I understood everything. It would be nice if we could do a pull request to fix up any issues we find with the transcriptions. Thanks!

jen chan
jen chan
~ 3 years ago

Same, never heard of a graph in JS and also had to rewatch the part describing directed and undirected graphs. I got it with the example though.

Marcell Ciszek
Marcell Ciszek
~ 2 years ago

Awesome course Kyle! I really like that you using functions

luca leone
luca leone
~ a year ago

Kyle, in the transcript section, in the addEdge method definition, I think node2.addChild(node1) should be node2.addNeighbor(node1).

luca leone
luca leone
~ a year ago

...also, in the print definition, children should be neighbors

Lucas Minter
Lucas Minter
~ a year ago

Kyle, in the transcript section, in the addEdge method definition, I think node2.addChild(node1) should be node2.addNeighbor(node1).

You are correct Luca! I've gone ahead and gotten those fixed in the transcripts. Thank you for bringing this to our attention.