Making the Graph
Previously<<here we talked about the fundamentals and how they were so important in building real worlds applications. We built a Node class in JavaScript and talked about how this could help us replace the built in data structure Array []. We also talked about the limitations of Arrays and and how we would try to overcome these obstacles.
Our Node implementation had a lot of promise but we started to implement a linked list variant. Linked Lists are great but they also have major limitations similar to Arrays. While It overcomes the inability of arrays to add to the beginning without causing havoc costing us bigO value, it is still held back by the time it takes to find data; linked Lists must be iterated through to find elements. Hypothetically if what you want is not present you would have to iterate thorough the entire list costing you bigO(n) where n is the length of the list. So lets change our Node to not have pointers to an adjacent node. Instead lets lets just have our Node have a “connections” property. We will use an array to store our connections. This makes sense like a house would know what it’s neighboring houses are and you know who your friends are. But This is just the building block of a greater data structure.
As we mentioned before Nodes are the building blocks we use to make a house. Instead of a Linked List that breaks even in time complexity with arrays (remember you can find things very quickly with arrays but you cannot add to the start without time cost) Lets make a Graph.
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 that 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 methods to take data and ids to create a Node then add them to the itself.
Then we will have a method for the graph to associate Nodes into connections and edges(in formal mathematics and 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.
