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
|
package at.hannibal2.skyhanni.utils
import at.hannibal2.skyhanni.data.model.Graph
import at.hannibal2.skyhanni.data.model.GraphNode
import at.hannibal2.skyhanni.data.model.findAllShortestDistances
import at.hannibal2.skyhanni.data.model.findDijkstraDistances
import at.hannibal2.skyhanni.data.model.findPathToDestination
import java.util.Stack
object GraphUtils {
/**
* Find the fastest path from [closestNode] to *any* node that matches [condition].
*/
fun findFastestPath(
graph: Graph,
closestNode: GraphNode,
condition: (GraphNode) -> Boolean,
): Pair<Graph, Double>? {
val distances = graph.findDijkstraDistances(closestNode, condition)
val entry = distances.lastVisitedNode.takeIf(condition)
return entry?.let {
distances.findPathToDestination(it)
}
}
/**
* Find the fastest path from [closestNode] to *all* nodes that matches [condition].
*/
fun findFastestPaths(
graph: Graph,
closestNode: GraphNode,
condition: (GraphNode) -> Boolean = { true },
): Pair<MutableMap<GraphNode, Graph>, MutableMap<GraphNode, Double>> {
val paths = mutableMapOf<GraphNode, Graph>()
val map = mutableMapOf<GraphNode, Double>()
val distances = graph.findAllShortestDistances(closestNode)
for (graphNode in graph.nodes) {
if (!condition(graphNode)) continue
val (path, distance) = distances.findPathToDestination(graphNode)
paths[graphNode] = path
map[graphNode] = distance
}
return Pair(paths, map)
}
/**
* Find all maximal sub graphs of the given graph which are not connected
*/
fun findDisjointClusters(graph: Graph): List<Set<GraphNode>> {
val universe = graph.toMutableSet()
val allClusters = mutableListOf<Set<GraphNode>>()
while (universe.isNotEmpty()) {
val cluster = mutableSetOf<GraphNode>()
allClusters.add(cluster)
val queue = Stack<GraphNode>()
queue.add(universe.first())
while (queue.isNotEmpty()) {
val next = queue.pop()
universe.remove(next)
cluster.add(next)
queue.addAll(next.neighbours.keys)
queue.retainAll(universe)
}
}
return allClusters
}
}
|
