tarjansAlgorithmDetailed<T> function

TarjansDetailedResult<T> tarjansAlgorithmDetailed<T>(Map<T, List<T>> graph)

Enhanced Tarjan's algorithm with detailed analysis

Implementation

TarjansDetailedResult<T> tarjansAlgorithmDetailed<T>(Map<T, List<T>> graph) {
  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
  for (final node in graph.keys) {
    if (discovery[node] == -1) {
      _dfs(
        node,
        graph,
        bridges,
        articulationPoints,
        discovery,
        low,
        parent,
        children,
        time,
      );
    }
  }

  // Find connected components
  final connectedComponents = _findConnectedComponents(graph);

  // Calculate total edges
  int totalEdges = 0;
  for (final neighbors in graph.values) {
    totalEdges += neighbors.length;
  }
  totalEdges = totalEdges ~/ 2; // Undirected graph

  final basicResult = TarjansResult<T>(
    bridges: bridges,
    articulationPoints: articulationPoints,
  );

  return TarjansDetailedResult<T>(
    basicResult: basicResult,
    discoveryTimes: Map<T, int>.from(discovery),
    lowValues: Map<T, int>.from(low),
    parentNodes: Map<T, T?>.from(parent),
    childCounts: Map<T, int>.from(children),
    connectedComponents: connectedComponents,
    totalNodes: graph.length,
    totalEdges: totalEdges,
  );
}