Upload

simphotonics · Aug 15, 2023 · b0577e5 · b0577e5
1 parent 316cd02
commit b0577e5
Showing 1 changed file with 52 additions and 1 deletion.
diff --git a/analysis_options.yaml b/analysis_options.yaml
@@ -1,2 +1,53 @@
 include: package:lints/recommended.yaml
-# 
+#
+
+/// Returns a list of strongly connected components.
+  /// * If vertices a and b belong to the same strongly connected component,
+  /// then vertex a is reachable from b and vertex b is reachable from a.
+  /// * Uses Tarjans algorithm (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#References)
+  /// * If a graph is acyclic, each strongly connected component
+  /// consists of a single vertex and the vertices are listed in inverse
+  /// topological order. Note: The reverse is not true if the graph contains any
+  /// self-loops, that is edges pointing from a vertex to itself.
+  List<List<T>> get stronglyConnectedComponentsI {
+    final queue = Queue<T>();
+    var index = 0;
+    final result = <List<T>>[];
+
+    final lowLink = HashMap<T, int>();
+    final indices = HashMap<T, int>();
+
+    void strongConnect(T vertex) {
+      lowLink[vertex] = index;
+      indices[vertex] = index;
+      index++;
+      queue.addLast(vertex);
+
+      for (final connectedVertex in edges(vertex)) {
+        if (!indices.containsKey(connectedVertex)) {
+          strongConnect(connectedVertex);
+          lowLink[vertex] = min(lowLink[vertex]!, lowLink[connectedVertex]!);
+        } else if (queue.contains(connectedVertex)) {
+          lowLink[vertex] = min(lowLink[vertex]!, indices[connectedVertex]!);
+        }
+      }
+
+      // Check if vertex is a root node:
+      if (lowLink[vertex] == indices[vertex]) {
+        final scc = <T>[];
+        late T componentVertex;
+        do {
+          componentVertex = queue.removeLast();
+          scc.add(componentVertex);
+        } while (vertex != componentVertex);
+        result.add(scc);
+      }
+    }
+
+    for (final vertex in sortedVertices) {
+      if (!indices.containsKey(vertex)) {
+        strongConnect(vertex);
+      }
+    }
+    return result;
+  }