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 to 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, and the getNeighborsAndWeights method returns a map consisting of all neighbors and the weights of the corresponding edges. By using the results from these methods you can iterate over the vertices in a graph by ID, or by the objects themselves.
class AdjacencyListGraph<T>: GraphADT<T> {
// T represents the id, or key, for each vertex.
// Each vertex maps to a set of vertices.
// Each set is an "adjacency set" of neighbors.
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)
// Local copy for null safety.
// We just verified vertex is there, so not null.
val beginNeighbors = neighbors[begin]!!
// Add or replace the edge.
beginNeighbors[end] = weight
}
// Returns true if vertex is present, false if not
override fun containsVertex(id: T): Boolean {
return id in neighbors
}
// Returns true if edge is present, false if not
override fun containsEdge(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 a map of all neighbors to a vertex,
// and the weights of the edges.
// Returns null if the vertex is not in the graph.
override fun getNeighborsAndWeights(id: T): Map<T, Double>? {
return neighbors[id]
}
}
Using the
AdjacencyListGraph class just defined, the following program creates the graph in Section 10.2. First we add six vertices, with integers 0 through 5 as their IDs. Next, we add the edges that connect the vertices together. Finally, the loop displays each vertex, and its neighbors with their weights. You should check the output of the edge list at the end of this session against the graph shown in Section 10.2.
Graph ClassHere is its output:
0 connected to: {1=5.0, 5=2.0}
1 connected to: {2=4.0}
2 connected to: {3=9.0}
3 connected to: {4=7.0, 5=3.0}
4 connected to: {0=1.0}
5 connected to: {4=8.0, 2=1.0}
You have attempted of activities on this page.
