1 files changed, 68 insertions, 0 deletions
diff --git a/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt b/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt
new file mode 100644
index 000000000..4a245a894
--- /dev/null
+++ b/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt
@@ -0,0 +1,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
+    }
+}