Day 84 is in the books. I’ve got to tell you that things are straight up crazy at this point in the program. We’re three weeks away from graduation and the mad dash to tie up any loose ends is officially underway. We’ve got to wrap up assignments on linked lists, trees, graphs, unfamiliar environments (Swift), portfolio sites, and oh ya our capstone projects! The struggle is real as the millennials (guilty) say.
Graphs
Today we were introduced to graphs by a guest instructor. Graphs are the land of crazy. They are basically like trees with fewer restrictions. In a graph a node can point to any node that it wants regardless of direction. Graph nodes can also be loners and not point to any other nodes. As you might imagine this makes traversing a graph data structure much more difficult. Graphs typically store a list of all the nodes in the graph and a list of all of the edges in the graph. A node in javascript is just an object with a value property. An edge is the thing that connects two nodes and it’s also an object that has first, second, and weight properties. The first and second properties are just nodes that represent the nodes that this edge connects. The weight property is a way of declaring the “cost” of traveling along this edge. The weight property allows us to maintain some sanity when trying to, for example, find the shortest path between two nodes.
There are so many cool things that you can do to manipulate, traverse, and search these different types of data structures. Here’s an example of something we did in class today. Our task was to find all of the neighbors of a specific node. Let’s walk through the example below to give you a feel for what we’re working with. First let me lay the foundation for this problem. Below I will provide some context for some of the things that I will be using to solve this problem.
- this.findNeighbors is a method on a graph object. A method is just a function that is defined as an object property. this refers to the graph object that this method is being added to.
- value is the search value that is being passed in when the findNeighbors method is invoked.
- this.edges is the list of edges that is defined on this graph object. This is the list (array) that we are going to be working with to find the neighboring nodes.
- The rest is ES6 magic that I will explain as we go through.
On the left hand side of the = sign on line 59 we are adding our findNeighbors property. On the right hand side of the = sign we our defining our method/function. It may look a little funny if you’re not used to ES6. ES6 allows you to do arrow functions which means that you can do away with some of the overhead for declaring functions under certain conditions. In this case our function/method only accepts one argument so we were able to omit the parenthesis around the argument “value”. The arrow means that we are going to return whatever follows the arrow. ES6 states that if you are returning on the “same line” you can omit the return keyword as well as the curly brackets that you typically see. I decided to put the filter method and the map method on their own lines, but the interpreter still considers this as one line, because we are chaining these methods together. It’s just a little easier to read this way. this.edges is the list that we are going to do some work with. The first order of business is to grab only the edges that contain our search value. Javascript has a built in method called filter that is perfect for this. Filter is an array method and since this.edges is an array we are able to chain our filter method right onto it like so:
The filter method accepts a callback function as a parameter and that callback function accepts an element as an argument. That element will end up representing each item in our list. The callback function also needs to provide us with a test condition. Only the items in our array that pass this condition will get to proceed to the next step in the process. Filter will eventually return an array of our filtered results. In the example above “e” represents each element in our this.edges array. Each one of those elements has a first & second property. Those property are just objects/nodes that have a value property. So “e” represents each element and then the arrow indicates that we are going to return something. The items that we are returning are the ones that pass our test condition. Our test condition implements a logical “or” operator. That operator states that if the condition on either side of it evaluates to true then the whole statement will be considered true. That works perfectly with our filter method because it will only return something that evaluates to true. So in this case we check to see if the node that lives at e.first or the node that lives at e.second has a value that matches our search criteria. If either of those edges passes the test it will be added to our filtered array. At this point we have an array that contains all of the edges that contain our search criteria. However our task was to return an array of the neighboring values not the entire edge objects so we still have some work to do. We need to turn an array of one thing into an array of another kind of thing, and for that map is perfect!
Map is another array method and luckily filter returned an array to us so we can once again chain right onto it on line 61. Map also accepts a callback function and that callback function accepts an element. “e” will once again represent the current element in the list which is once again an edge object that contains a first & second property. We want to return a list of values that are neighbors to our search value and we know that our current list contains edges that have both our search value as well as it’s neighbors. Our job is to figure out which ones are which and return only the neighboring values. So for this we are going to use a test condition and some more ES6 goodness. Once again our arrow on line 61 states that we are ready to return something. Everything after the arrow is essentially an if/else statement. In other words if x condition is true do y otherwise do z. Only that’s boring so we are spicing it up with something called a ternary operator. The way this operation works is simple first we state our condition. In this case the condition is if e.second.value is equal to our search value. If that condition is true we return the thing after the question mark. Otherwise we return the thing on the other side of the colon. Remember that we want the neighbors. Our condition checks to see if e.second.value is equal to our search value. If it is we return e.first.value (the neighbor) otherwise we return e.second.value because that means it’s not equal to the search value which suggests that it is the neighbor.
Whew that was A LOT! If you’re still reading I’m very impressed. That’s just one of many really fun things that you can do with graph data structures and a little ES6 magic. I encourage you to experiment with both when you have a chance. You won’t be disappointed.
Tomorrow
Tomorrow and for the rest of the week we are pretty much just working on finishing up assignments and getting ready for our capstones. I’ll be working mostly on my portfolio site. I will keep you guys updated with the latest and greatest as always. Until next time…happy coding.
