Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Kotlin The Interactive Edition

Bradley N. Miller, David L. Ranum, Roman Yasinovskyy, J. David Eisenberg, David R. Musicant

Section 10.6 Implementation

Using maps, we can implement the adjacency list in Kotlin. In our implementation of the graph abstract data type, we will use a mutable map named neighbors. Each vertex is represented in neighbors via a key, which typically is a string, but doesn’t have to be. In Section 10.5 this map is represented by the shaded gray box. neighbors maps each vertex to another mutable map, which contains that vertex’s neighbors as keys, and weights as values.
🔗
Our implementation also provides methods for adding vertices to a graph and connecting one vertex to another. The addVertex method is used to add a new vertex to the graph, and the addEdge method is used to add a connection between two vertices. If addEdge is used with one or more vertices that are not already present in the graph, it will add them.
🔗

Aside

There are also methods for returning neighbors associated for a particular vertex. Specifically, the getNeighbors method returns a set of the vertices adjacent to a particular vertex. The getWeight method can then be used to get the weight associated with a particular edge.
🔗
Our implementation can represent either a directed graph or an undirected graph. Since this is an adjacency list implementation, the code for the two are nearly identical. For an undirected graph, if we have an edge between A and B, we store it as two directed edges: one from A to B, and one from B to A. So the only difference in the two implementations is in the addEdge method, which adds both directions for an edge if the graph is undirected. We handle this with a boolean variable in the constructor for the graph indicating whether it should be handled as a directed or an undirected graph.
🔗
Listing 10.6.1. Graph implementation
🔗
class AdjListGraph<T>(val directed: Boolean): GraphADT<T> {

    // T represents the type of the id for each vertex.
    // Each vertex maps to a collection of neighbors.
    // This collection maps each neighbor to the weight of the edge.
    var neighbors = mutableMapOf<T, MutableMap<T, Double>>()

    // Returns true if vertex added,
    // false if not (because it was already there)
    override fun addVertex(id: T): Boolean {
        if (id !in neighbors) {
            neighbors[id] = mutableMapOf()
            return true
        } else {
            return false
        }
    }

    // Adds edge if not previously present;
    // replaces weight with new one if edge already there.
    // A default weight of 0 is placed if the function
    // is called without specifying a weight; this is handled
    // via the interface.
    override fun addEdge(begin: T, end: T, weight: Double) {
        // Make sure vertices are in the graph. (addVertex will
        // just return false if already there.)
        addVertex(begin)
        addVertex(end)
        neighbors[begin]!![end] = weight
        if (!directed) {
            neighbors[end]!![begin] = weight
        }
    }

    // Returns true if vertex is present, false if not
    override fun hasVertex(id: T): Boolean {
        return id in neighbors
    }

    // Returns true if edge is present, false if not
    override fun hasEdge(begin: T, end: T): Boolean {
        val beginNeighbors = neighbors[begin]
        return beginNeighbors != null && end in beginNeighbors
    }

    // Returns a set of all vertex keys in the graph
    override fun getVertices(): Set<T> {
        return neighbors.keys
    }

    // Returns a set of all neighbors to a vertex.
    // Returns null if the vertex is not in the graph.
    override fun getNeighbors(id: T): Set<T>? {
        return neighbors[id]?.keys
    }

    // Returns the weight associated with an edge.
    // Returns null if the edge is not in the graph.
    override fun getWeight(begin: T, end: T): Double? {
        return neighbors[begin]!![end]
    }

    override fun toString(): String {
        var result = ""
        for (vertex in neighbors.keys) {
            result += vertex.toString() + ": " + neighbors[vertex].toString() + "\n"
        }
        return result
    }
}
Using the AdjListGraph class just defined, the following program creates two graphs: a directed graph, and an undirected graph. For each, we add six vertices, with integers 0 through 5 as their IDs. Next, we add edges that connect the vertices together. Finally, we display the graph. You should check the output of the edge list against the edges that are inserted, and convince yourself that it is correct.
🔗
There’s a small stylistic detail to notice. In lines 3 and 19, when we construct the AdjListGraph, we use a named argument. Instead of just supplying the value true to indicate that we are constructing a directed graph, as in the following:
🔗
val g1 = AdjListGraph<Int>(true)
🔗
we instead use the name of the argument as well:
🔗
val g1 = AdjListGraph<Int>(directed=true)
🔗
This is optional in Kotlin, but is useful for clarity. In this particular case, it makes the code considerably more readable to include the name of the argument.
🔗
Listing 10.6.2. Testing the AdjListGraph Class
🔗
Here is its output:
🔗
Test 1: directed graph
0: {1=5.0, 5=2.0}
1: {2=4.0}
2: {3=9.0}
3: {4=7.0, 5=3.0}
4: {0=1.0}
5: {4=8.0, 2=1.0}

Test 2: undirected graph
0: {1=5.0, 5=2.0, 4=1.0}
1: {0=5.0, 2=4.0}
2: {1=4.0, 3=9.0, 5=1.0}
3: {2=9.0, 4=7.0, 5=3.0}
4: {3=7.0, 0=1.0, 5=8.0}
5: {0=2.0, 3=3.0, 4=8.0, 2=1.0}
You have attempted of activities on this page.
🔗
PrevTopNext