tarjansAlgorithm<T> function

TarjansResult<T> tarjansAlgorithm<T>(Map<T, List<T>> graph)

Tarjan's algorithm for finding bridges and articulation points

graph represents the undirected graph as adjacency list

Returns a TarjansResult containing all bridges and articulation points.

Throws ArgumentError if the graph is empty.

Implementation

TarjansResult<T> tarjansAlgorithm<T>(Map<T, List<T>> graph) {
  // Input validation
  if (graph.isEmpty) {
    throw ArgumentError('Graph cannot be empty');
  }

  final bridges = <Bridge<T>>[];
  final articulationPoints = <T>{};
  final discovery = <T, int>{};
  final low = <T, int>{};
  final parent = <T, T?>{};
  final children = <T, int>{};
  int time = 0;

  // Initialize all nodes
  for (final node in graph.keys) {
    discovery[node] = -1;
    low[node] = -1;
    parent[node] = null;
    children[node] = 0;
  }

  // DFS from each unvisited node (handles disconnected components)
  for (final node in graph.keys) {
    if (discovery[node] == -1) {
      _dfs(
        node,
        graph,
        bridges,
        articulationPoints,
        discovery,
        low,
        parent,
        children,
        time,
      );
    }
  }

  return TarjansResult<T>(
    bridges: bridges,
    articulationPoints: articulationPoints,
  );
}