-
Notifications
You must be signed in to change notification settings - Fork 7
/
UndirectedGraph.kt
193 lines (168 loc) · 5.25 KB
/
UndirectedGraph.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
/*******************************************************
* UndirectedGraph.kt
* Created by Stephen Hall on 11/08/18.
* Copyright (c) 2018 Stephen Hall. All rights reserved.
* Undirected Graph implementation in Kotlin
*****************************************************/
import java.util.Collections
import java.util.LinkedHashMap
/**
* Undirected Graph class
*/
class UndirectedGraph {
/**
* private members
*/
/**
* gets the number of edges
* @return int: number of edges
*/
private var numberOfEdges: Int = 0
private val map = LinkedHashMap<Int, MutableMap<Int, Double>>()
/**
* Returns all nodes of a graph
* @return Set: set of the nodes in the graph
*/
val allNodes: Set<Int>
get() = Collections.unmodifiableSet(map.keys)
/**
* Gets the size of the graph
* @return int: size of the graph
*/
fun size(): Int {
return map.size
}
/**
* adds a node into the graph
* @param nodeId: id to add
* @return boolean: success|fail
*/
fun addNode(nodeId: Int): Boolean {
if (map.containsKey(nodeId)) {
return false
}
map[nodeId] = LinkedHashMap()
return true
}
/**
* test to see if the node exisits
* @param nodeId: id to find
* @return boolean: true|false
*/
fun hasNode(nodeId: Int): Boolean {
return map.containsKey(nodeId)
}
/**
* clears a node from the graph
* @param nodeId: id to clear
* @return boolean: success|fail
*/
fun clearNode(nodeId: Int): Boolean {
if (!hasNode(nodeId)) {
return false
}
val neighbors = map[nodeId]
if (neighbors!!.isEmpty()) {
return false
}
neighbors.keys.forEach { neighborId -> map[neighborId]!!.remove(nodeId) }
numberOfEdges -= neighbors.size
neighbors.clear()
return true
}
/**
* removes a node from the graph
* @param nodeId: id to remove
* @return boolean: success|fail
*/
fun removeNode(nodeId: Int): Boolean {
if (hasNode(nodeId)) {
clearNode(nodeId)
map.remove(nodeId)
return true
}
return false
}
/**
* helper function to add an edge to the graph
* @param tailNodeId: tail node
* @param headNodeId: head node
* @param weight: weight of the edge
* @return boolean: success|fail
*/
@JvmOverloads
fun addEdge(tailNodeId: Int, headNodeId: Int, weight: Double = 1.0): Boolean {
if (tailNodeId != headNodeId) {
addNode(tailNodeId)
addNode(headNodeId)
if (!map[tailNodeId]!!.containsKey(headNodeId)) {
map[tailNodeId]!![headNodeId] = weight
map[headNodeId]!![tailNodeId] = weight
++numberOfEdges
return true
} else {
val oldWeight = map[tailNodeId]!![headNodeId]
map[tailNodeId]!![headNodeId] = weight
map[headNodeId]!![tailNodeId] = weight
return oldWeight != weight
}
}
// Undirected graph are not allowed to contain self-loops.
return false
}
/**
* tests to see if an edge exisit
* @param tailNodeId: tail node
* @param headNodeId: head node
* @return boolean: true|false
*/
fun hasEdge(tailNodeId: Int, headNodeId: Int): Boolean {
return map.containsKey(tailNodeId) && map[tailNodeId]!!.containsKey(headNodeId)
}
/**
* gets the weight of an edge
* @param tailNodeId: tail node
* @param headNodeId: head node
* @return double: weight of the edge
*/
fun getEdgeWeight(tailNodeId: Int, headNodeId: Int): Double? {
return if (!hasEdge(tailNodeId, headNodeId)) java.lang.Double.NaN else map[tailNodeId]!!.get(headNodeId)
}
/**
* removes an edge from the graph
* @param tailNodeId: tail node
* @param headNodeId: head node
* @return boolean: success|fail
*/
fun removeEdge(tailNodeId: Int, headNodeId: Int): Boolean {
if (!(map.containsKey(tailNodeId) || !map[tailNodeId]!!.containsKey(headNodeId)))
return false
map[tailNodeId]!!.remove(headNodeId)
map[headNodeId]!!.remove(tailNodeId)
--numberOfEdges
return true
}
/**
* gets the children of the given node
* @param nodeId: node to test
* @return Set: set of child nodes
*/
fun getChildrenOf(nodeId: Int): Set<Int> {
return if (map.containsKey(nodeId)) Collections.unmodifiableSet(map[nodeId]!!.keys) else emptySet()
}
/**
* gets the parents of a node
* @param nodeId: node to test
* @return Set: set of parents
*/
fun getParentsOf(nodeId: Int): Set<Int> {
return if (map.containsKey(nodeId)) Collections.unmodifiableSet(map[nodeId]!!.keys) else emptySet()
}
/**
* Clears the graph of all nodes and edges
*/
fun clear() {
map.clear()
numberOfEdges = 0
}
}