Graph Implementation in Kotlin

1. Introduction

In this tutorial, we will learn how to implement a simple Graph structure using Kotlin programming language.

A Graph is a collection of nodes (vertices) with edges connecting them. These structures are ubiquitous in computer science and can represent various real-world entities like road networks, social networks, and more. In this post, we will discuss a comprehensive Graph implementation in Kotlin and cover common operations such as adding vertices, adding edges, removing vertices, removing edges, and displaying the graph.

2. Implementation Steps

1. Define a Graph class.

2. Use a HashMap to store vertices and their respective adjacent vertices.

3. Implement methods for adding and removing vertices and edges.

4. Implement a method to display the graph.

3. Implementation in Kotlin Programming

class Graph {
    private val adjList: HashMap<Int, MutableList<Int>> = HashMap()
    
    // Adds a vertex to the graph
    fun addVertex(vertex: Int) {
        if (!adjList.containsKey(vertex)) adjList[vertex] = mutableListOf()
    }
    
    // Adds an edge between two vertices
    fun addEdge(v1: Int, v2: Int) {
        adjList[v1]?.add(v2)
        adjList[v2]?.add(v1)  // Since it's an undirected graph
    }
    
    // Removes a vertex and its associated edges
    fun removeVertex(vertex: Int) {
        while (adjList[vertex]?.isNotEmpty() == true) {
            val adjacentVertex = adjList[vertex]?.first()
            removeEdge(vertex, adjacentVertex!!)
        }
        adjList.remove(vertex)
    }
    
    // Removes an edge between two vertices
    fun removeEdge(v1: Int, v2: Int) {
        adjList[v1]?.remove(v2)
        adjList[v2]?.remove(v1)
    }
    
    // Displays the graph
    fun display() {
        for ((vertex, edges) in adjList) {
            println("$vertex -> $edges")
        }
    }
}

// client code to test Graph Implementation in Kotlin
fun main() {
    val graph = Graph()
    graph.addVertex(1)
    graph.addVertex(2)
    graph.addVertex(3)
    graph.addVertex(4)
    graph.addEdge(1, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 4)
    graph.display()
    graph.removeEdge(2, 4)
    graph.removeVertex(3)
    graph.display()
}

Output:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3]
1 -> [2]
2 -> [1]
4 -> []

Explanation:

1. Graph class: Represents the graph using an adjacency list.

2. adjList: A HashMap where each key is a vertex, and its value is a list of adjacent vertices.

3. addVertex method: Adds a vertex to the graph.

4. addEdge method: Adds an edge between two vertices.

5. removeVertex method: Removes a vertex and its associated edges from the graph.

6. removeEdge method: Removes an edge between two vertices.

7. display method: Prints out the graph in the form of an adjacency list.

8. The main function demonstrates adding vertices and edges, displaying the graph, and then removing vertices and edges followed by another display to see the changes.