W3150 Graphs
Overview[edit]
In Computer Science, Graphs refer to a Data Structure meant to store Data involving Nodes and their relationships. Specifically, a Graph is made of several points called Vertices with relationships in between them called Edges. Additionally, Graphs are involved in Graph Theory involving Paths. Paths simply refer to the series of Vertices that need to be taken between two given Vertices. A common example is the flights at an Airline where the Vertices represent different locations and edges represent an available flight between them. [insert image here] Graphs can also be used for social networking applications where a Vertex is a user and an edge is a relationship between them. [insert image here] If you're already familiar with Linked Lists, Graphs will be rather familiar as they're simpler versions of Graphs. In the following, we'll take a deep dive on how Graphs work as well as how to implement one using Swift.
Adjacency[edit]
First, let's understand Adjacency. This term is commonly used when discussing Graphs. Adjacency in A graph essentially means what vertices are adjacent to each other, or have an edge connecting them. In the following Diagram, A is adjacent to B, B is adjacent to A and C, but A is not Adjacent to C since there is not an edge that directly connects these two.
From the idea of Adjacency, we can make an Adjacency List. Each Vertex will have an Adjacency List which describes every Vertex that is adjacent to the given vertex. The Adjacency Lists combined with a List of all the vertices can essentially describe a Graph. Here is a visual representation of the Adjacency Lists for every Vertex in the Social networking example.
Adjacency Lists will be critical for implementing the code to build our Graph.
Types of Edges[edit]
Graphs can also have specialized edges for different use cases. Specifically, their can be weighted edges. Where the edges are given greater emphasis. Let's look at the Social Networking example again, if two users are friends, this relationship can be represented by a max weight on the edge, such as the number 1, then we can have the weight be the number 2 between two users who are connected only by a mutual friend. This principle could be used to implement the sort of Connection functionality that popular apps such as LinkedIn uses, where the app shows if the user is 1st, 2nd, or 3rd connection.
Beyond the concept of Weight, edges can also have direction. For instance, perhaps user A is subscribed to user B, but user B is not subscribed to user A. This can be stored in the graph via direction and would be visualized with an image such as the following. When implementing this concept with code, this can be accomplished by having a "From:" and a "To:" or a "Source:" and a "Destination:" when describing the Adjacency Lists. If an edge does not have a direction, it usually means it is "bi-directional," such as a Mutual connection on a social network or an Airline that flies Airplanes to and from a certain location.
