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 typically called Vertices, with relationships in between them called Edges. This data structure can be very useful in applications where the relationships between the data bears importance similar to the data that is being stored. Using the Edges between the Vertices, information can be mathematically conveyed.
For example, you might have heard of Graphs in the past in the context of Graph Theory, which is the study of graphs for finding mathematical relationships between objects. A concept in Graph Theory is a Path, which simply refers to the series of edges that connect two Vertices. Simply understanding the path between vertices can provide information on the data such as finding which vertices are the most and least interconnected.
This type of information can be very useful for data analysts, software developers, and even enterprise applications. For example, a Graph is commonly used for the flights at an airline, where the Vertices represent different locations, and edges represent an available flight between them.
This article can be improved by: All images on this page would be easier to read if the text showed up better in their boxes. The black text doesn't offer enough visual contrast with the dark gray box.
Graphs can also be used for social networking applications, where a Vertex is a user and an edge is a relationship between them.
You can imagine that in either of these scenarios, understanding the inter-connectedness of a Vertex can provide important insights, such as finding cities with more air traffic or users with the strongest business connections. That is only one value that you can derive from one feature of a graph. With the concepts of Weight, Direction, and Path, graphs prove to be one of the most dynamic and insightful forms of storing data.
Looking at these graphs, you might also notice that they are in many ways similar to a Linked List because the underlying concept is the same: many nodes of data with pointers in between that data. The main difference is that Graphs are rarely, if ever, linear in nature. Now with that, we'll take closer look at how Graphs work and how to implement one in Swift.
Adjacency[edit]
First, let's understand Adjacency, a term commonly used when discussing Graphs. Adjacency in a graph essentially means a vertex has an edge connecting it to another vertex. In the following diagram, A is adjacent to B, B is adjacent to A and C, but A is not adjacent to C because no edge directly connects these two.
Now, from the idea of Adjacency, we can make an Adjacency List. Each Vertex will have an Adjacency List that describes every Vertex that is adjacent to the given vertex. In other words, you can make an Adjacency List by looking at each vertex and documenting all the vertices it shares an edge directly with. 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 are critical for implementing the code to build our Graph later on.
Quiz[edit]
Types of Edges[edit]
Now, let's take a closer look at Edges. Graphs can have specialized edges for different use cases. Specifically, there can be Weighted Edges, where the edges are given greater emphasis by assigning a numerical value to the edge giving it weight. This way, you can look at an edge that has the highest value of 10 and look at an edge that has a lowest value of 1 and be able to interpret a difference in the importance of the relationship between the respective vertices.
Let's look at the social networking and airline examples again. If two users are friends, this relationship can be represented by a max weight on the edge, such as the number 1, we can have the weight be the number 2 between two users who are connected only by a mutual friend. We can use this principle to implement the sort of Connection functionality that popular apps such as LinkedIn uses, where the app shows if the user is a 1st, 2nd, or 3rd-level connection. We can also assign values to the edges of an airline graph to represent the cost of a flight.
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:
You can implement this concept in code by having a "From:" and a "To:" or a "Source:" and a "Destination:" when describing the Adjacency Lists. This is explored more in the next section. Note: If an edge does not have a direction, it's usually implied that it is bi-directional, such as a mutual connection on a social network or an airline that flies airplanes both to and from a certain location.
Quiz[edit]
Making a Graph[edit]
As mentioned, Graphs are made of Vertices and Edges. So, let's start by making some basic classes to handle a Vertex and an Edge. For this example, we'll keep things simple, but keep in mind that you can implement graphs in many ways. You should challenge yourself to learn other implementations.
public class Vertex{
var data: String?
var adjacencyList: Array<Edge>
init() {
self.adjacencyList = Array<Edge>()
}
}
Notice that each Vertex needs to hold an Array listing all the Edges it is adjacent with. This is one of the many ways of implementing adjacency lists.
We'll also include the following function to get the data stored in the vertex class.
func getData() -> String{
return data!
}
public class Edge{
var weight: Int
var to: Vertex
var from: Vertex
init(){
weight = 0
self.to = Vertex()
self.from = Vertex()
}
}
Here, we'll implement both direction and weight by having properties for them in each Edge. Now, all we need to do is make a Graph class that has some basic functions to let us interact with these classes.
public class Graph{
func addVertex(data: String) -> Vertex {
let newVertex: Vertex = Vertex()
newVertex.data = data
return newVertex
}
func addEdge(from: Vertex, to: Vertex, weight: Int){
let newEdge = Edge()
newEdge.to = to
newEdge.weight = weight
from.adjacencyList.append(newEdge)
}
}
Now we have two functions. One to add a Vertex and one to add an Edge in between two vertexes. We simply make a new vertex and assign the data value to the given value and the same is true of the Edge. Now, we can test this mini graph.
let socialNetwork = Graph()
let user1 = socialNetwork.addVertex(data:"Tiffany")
let user2 = socialNetwork.addVertex(data:"Connor")
socialNetwork.addEdge(from: user1, to: user2, weight: 10)
socialNetwork.addEdge(from: user2, to: user1, weight: 10)
print(user1.getData())
print(user2.getData())
Here we set up two users and put an edge in between them, then print out each user to make sure the scripts work. This remains a somewhat crude example; however, it has the basic features of a graph. As a bonus challenge, you can try to print out the adjacency lists of a user as a String. Think of the additional functions and refactoring you might need.
Quiz[edit]
Key Concepts[edit]
- Graphs are a data structure meant to show relationships between data using Vertices and Edges
- A Graph can be described by using Adjacency Lists, which is a list of all the Vertices a Vertex is connected to
- The weight on edge can show the relative importance of the relationship between two Vertices
- An Edge can also have direction (From: A To: B) to better describe the relationship between Vertices