A Node of Truth For Making Graphs

December 14th 2020 new story

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

Dan Abramov

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

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

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

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

CRUD

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