W3150 Graphs

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder


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 bares an importance similar to the data that's being stored. Using the Edges between the Vertices, information can be mathematically conveyed.

For instance, you may 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 given Vertices. Simply understanding the path between vertices can provide information on the data such as finding which vertices are the most and least inter-connected.

This type of information can be very useful for data analysts, software developers, and even enterprise applications. For instance, a common example of Graph usage is the flights at an Airline where the Vertices represent different locations and edges represent an available flight between them.

Graph Basic Airline.png

Graphs can also be used for social networking applications where a Vertex is a user and an edge is a relationship between them.

Graph Basic Social-networking.png

You can imagine that in either of these scenarios, understanding the inter-connectedness of a given Vertex can provide important insights. such as finding cities with greater air traffic or users with the strongest business connections, and that's only one value that can be derived 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 since the underlying concept is the same: many nodes of data with pointers in between that data. The main difference is Graphs are rarely, if ever, linear in nature. Now with that, 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, a term commonly used when discussing Graphs. Adjacency in a graph essentially means if 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 since there is not an edge that directly connects these two.

Adjacency Diagram.png

Now, 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. In other words, you can make an Adjacency List by looking at each individual vertex and documenting all of 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.

Examine the Graph! Look at a Name and see all the names that are connected to it. See how this lines up with that Name's adjacency list!

Adjacency Lists will be critical for implementing the code to build our Graph later on.

Quiz[edit]

1 What is the meaning of Adjacency?

If two Vertices are connected directly with an Edge, they are Adjacent
If two Vertices are together in the same Graph, they are adjacent
If a Vertex is positioned Graphically to be next to another Vertex (but no edge connecting them directly) they are adjacent
Adjacency refers to the edges that lie in between two given Vertices

2 What is an Adjacency List?

Adjacency Lists are simply lists of every Vertex in a given graph
An Adjacency List is a list given to each Vertex that describes which Vertices are Adjacent to the given Vertex
An Adjacency List is a list associated with each Vertex that list the shortest paths to each and every other Vertex present on the graph
An Adjacency List is a single list that exists with the graph that describes the relative importance of the relationships between each vertex

3 True or False: In a Graph, a Vertex must have an Edge that connects it to another Vertex

True
False

4 True or False: In a Graph, a Vertex must have an Edge that connects it to another Vertex

True
False

5 True or False: Every Vertex has a list of Vertices that the Vertex is connected to, called an Adjacency List

True
False


Types of Edges[edit]

Now, let's take a deeper look at Edges. Graphs can have specialized edges for different use cases. Specifically, their 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, 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 a 1st, 2nd, or 3rd connection. We can also assign values to the edges of an Airline graph to represent the cost of a certain flight.

Weighted Airline Graph.png

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.

Directional Edges Graph.png

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 will be 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]

1 How can Edges provide deeper information for a Graph?

Edges can be assigned numerical values and direction to provide insights as to the direction and importance of a relationship
Edges can point to multiple different Vertices in a Graph to provide greater insight on relationships
Edges can only provide information by demonstrating that there is a connection between two Vertices but the Vertices contain all the information
Edges can be assigned direction but all edges will always have the same weight of importance

2 How can you give direction to an Edge?

Edges are given direction by assigning them to other Edges to define their source and destination
Edges are given direction by assigning them in between Vertices to define their source and destination
Edges cannot be given direction as they are meant to be bi-directional
Edges can be given direction by assigning them a numerical value to show the importance of the relationship it represents

3 True or False: Weight values go from a defined scale of 1 to 10.

True
False

4 True or False: Weight must be assigned to an Edge

True
False


Making a Graph[edit]

As was 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 as simple as we can, but keep in mind there are many ways of tackling the implementation of a graph. You should challenge yourself to learn other implementations as well.

public class Vertex{
  var data: String?
  var adjacencyList: Array<Edge>
  
  init() {
    self.adjacencyList = Array<Edge>()
  }
}

Notice that each Vertex will need to hold an Array listing all of the Edges it is adjacent with, this is one of the many ways of implementing adjacency lists.

We'll also include the following function as well 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 such 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)
      
   }        
}

Here 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 may need.

Quiz[edit]

1 True or False: There is a set way of making a Graph data structure

True
False

2 True or False: Graph Data structures must be implemented with some representation of Vertices and Edges

True
False


Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • 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 given Vertex is connected to
  • The weight on edge can show the relative importance of the relationship between two given Vertices
  • An Edge can also have direction (From: A To: B) to better describe the relationship between Vertices
CoderMerlin™ proudly recommends: