W3150 Graphs

From Coder Merlin
Revision as of 06:40, 26 January 2022 by Jeff-strong (talk | contribs) (editorial review)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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 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.

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 how interconnected Vertices are 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.

Adjacency Diagram.png

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.

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 are 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 Vertices.

2 What is an Adjacency List?

Adjacency Lists are simply lists of every Vertex in a graph.
An Adjacency List is a list given to each Vertex that describes which Vertices are Adjacent to that Vertex.
An Adjacency List is a list associated with each Vertex providing the shortest paths to each and every other Vertex 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 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.

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

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 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 because 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 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 is to add a Vertex and one to add an Edge in between two vertices. 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]

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 an Adjacency List, 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