blob: 105b170b66249e0b52e75ee8278ba237ebfc0cab [file] [log] [blame]
 // Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file // for details. All rights reserved. Use of this source code is governed by a // BSD-style license that can be found in the LICENSE.md file. library fasta.graph; import 'dart:math'; import '../ast.dart'; abstract class Graph { Iterable get vertices; Iterable neighborsOf(T vertex); } /// [Graph] implementation using a collection of [Library] nodes as the graph /// vertices and using library dependencies to compute neighbors. /// /// If [coreLibrary] is provided, it will be included in the neighbor of all /// vertices. Otherwise, `dart:core` will only be neighboring libraries that /// explicitly dependent on it. class LibraryGraph implements Graph { final Iterable libraries; final Library? coreLibrary; LibraryGraph(this.libraries, {this.coreLibrary}); @override Iterable get vertices => libraries; @override Iterable neighborsOf(Library library) sync* { if (coreLibrary != null && library != coreLibrary) { yield coreLibrary!; } for (LibraryDependency dependency in library.dependencies) { yield dependency.targetLibrary; } } } /// Computes the strongly connected components of [graph]. /// /// This implementation is based on [Dijkstra's path-based strong component /// algorithm] /// (https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm#Description). List> computeStrongComponents(Graph graph) { List> result = >[]; int count = 0; Map preorderNumbers = {}; List unassigned = []; List candidates = []; Set assigned = new Set(); void recursivelySearch(T vertex) { // Step 1: Set the preorder number of [vertex] to [count], and increment // [count]. preorderNumbers[vertex] = count++; // Step 2: Push [vertex] onto [unassigned] and also onto [candidates]. unassigned.add(vertex); candidates.add(vertex); // Step 3: For each edge from [vertex] to a neighboring vertex [neighbor]: for (T neighbor in graph.neighborsOf(vertex)) { int? neighborPreorderNumber = preorderNumbers[neighbor]; if (neighborPreorderNumber == null) { // If the preorder number of [neighbor] has not yet been assigned, // recursively search [neighbor]; recursivelySearch(neighbor); } else if (!assigned.contains(neighbor)) { // Otherwise, if [neighbor] has not yet been assigned to a strongly // connected component: // // * Repeatedly pop vertices from [candidates] until the top element of // [candidates] has a preorder number less than or equal to the // preorder number of [neighbor]. while (preorderNumbers[candidates.last]! > neighborPreorderNumber) { candidates.removeLast(); } } } // Step 4: If [vertex] is the top element of [candidates]: if (candidates.last == vertex) { // Pop vertices from [unassigned] until [vertex] has been popped, and // assign the popped vertices to a new component. List component = []; while (true) { T top = unassigned.removeLast(); component.add(top); assigned.add(top); if (top == vertex) break; } result.add(component); // Pop [vertex] from [candidates]. candidates.removeLast(); } } for (T vertex in graph.vertices) { if (preorderNumbers[vertex] == null) { recursivelySearch(vertex); } } return result; } /// A [Graph] using strongly connected components, as computed by /// [computeStrongComponents], as vertices. Neighbors are computed using the /// neighbors of the provided [subgraph] which was used to compute the strongly /// connected components. class StrongComponentGraph implements Graph> { final Graph subgraph; final List> components; final Map> _elementToComponentMap = {}; final Map, Set>> _neighborsMap = {}; StrongComponentGraph(this.subgraph, this.components) { for (List component in components) { for (T element in component) { _elementToComponentMap[element] = component; } } } Set> _computeNeighborsOf(List component) { Set> neighbors = {}; for (T element in component) { for (T neighborElement in subgraph.neighborsOf(element)) { List neighborComponent = _elementToComponentMap[neighborElement]!; if (component != neighborComponent) { neighbors.add(neighborComponent); } } } return neighbors; } @override Iterable> neighborsOf(List vertex) { return _neighborsMap[vertex] ??= _computeNeighborsOf(vertex); } @override Iterable> get vertices => components; } const int cyclicMarker = -1; int _topologicalSortInternal( Graph graph, TopologicalSortResult result, T vertex) { int? index = result.indexMap[vertex]; if (index == null) { result.indexMap[vertex] = cyclicMarker; int index = 0; for (T neighbor in graph.neighborsOf(vertex)) { int neighborIndex = _topologicalSortInternal(graph, result, neighbor); if (neighborIndex == cyclicMarker) { result.cyclicVertices.add(vertex); return cyclicMarker; } else { index = max(index, neighborIndex + 1); } } result.sortedVertices.add(vertex); if (index >= result.layers.length) { assert(index == result.layers.length); result.layers.add([vertex]); } else { result.layers[index].add(vertex); } return result.indexMap[vertex] = index; } return index; } /// Perform a topological sorting of the vertices in [graph], returning a /// [TopologicalSortResult] object with the result. TopologicalSortResult topologicalSort(Graph graph) { TopologicalSortResult result = new TopologicalSortResult(); for (T vertex in graph.vertices) { _topologicalSortInternal(graph, result, vertex); } return result; } /// The result of computing the [topologicalSort] on a [Graph]. class TopologicalSortResult { /// The non-cyclic vertices of the graph sorted in topological order. final List sortedVertices = []; /// The cyclic vertices of graph, including vertices that have a path to /// a vertex. final List cyclicVertices = []; /// The topological index of all non-cyclic vertices of the graph. /// /// The "topological index" of a vertex is the length of the longest path /// through neighbors. For vertices with no neighbors, the index is 0. /// For any other vertex, it is 1 plus max of the index of its neighbors. final Map indexMap = {}; /// The non-cyclic vertices in layers according to their topological index. /// That is, `layers[i]` contain the list of vertices with index `i`. final List> layers = []; }