iOS, Graph Data Structure

Graph data structure implementation in Swift for iOS developers

Written by

Traveller

in

✍️ 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 and directed graph examples showing vertices and edges

Undirected Graph

Undirected graph showing adjacent nodes, degree three at F, and a path from C to B
Graph with a cycle compared with a connected acyclic graph that forms a tree

Unconnected Graph

Disconnected acyclic graph forming a forest of two trees

Directed Graph

Directed graph showing cycle A-B-D-A and path A-B-F-H

Directed Acyclic Graph

Directed acyclic graph with vertices A through H

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
Directed graph represented as a five-by-five adjacency matrix
Undirected graph represented as a symmetric adjacency matrix
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.

Directed graph represented as an adjacency list
Undirected graph represented as an adjacency list

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
Undirected graph represented with adjacency sets
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
Graph traversal using a visited list to prevent revisiting nodes

Depth First Traversal

Numeric graph traversal using a visited list for vertices 0 through 4
//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)
Swift depth-first graph traversal with output 4, 2, 3, 1, 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
Breadth-first traversal moving level by level from vertex 0
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)
Swift breadth-first graph traversal with output 0, 1, 2, 3, 4

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
Topological-sort steps applying dependency constraints to vertices 0 through 4
Directed acyclic graph with topological order 0, 2, 3, 1, 4

Find first vertex

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

Topological sort selecting vertex 0 because it has no incoming edge

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.

Directed graph labeled with each vertex indegree
Topological-sort step removing vertex 0 and reducing neighboring indegrees
Topological-sort steps selecting vertices 2 and 3 after their indegrees reach zero
Completed topological order 0, 2, 3, 1, 4 with O(V plus E) complexity

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

Topological-sort result after every vertex and edge is visited once
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)
Swift adjacency-matrix topological sort producing 0, 2, 3, 1, 4

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)
Swift adjacency-set topological sort producing 0, 2, 3, 1, 4

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

Computer science course list with prerequisite course pairs
Directed graph representing course prerequisite relationships

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
Course prerequisite graph labeled with each course indegree

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]]
)
Swift course scheduling with topological order 101, 104, 106, 102, 103, 105, 107

Comments

Leave a Reply

More posts