A Node of Truth For Making Graphs

When you are learning software you will have to pick and choose what. There is just too much to learn it all. So much is really cool and fulfilling but some of it is more tedious and feels like busy work. However there are things you will have to know; the fundamentals are a requirement no matter what you choose. Whether its Machine Learning and Neural Networks or Web Development and REST APIs you will need to know the fundamentals for both.

Data Structures are fairly fundamental and knowledge of them is crucial. If you are new to code, you are already working with data structures like arrays and object literals without even knowing it. As you dig deeper you will learn the costs and benefits of using different types. There is a reason why arrays are not the be all and end all of data structures.

Arrays [] are very user friendly and come with out of the box functionality. If you want to only pull out specific elements from an array? Array.prototype.filter lets you do that. JavaScript is prototypal and thus it will look on your array and not find the filter method. It will then look to it’s parent

Array prototype

where the filter method lives. Want to add an element to the start of your array? Array.prototype.unshift will let you do this too. However that will have unexpected costs. Lets think about why. What does that mean for your array in that last case? The first element is the newly unshifted element into the array, but now the second element was originally the first element. The second element was pushed into the second slot. This happens for every element in the array. Now every element has to move and it costs memory and time. It has BigO(n) time complexity, n meaning the number of elements in the array. If your array is small it is negligible but if your array is 1000s of elements it will cause time and memory issues. Lets think about fixing this issue. After all we are engineers and developers. Remembering the fundamentals, if you needed to come up with a custom data structure to solve this what would you create?

Dan Abramov

creator of Redux and boy genius(he was about 22 when he created Redux) used functions called reducers and that had switch statement logic which returned objects to create redux. That’s a pretty good hint on what to use; at the end of the day you have to use the fundamentals.

Lets create an object that will replace our Array to store information. This array will have to store data but should also be able to find the other other data we will need to store. This will mean we need a way to store the other data that is associated or connected with our data. We will create a Node class for our data structure. Classes in JavaScript are just syntactic sugar for Object factories. Our Node will have a data property where we can store the information. We are the creators of our data structure so lets add a place to store the associated or connected data.

class Node{
    constructor(id, data){  
        this.id = id
        this.data = data, 
        this.connections = [] 
    } 
    
    addConnection(id){
        this.connections.push(id)
    }
}

This is a good start but not enough for our Node class to do the job. Following the rule of

single responsibility principal

we do not want our Node doing things too far out of it's jurisdiction. We can use our Node but we will have something above the Node that will use it like building blocks to make a house. We will make new Graph class.

Graphs are very useful and are used in production commonly. This is intuitive because Software should model the real world and graphs are everywhere. A town can be a graph where buildings are Nodes and roads are the connections likewise a building has a graph like property where the Nodes are rooms and connections are the halls. We will have an Id property for each Node and we can use it like an ownership collar. This means a Node will have a

“

has and belongs to many” (a rails resource however the knowledge still applies

) relationship with other Nodes in the graph. If I own my dog I will put a collar on her. This will tell others it is my dog. Conversely my Dog has a making on her that indicates I the owner have a relationship to her. We will be able to use the ids to look up the other nodes and even see how they are associated with other Nodes. Lets code out a Graph class.

The Graph will be in charge of building new Nodes and thus we will give it a method to take data and ids to create a new Node then add them to itself.

Then we will have a method for the graph to associate Nodes into connections and edges(

in formal mathematics an edge

is a line between two points) and keep track of those relationships. We will give it a helper method to find Nodes already associated with the graph which will be used in the connector method.

We will also give it the ability to delete Nodes and lastly edit the Nodes. We will effectively make a

CRUD

Graph.

With this data structure we can store our data and also associate that data with other Nodes. We have no limitation on how many connections one node can have. This would work well for a social network.

We can find our nodes very quickly just like in arrays and unlike arrays we have no unexpected time cost to add data. We have a win win and explains why graphs are actually used in Production code. This is just one implementation to make a graph. I am by no means the authority on data structures and there are a slew of other tutorials/vlogs/videos on graphs in code.

Lets test out our graph and create a few Nodes with it and then associate those nodes. As I said we could use this to represent almost anything. Lets Create a Town then nodes will represent houses.

let town = new Graph();
town.addToGraph(100, "address 100")  
town.addToGraph(101, "address 101") 
town.addToGraph(102, "address 102") 
town.addToGraph(103, "address 103") 
town.addConnectionToNodes(101, 103) 
town.addConnectionToNodes(100,102) 
town.printGraph()

What does town.printGraph() give us?

Fair enough. just like we instructed we see House id 101 and 103 are connected and 100 and 102 are connected. Below is the full Graph class.

class Graph{
    constructor(){
        this.edges = [], 
        this.nodes = []
    } 
    addToGraph(id, data){ 
        let newNode = new Node(id, data)
        this.nodes.push(newNode)
    } 


    findNodeById(id) {
        let found = this.nodes.filter(node => {
            if (node.id === id) {
                return node
            }
        })
        return found[0]
    }
    addConnectionToNodes(node1Id, node2Id){ 
        let node1 = this.findNodeById(node1Id) 
        let node2 = this.findNodeById(node2Id)
        node1.addConnection(node2) 
        node2.addConnection(node1) 
        this.edges.push(`${node1.id} ${node2.id}`) 
        return this.edges

    }   

    editDataById(id, newData){ 
        let editMe = this.findNodeById(id) 
        editMe.data = newData 
        return "HTTP 204"
    } 
    deleteById(id){ 
     let filteredArray = this.nodes.filter(node =>( node.id !== id)) 
     this.nodes = filteredArray
      
    }
    printGraph(){ 
        console.log(this.nodes)
    }
}