Directed Graph with Kotlin
A graph is a mathematical structure studied in computer science as a data structure with one of the most beautiful arrangements. According to Cormen et al. (2009), "hundreds of interesting computational problems are couched in terms of graphs".
Galata and Suica (2019) bring a good introduction to the graph concept: social networks and booking cheap flights, what do they have in common? We can represent both as a graph! At the end of this paper, we will be able to understand this association.
If you are looking for a short introduction to graph data structure concepts, this story presents a simple Kotlin implementation 😃
Graph
"A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges." (GALATA; SUICA, 2019)
The most common representation of a graph is presented below.
Circles represent the vertices and lines the edges. Then, we have two abstractions: Vertex and Edge. Let's create both of them and understand their connections and the directed graph fundamentals.
Directed Graphs
Directed graphs are more restrictive. In the other words, between two vertices we have a directed edge (GALATA; SUICA, 2019), therefore we determine that vertex A is directed to vertex B, and not necessarily vertex B is directed to vertex A. When we are studying undirected graphs, it means that a vertex is directed to another vertex, and vice versa.
A directed graph illustration is presented next by Cormen et al. (2009).
Aiming to understand what directed edge means, let's see the implementation of a vertex and edge in Kotlin, based on Galata and Suica (2019).
Vertice
As well as a Node in the other data structures, a vertex is a complex data type that holds some values. So, we will represent it as a data class.
data class Vertex<T>(
val index: Int,
val data: T,
)Edge
The responsibility of an edge is to connect two vertices. Beyond the reference of these two vertices, an edge can have weight. With weight and eventually other data, it's possible to get some inferences about the connections.
data class Edge<T>(
val source: Vertex<T>,
val destination: Vertex<T>,
val weight: Double? = null,
)Adjacency list
Considering that a vertex can have several edges — according to the illustration presented by Cormen et al. (2009), we need to manage this in some way. The adjacency list is one technique that consists of an array of edges, one for each vertex. To implement this approach, a hash table will be used to handle the vertices of our graph, therefore the key of the hash table is our vertices, and the value is the edge list.
class AdjacencyList<T> {
private val adjacencyMap = mutableMapOf<Vertex<T>, ArrayList<Edge<T>>>()
}Looking at the directed graph previously shown, the adjacency list will be like this:
Vertex creation
Right now, let's implement a function that creates an instance of Vertex, adds this to our hash table (with an empty array list), and returns the vertex.
class AdjacencyList<T> {
private val adjacencyMap = mutableMapOf<Vertex<T>, ArrayList<Edge<T>>>()
fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(adjacencyMap.count(), data)
adjacencyMap[vertex] = arrayListOf()
return vertex
}
}The index value of vertices will be the count() of the map, so this returns the number of entries in this map.
Directed edge creation
Creating a directed edge consists of adding edges with a source and destination. An instance of Edge is created and then we verify whether the source passed on edge exists in our hash table of vertices, existing the source we will be able to add a new edge on the array list of our source vertex.
class AdjacencyList<T> {
private val adjacencyMap = mutableMapOf<Vertex<T>, ArrayList<Edge<T>>>()
fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(adjacencyMap.count(), data)
adjacencyMap[vertex] = arrayListOf()
return vertex
}
fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double? = 0.0) {
val edge = Edge(source, destination, weight)
adjacencyMap[source]?.add(edge)
}
}At this moment, we have done our directed graph with basic functions that let us create vertices and add edges with a specific source and destination. Aiming to complete the adjacency list, let's just implement a function to show all the destinations related to one vertex through the edges.
class AdjacencyList<T> {
private val adjacencyMap = mutableMapOf<Vertex<T>, ArrayList<Edge<T>>>()
fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(adjacencyMap.count(), data)
adjacencyMap[vertex] = arrayListOf()
return vertex
}
fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double? = 0.0) {
val edge = Edge(source, destination, weight)
adjacencyMap[source]?.add(edge)
}
fun toString(): String {
return buildString {
adjacencyMap.forEach { (vertex, edges) ->
val edgeString = edges.joinToString { it.destination.data.toString() }
append("${vertex.data} -> [$edgeString]\n")
}
}
}
}Creating a booking flights
An example of an adjacency list instance with some calls of the add directed edges function.
fun main() {
val adjacencyListGraph = AdjacencyList<String>()
val brazil = adjacencyListGraph.createVertex("Brazil")
val germany = adjacencyListGraph.createVertex("Germany")
val thailand = adjacencyListGraph.createVertex("Thailand")
val unitedKingdom = adjacencyListGraph.createVertex("United Kingdom")
adjacencyListGraph.addDirectedEdge(brazil, germany, 1860.00)
adjacencyListGraph.addDirectedEdge(brazil, thailand, 2310.00)
adjacencyListGraph.addDirectedEdge(thailand, germany, 1250.00)
adjacencyListGraph.addDirectedEdge(germany, unitedKingdom, 1310.00)
adjacencyListGraph.addDirectedEdge(unitedKingdom, brazil, 890.00)
println(adjacencyListGraph)
}Brazil -> [Germany, Thailand]
Germany -> [United Kingdom]
Thailand -> [Germany]
United Kingdom -> [Brazil]Conclusion
A graph of the adjacency list with directed edges was created and used to simulate booking flights. With these code snippets, we can observe the graph behavior and how we can implement this data structure in Kotlin.
As we can see in this approach, taking into account the simple example of booking flights, directed graphs can be used for many computational problems.
It's recommended to study and do some implementations of undirected graphs, besides the algorithms of traversal that are very interesting to take a step forward 🚀
References
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. Introduction to Algorithms. 3. ed. Cambridge: Mit Press, 2009. 1292 p.
Galata, I.; Suica, M. Data Structures & Algorithms in Kotlin. Alexandria: Razeware, 2019. 403 p.
