iOS, Graph Data Structure

✍️ Note

Some codes and contents are sourced from Udemy. This post is for personal notes where I summarize the original contents to grasp the key concepts (🎨 some images I draw it)

Graph

A graph is used to represent relationships between entities

Graphs are used to represent information in many many real world applications

Graphs are also favorite interview questions – They can start from simple concepts and get arbitrarily complex

Graph theory is a complex field of study by itself – There are many algorithms to optimize different problems represented using graphs

First principle of graph can solve most of the graph problems

Vertex

The entities can be anything – Graphs find applications in variety of ways in the real word

Edge

These relationships can be arbitrarily complicated and of a variety of different types

Real word Example

LinkedIn (Professional Graph)

Entities: People

Edge: Professional relationships – people work together

Facebook (Social Graph)

Entities: People

Edge: Personal relationships – People are friends

GoogleMaps (Locations)

Entities: Locations

Edge: A way to get from one location to another – Roads, Rail, Air

Each of these can be further thought of in terms of specific means of transport

Bus, Car, Taxi, Individual trains, Airlines

at&t (Phone network)

Entities: Old fashioned phones – landlines

Edge: A network to carry voice from one instrument to another

cisco / google and more (Internet)

Entities: Computers across the world

Edge: A way to send information or data from one computer to another

This can information can be routed wirelessly or over wires

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474120#content

What is a graph?

A graph is a set of vertices and edges (V, E)

A very simple graph is one vertex

Two vertices and a single edge is also a valid graph

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8484198#content

Undirected Graph

Undirected Graph

Unconnected Graph

Directed Graph

Directed Acyclic Graph

Graph Representation

A way to model a vertex which may hold some information

A way to model directed or undirected edges

There are 3 standard ways that graphs can be represented

Adjacency Matrix

Adjacency List

Adjacency Set

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474130#content

Graph Interface

enum GraphType {
    case directed
    case undirected
}

protocol Graph {
    func addEdge(src: Int, dst: Int)
//Helper to get the adjacent vertices for any vertex - A method which is required for all algorithms involving graphs
    func getAdjacentVertices(vertext: Int) -> [Int]?
}

Adjacency Matrix

Use A Matrix with Rows and Columns – It just a Table

The row labels and the column labels represent the vertices

Each cell represents the relationship between the vertices. I.E. The edges
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474136#content

enum GraphType {
    case directed
    case undirected
}

protocol Graph {
    func addEdge(src: Int, dst: Int)
    func getAdjacentVertices(vertext: Int) -> [Int]?
}

class AdjacencyMatrix: Graph {
    private var matrix: [[Int]]
    private let type: GraphType
    
    init(vertices: [Int], graphType: GraphType) {
        matrix = Array(
            repeating: Array(
                repeating: 0,
                count: vertices.count
            ), count: vertices.count
        )
        type = graphType
    }
    
    func addEdge(src: Int, dst: Int) {
        let range = 0..<matrix[0].count
        guard range ~= src, range ~= dst else {
            return
        }
        matrix[src][dst] = 1
        if type == .undirected {
            matrix[dst][src] = 1
        }
    }
    
    func getAdjacentVertices(vertext: Int) -> [Int]? {
        let range = 0..<matrix[0].count
        guard range ~= vertext else {
            return nil
        }
        var result = [Int]()
        for i in 0..<matrix[0].count {
            //If 1 is present in the cell it means that the vertext V is directly connected to another vertex
            if matrix[vertext][i] == 1 {
                result.append(i)
            }
        }
        //Always return the vertices in ascending order - to compare with other values's adjacents
        return result.sorted(by: { $0 < $1 })
    }
}

Adjacency List

Each vertex is a node

Each vertex has a pointer to a linked list

This linked list contains all the other nodes this vertex connects to directly

If a vertex V has an edge leading to another vertex U

The U is present in V’s linked list
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474138#content

Directed Graph – Adjacency List

I’ll skip implementation of adjacency list. Use 2D Matrix or Set, It’s the simple and easy to handle logics.

Cons

Order of the vertices in the adjacency lists matter

The same graph can have multiple representations

Certain operations become tricky. E.G. Deleting a node involves looking through all the adjacency lists to remove the node from all lists
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474138#content

Adjacency Set

This is very similar to an adjacency list

Instead of a linked list to maintain the adjacent vertices It use a Set
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474138#content

enum GraphType {
    case directed
    case undirected
}

protocol Graph {
    func addEdge(src: Int, dst: Int)
    func getAdjacentVertices(vertext: Int) -> [Int]?
}

class Vertex {
    let value: Int
    var adjacencySet: Set<Int>
    
    init(value: Int, adjacencySet: Set<Int>) {
        self.value = value
        self.adjacencySet = adjacencySet
    }
    
    func addEdge(vertext: Int) {
        adjacencySet.insert(vertext)
    }
    
    func getAdjacentVertices() -> [Int] {
        let array = Array(adjacencySet)
        return array.sorted(by: { $0 < $1 })
    }
}

class GraphAdjacencySet: Graph {
    var vertices: [Vertex]
    let graphType: GraphType
    var numberOfVertice = 0
    
    init(numberOfVertices: Int, graphType: GraphType) {
        self.vertices = [Vertex]()
        for i in 0..<numberOfVertices {
            vertices.append(Vertex(value: i, adjacencySet: []))
        }
        self.numberOfVertice = numberOfVertices
        self.graphType = graphType
    }
    
    func addEdge(src: Int, dst: Int) {
        let range = 0..<numberOfVertice
        guard range ~= src, range ~= dst else {
            return
        }
        vertices[src].addEdge(vertext: dst)
        if graphType == .undirected {
            vertices[dst].addEdge(vertext: src)
        }
    }
    
    func getAdjacentVertices(vertext: Int) -> [Int]? {
        let range = 0..<numberOfVertice
        guard range ~= vertext else {
            return nil
        }
        return vertices[vertext].getAdjacentVertices()
    }
}

Comparison of Graph Representations

Adjacency Matrix

This works well when the graph is well connected I.E. Many nodes are connected with many other nodes

The overhead of V^2 space is worth it when the number of connections are large.

Adjacency List/Set

A Sparse graph with few connections between nodes might be more efficiently represented using adjacency list or set

E = Number of Edges

V = Number of Vertices

Space

Adjacency Matrix -> O(V^2)

Adjacency List -> O(E + V)

Adjacency Set -> O(E + V)

Is Edge Present

Adjacency Matrix -> O(1), look up in 2D Array

Adjacency List -> Degree of V

Adjacency Set -> O(LogDegree of V) <- like a binary search…

Iterate over edges on a vertex

Adjacency Matrix -> O(V)

Adjacency List -> Degree of V

Adjacency Set -> Degree of V

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474144#content

Graph Traversal

This is very similar to tree traversal

Depth-First

Breadth-First

One additional wrinkle

In A Tree there is only one path from the root to a specific node

In A Graph multiple paths can lead from one node to another

A Graph can also have cycles, so the same node can be visited multiple times

In order to avoid infinite looping in a graph we need to keep track of the nodes previously visited
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474146#content

Depth First Traversal

//Vertex is 5
var visited = Array(repeating: 0, count: 5)

func dfsGraph(graph: Graph, visited: inout [Int], currentVertex: Int) {
    if visited[currentVertex] == 1 {
        return
    }
    visited[currentVertex] = 1
    
    let list = graph.getAdjacentVertices(vertext: currentVertex) ?? []
    for v in list {
        dfsGraph(graph: graph, visited: &visited, currentVertex: v)
    }
    
    //This for loop ensures that all nodes are covered even for an unconnected graph
    for i in 0..<visited.count {
        dfsGraph(graph: graph, visited: &visited, currentVertex: i)
    }
    //Post order Traversal
    print("\(currentVertex)", terminator: "->")
}

let graph = AdjacencyMatrix(vertices: [0, 1, 2, 3, 4], graphType: .undirected)
graph.addEdge(src: 0, dst: 1)
graph.addEdge(src: 0, dst: 2)

graph.addEdge(src: 1, dst: 4)
graph.addEdge(src: 1, dst: 3)
graph.addEdge(src: 1, dst: 0)

graph.addEdge(src: 2, dst: 0)
graph.addEdge(src: 2, dst: 3)

graph.addEdge(src: 3, dst: 2)
graph.addEdge(src: 3, dst: 1)
graph.addEdge(src: 3, dst: 4)

graph.addEdge(src: 4, dst: 1)
graph.addEdge(src: 4, dst: 3)

dfsGraph(graph: graph, visited: &visited, currentVertex: 0)

Breadth First Traversal

Go level wise from the first node

Add non-visited child nodes to a queue

Visited = true means the node has been seen before

Use a visited list to keep track of nodes already visited

Not using recursive call
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474146#content

func bfsGraph(graph: Graph, visited: inout [Int], currentVertext: Int) {
    var queue = [Int]()
    queue.append(currentVertext)
    
    while !queue.isEmpty {
        let vertex = queue.removeFirst()
        if visited[vertex] == 1 {
            continue
        }
        print("\(vertex)", terminator: "->")
        //MARK Visited
        visited[vertex] = 1
        if let adjacentVertices = graph.getAdjacentVertices(vertext: vertex) {
            for v in adjacentVertices {
                if visited[v] != 1 {
                    queue.append(v)
                }
            }
        }
    }
}

let graph = AdjacencyMatrix(vertices: [0, 1, 2, 3, 4], graphType: .undirected)
graph.addEdge(src: 0, dst: 1)
graph.addEdge(src: 0, dst: 2)

graph.addEdge(src: 1, dst: 4)
graph.addEdge(src: 1, dst: 3)
graph.addEdge(src: 1, dst: 0)

graph.addEdge(src: 2, dst: 0)
graph.addEdge(src: 2, dst: 3)

graph.addEdge(src: 3, dst: 2)
graph.addEdge(src: 3, dst: 1)
graph.addEdge(src: 3, dst: 4)

graph.addEdge(src: 4, dst: 1)
graph.addEdge(src: 4, dst: 3)

bfsGraph(graph: graph, visited: &visited, currentVertext: 0)

Check Unconnected Graph – BFS

🔥 BFS is not using a recursive call. Don’t put below logic inside bfsGraph function!


    //This for loop ensures that all nodes are covered even for an unconnected graph
    for i in 0..<visited.count {
        bfsGraph(graph: graph, visited: &visited, currentVertext: i)
    }

Exercise 1. Topological Sort

It is an ordering of vertices in a directed acyclic graph in which each node comes before all the nodes to which

It has outgoing edges

A -> B

A should come before B

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474156#content

Find first vertex

If there are vertices which has no incoming edge, you can start any of vertex among them.

Indegree

Number of inward directed graph edges for a given graph vertex
Indegree of vertex 0 is 0

If there were no vertices with 0 indegree, then there would have been no topological sort -> The graph has a cycle.

It is an ordering of vertices in a Directed Acyclic Graph in which each node comes before all the nodes to which. It has outgoing edges

Final code for topological sort. (I added 2 functions)

enum GraphType {
    case directed
    case undirected
}

protocol Graph {
    func addEdge(src: Int, dst: Int)
    func getAdjacentVertices(vertext: Int) -> [Int]?
//New functions
    func getIndegree(vertext: Int) -> Int
    var numberOfVertices: Int { get set }
}

class Vertex {
    let value: Int
    var adjacencySet: Set<Int>
    
    init(value: Int, adjacencySet: Set<Int>) {
        self.value = value
        self.adjacencySet = adjacencySet
    }
    
    func addEdge(vertext: Int) {
        adjacencySet.insert(vertext)
    }
    
    func getAdjacentVertices() -> [Int] {
        let array = Array(adjacencySet)
        return array.sorted(by: { $0 < $1 })
    }
}

Using Matrix

class AdjacencyMatrix: Graph {
    var numberOfVertices: Int
    private var matrix: [[Int]]
    private let type: GraphType
    
    init(vertices: [Int], graphType: GraphType) {
        matrix = Array(
            repeating: Array(
                repeating: 0,
                count: vertices.count
            ), count: vertices.count
        )
        numberOfVertices = vertices.count
        type = graphType
    }
    
    func addEdge(src: Int, dst: Int) {
        let range = 0..<numberOfVertices
        guard range ~= src, range ~= dst else {
            return
        }
        matrix[src][dst] = 1
        if type == .undirected {
            matrix[dst][src] = 1
        }
    }
    
    func getAdjacentVertices(vertext: Int) -> [Int]? {
        let range = 0..<numberOfVertices
        guard range ~= vertext else {
            return nil
        }
        var result = [Int]()
        for i in 0..<numberOfVertices {
            //If 1 is present in the cell it means that the vertext V is directly connected to another vertex
            if matrix[vertext][i] == 1 {
                result.append(i)
            }
        }
        //Always return the vertices in ascending order - to compare with other values's adjacents
        return result.sorted(by: { $0 < $1 })
    }
    
    //New function, Get Indegree of vertex
    func getIndegree(vertext: Int) -> Int {
        let range = 0..<numberOfVertices
        guard range ~= vertext else {
            return 0
        }
        var indegree = 0
        //Loop from 0 to all vertex
        for i in 0..<numberOfVertices {
            //src = i, dst = vertex
            if matrix[i][vertext] != 0 {
                indegree += 1
            }
        }
        return indegree
    }
}

Topological Sort

func topologicalSort(graph: Graph) -> [Int] {
    var queue = [Int]()
    var indgreeMap = [Int: Int]()
    
    //Step 1. Add first node of sort
    for i in 0..<graph.numberOfVertices {
        let indegree = graph.getIndegree(vertext: i)
        //Add indegree 0's vertex to queue
        indgreeMap[i] = indegree
        //Add all vertices with indegree = 0 to the queue of vertices to explore
        if indegree == 0 {
            queue.append(i)
        }
    }
    
    print(indgreeMap)
    var result = [Int]()
    //BFS
    while !queue.isEmpty {
        let vertex = queue.removeLast()
        result.append(vertex)
        var adjacentVertices = graph.getAdjacentVertices(vertext: vertex) ?? []
        print("v: \(vertex) -> neighbors: \(adjacentVertices)")
        for v in adjacentVertices {
            //Important! get indegree from dictionary!
            //Get the adjacent vertices of the current one and decrement their indegrees by 1
            let updatedIndegree = indgreeMap[v]! - 1
            indgreeMap[v] = updatedIndegree
            //For every vertex which now has indegree = 0, It's a potential next node for the topological sort
            if updatedIndegree == 0 {
                queue.append(v)
            }
        }
    }
    
    print(result)
    //If the final sorted list is not same to the number of vertices in the graph there is a cycles
    if result.count != graph.numberOfVertices {
        print("There is cycle")
        return []
    }
    
    return result
}

Topological sort using Matrix

let graph = AdjacencyMatrix(vertices: [0, 1, 2, 3, 4], graphType: .directed)
graph.addEdge(src: 0, dst: 1)
graph.addEdge(src: 0, dst: 2)

graph.addEdge(src: 1, dst: 4)

graph.addEdge(src: 2, dst: 3)

graph.addEdge(src: 3, dst: 1)
graph.addEdge(src: 3, dst: 4)

topologicalSort(graph: graph)

Using Set

class GraphAdjacencySet: Graph {
    var vertices: [Vertex]
    let graphType: GraphType
    var numberOfVertices: Int
    init(numberOfVertices: Int, graphType: GraphType) {
        self.vertices = [Vertex]()
        for i in 0..<numberOfVertices {
            vertices.append(Vertex(value: i, adjacencySet: []))
        }
        self.numberOfVertices = numberOfVertices
        self.graphType = graphType
    }
    
    func addEdge(src: Int, dst: Int) {
        let range = 0..<numberOfVertices
        guard range ~= src, range ~= dst else {
            return
        }
        vertices[src].addEdge(vertext: dst)
        if graphType == .undirected {
            vertices[dst].addEdge(vertext: src)
        }
    }
    
    func getAdjacentVertices(vertext: Int) -> [Int]? {
        let range = 0..<numberOfVertices
        guard range ~= vertext else {
            return nil
        }
        return vertices[vertext].getAdjacentVertices()
    }
    
    //New function, Get Indegree of vertex
    func getIndegree(vertext: Int) -> Int {
        let range = 0..<numberOfVertices
        guard range ~= vertext else {
            return 0
        }
        var indegree = 0
        //Loop from 0 to all vertex
        for i in 0..<numberOfVertices {
            if getAdjacentVertices(vertext: i)?.contains(vertext) == true {
                indegree += 1
            }
        }
        return indegree
    }
}

let graph = GraphAdjacencySet(numberOfVertices: 5, graphType: .directed)

graph.addEdge(src: 0, dst: 1)
graph.addEdge(src: 0, dst: 2)

graph.addEdge(src: 1, dst: 4)

graph.addEdge(src: 2, dst: 3)

graph.addEdge(src: 3, dst: 1)
graph.addEdge(src: 3, dst: 4)

topologicalSort(graph: graph)

As you can see the results are the same. You don’t need to change topological sort logic, Because both Set and Matrix implements Graph interface.

Exercise 2. Design A Course Schedule Considering Pre-reqs for Courses

Design a schedule for a student to complete her degree given the list of courses along with the prerequisites for each course

We have 2 lists

List of courses

List of pre-reqs for each course

This contains pairs (course A, course B) where course A, course B belong to courses list and course A should be taken before course B

We want to know a valid order in which the student can take her courses!
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474160#content

Each course can be a vertex

Any course that has pre-reqs should not come before its pre-reqs in the schedule!

It is an ordering of vertices in a directed acyclic graph in which each node comes before all the nodes to which it has outgoing edges

It’s a Topological Sort!
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474160#content

All nodes with indegree 0 are potential courses the student could start with

There are many schedules possible!

func courseOrder(courseList: [Int], prereqs: [Int: [Int]]) {
    let graph = AdjacencyMatrix(vertices: courseList, graphType: .directed)
    //You need this because Matrix used row and col start from 0 to number of vertices.
    var courseId = [Int: Int]()
    var matrixIndexToCourseId = [Int: Int]()
    
    for (index, course) in courseList.enumerated() {
        courseId[course] = index
        matrixIndexToCourseId[index] = course
    }
    
    //Link Edges
    for (preCourse, nextCourse) in prereqs {
        for next in nextCourse {
            print("add edge: \(preCourse) -> \(next)")
            let preCourseId = courseId[preCourse]
            let nextId = courseId[next]
            graph.addEdge(src: preCourseId!, dst: nextId!)
        }
    }
    var indegreeMap = [Int: Int]()
    //Int is courseId not a Index
    var queue = [Int]()
    var sorted = [Int]()
    
    for v in courseList {
        //VertextId will be 0..<numberOfVertices
        let vertexId = courseId[v]!
        let indegree = graph.getIndegree(vertext: vertexId)
        indegreeMap[v] = indegree
        //Can take this course
        if indegree == 0 {
            queue.append(v)
        }
    }
    print(indegreeMap)
    while !queue.isEmpty {
        let insertingCourse = queue.removeFirst()
        sorted.append(insertingCourse)
        let vertexId = courseId[insertingCourse]!
        let nextCourses = graph.getAdjacentVertices(vertext: vertexId) ?? []
        for nextCourse in nextCourses {
            let courseId = matrixIndexToCourseId[nextCourse]!
            let updatedIndegree = indegreeMap[courseId]! - 1
            indegreeMap[courseId] = updatedIndegree
            print("Next course: \(courseId) - Indegree: \(updatedIndegree)")
            if updatedIndegree == 0 {
                queue.append(courseId)
            }
        }
    }
    print(sorted)
}

courseOrder(
    courseList: [101, 102, 103, 104, 105, 106, 107],
    prereqs: [101: [102, 103, 105], 104: [105], 105: [107]]
)

Shawn