| /******************************************************************************* |
| * Copyright (c) 2000, 2016 IBM Corporation and others. |
| * |
| * This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License 2.0 |
| * which accompanies this distribution, and is available at |
| * https://www.eclipse.org/legal/epl-2.0/ |
| * |
| * SPDX-License-Identifier: EPL-2.0 |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| * Broadcom Corporation - ongoing development |
| * Lars Vogel <Lars.Vogel@vogella.com> - Bug 473427 |
| * Mickael Istria (Red Hat Inc.) - Bug 488937 |
| *******************************************************************************/ |
| package org.eclipse.core.internal.resources; |
| |
| import java.lang.reflect.Array; |
| import java.util.*; |
| import java.util.function.Function; |
| import java.util.function.Predicate; |
| import org.eclipse.core.internal.resources.ComputeProjectOrder.Digraph.Vertex; |
| import org.eclipse.core.runtime.Assert; |
| |
| /** |
| * Implementation of a sort algorithm for computing the order of vertexes that are part |
| * of a reference graph. This algorithm handles cycles in the graph in a reasonable way. |
| * In 3.7 this class was enhanced to support computing order of a graph containing an |
| * arbitrary type. |
| * |
| * @since 2.1 |
| */ |
| public class ComputeProjectOrder { |
| |
| /* |
| * Prevent class from being instantiated. |
| */ |
| private ComputeProjectOrder() { |
| // not allowed |
| } |
| |
| /** |
| * A directed graph. Once the vertexes and edges of the graph have been |
| * defined, the graph can be queried for the depth-first finish time of each |
| * vertex. |
| * <p> |
| * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>, |
| * McGraw-Hill, 1990. The depth-first search algorithm is in section 23.3. |
| * </p> |
| */ |
| public static class Digraph<T> { |
| /** |
| * struct-like object for representing a vertex along with various |
| * values computed during depth-first search (DFS). |
| */ |
| public static class Vertex<T> { |
| /** |
| * White is for marking vertexes as unvisited. |
| */ |
| public static final String WHITE = "white"; //$NON-NLS-1$ |
| |
| /** |
| * Grey is for marking vertexes as discovered but visit not yet |
| * finished. |
| */ |
| public static final String GREY = "grey"; //$NON-NLS-1$ |
| |
| /** |
| * Black is for marking vertexes as visited. |
| */ |
| public static final String BLACK = "black"; //$NON-NLS-1$ |
| |
| /** |
| * Color of the vertex. One of <code>WHITE</code> (unvisited), |
| * <code>GREY</code> (visit in progress), or <code>BLACK</code> |
| * (visit finished). <code>WHITE</code> initially. |
| */ |
| public String color = WHITE; |
| |
| /** |
| * The DFS predecessor vertex, or <code>null</code> if there is no |
| * predecessor. <code>null</code> initially. |
| */ |
| public Vertex<T> predecessor = null; |
| |
| /** |
| * Timestamp indicating when the vertex was finished (became BLACK) |
| * in the DFS. Finish times are between 1 and the number of |
| * vertexes. |
| */ |
| public int finishTime; |
| |
| /** |
| * The id of this vertex. |
| */ |
| public T id; |
| |
| /** |
| * Ordered list of adjacent vertexes. In other words, "this" is the |
| * "from" vertex and the elements of this list are all "to" |
| * vertexes. |
| * |
| * Element type: <code>Vertex</code> |
| */ |
| public List<Vertex<T>> adjacent = new ArrayList<>(3); |
| |
| /** |
| * Creates a new vertex with the given id. |
| * |
| * @param id the vertex id |
| */ |
| public Vertex(T id) { |
| this.id = id; |
| } |
| } |
| |
| public static class Edge<T> { |
| public final T from; |
| public final T to; |
| |
| public Edge(T from, T to) { |
| this.from = from; |
| this.to = to; |
| } |
| |
| @Override |
| public boolean equals(Object obj) { |
| if (!(obj instanceof Edge)) { |
| return false; |
| } |
| Edge<?> other = (Edge<?>) obj; |
| return Objects.equals(this.from, other.from) && Objects.equals(this.to, other.to); |
| } |
| |
| @Override |
| public int hashCode() { |
| return Objects.hash(this.from, this.to); |
| } |
| |
| @Override |
| public String toString() { |
| return from + " -> " + to; //$NON-NLS-1$ |
| } |
| |
| } |
| |
| /** |
| * Ordered list of all vertexes in this graph. |
| * |
| * Element type: <code>Vertex</code> |
| */ |
| public final List<Vertex<T>> vertexList = new ArrayList<>(100); |
| |
| /** |
| * Map from id to vertex. |
| * |
| * Key type: <code>T</code>; value type: <code>Vertex</code> |
| */ |
| public final Map<T, Vertex<T>> vertexMap = new LinkedHashMap<>(100); |
| |
| /** |
| * DFS visit time. Non-negative. |
| */ |
| private int time; |
| |
| /** |
| * Indicates whether the graph has been initialized. Initially |
| * <code>false</code>. |
| */ |
| private boolean initialized = false; |
| |
| /** |
| * Indicates whether the graph contains cycles. Initially |
| * <code>false</code>. |
| */ |
| private boolean cycles = false; |
| |
| private Class<T> clazz; |
| |
| /** |
| * Creates a new empty directed graph object. |
| * <p> |
| * After this graph's vertexes and edges are defined with |
| * <code>addVertex</code> and <code>addEdge</code>, call |
| * <code>freeze</code> to indicate that the graph is all there, and then |
| * call <code>idsByDFSFinishTime</code> to read off the vertexes ordered |
| * by DFS finish time. |
| * </p> |
| */ |
| public Digraph(Class<T> clazz) { |
| super(); |
| this.clazz = clazz; |
| } |
| |
| /** |
| * Freezes this graph. No more vertexes or edges can be added to this |
| * graph after this method is called. Has no effect if the graph is |
| * already frozen. |
| */ |
| public void freeze() { |
| if (!initialized) { |
| initialized = true; |
| // only perform depth-first-search once |
| DFS(); |
| } |
| } |
| |
| /** |
| * Defines a new vertex with the given id. The depth-first search is |
| * performed in the relative order in which vertexes were added to the |
| * graph. |
| * |
| * @param id the id of the vertex |
| * @exception IllegalArgumentException if the vertex id is |
| * already defined or if the graph is frozen |
| */ |
| public void addVertex(T id) throws IllegalArgumentException { |
| if (initialized) { |
| throw new IllegalArgumentException(); |
| } |
| Vertex<T> vertex = new Vertex<>(id); |
| Vertex<T> existing = vertexMap.put(id, vertex); |
| // nip problems with duplicate vertexes in the bud |
| if (existing != null) { |
| throw new IllegalArgumentException(); |
| } |
| vertexList.add(vertex); |
| } |
| |
| /** |
| * Adds a new directed edge between the vertexes with the given ids. |
| * Vertexes for the given ids must be defined beforehand with |
| * <code>addVertex</code>. The depth-first search is performed in the |
| * relative order in which adjacent "to" vertexes were added to a given |
| * "from" index. |
| * |
| * @param fromId the id of the "from" vertex |
| * @param toId the id of the "to" vertex |
| * @exception IllegalArgumentException if either vertex is undefined or |
| * if the graph is frozen |
| */ |
| public void addEdge(T fromId, T toId) throws IllegalArgumentException { |
| if (initialized) { |
| throw new IllegalArgumentException(); |
| } |
| Vertex<T> fromVertex = vertexMap.get(fromId); |
| Vertex<T> toVertex = vertexMap.get(toId); |
| // nip problems with bogus vertexes in the bud |
| if (fromVertex == null) { |
| throw new IllegalArgumentException(); |
| } |
| if (toVertex == null) { |
| throw new IllegalArgumentException(); |
| } |
| fromVertex.adjacent.add(toVertex); |
| } |
| |
| /** |
| * Returns the ids of the vertexes in this graph ordered by depth-first |
| * search finish time. The graph must be frozen. |
| * |
| * @param increasing <code>true</code> if objects are to be arranged |
| * into increasing order of depth-first search finish time, and |
| * <code>false</code> if objects are to be arranged into decreasing |
| * order of depth-first search finish time |
| * @return the list of ids ordered by depth-first search finish time |
| * (element type: <code>Object</code>) |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| public List<T> idsByDFSFinishTime(boolean increasing) { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| int len = vertexList.size(); |
| @SuppressWarnings("unchecked") |
| T[] r = (T[]) Array.newInstance(clazz, len); |
| for (Vertex<T> vertex : vertexList) { |
| int f = vertex.finishTime; |
| // note that finish times start at 1, not 0 |
| if (increasing) { |
| r[f - 1] = vertex.id; |
| } else { |
| r[len - f] = vertex.id; |
| } |
| } |
| return Arrays.asList(r); |
| } |
| |
| /** |
| * Returns whether the graph contains cycles. The graph must be frozen. |
| * |
| * @return <code>true</code> if this graph contains at least one cycle, |
| * and <code>false</code> if this graph is cycle free |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| public boolean containsCycles() { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| return cycles; |
| } |
| |
| /** |
| * Returns the non-trivial components of this graph. A non-trivial |
| * component is a set of 2 or more vertexes that were traversed |
| * together. The graph must be frozen. |
| * |
| * @return the possibly empty list of non-trivial components, where |
| * each component is an array of ids (element type: |
| * <code>Object[]</code>) |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| @SuppressWarnings("unchecked") |
| public List<T[]> nonTrivialComponents() { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| // find the roots of each component |
| // Map<Vertex,List<Object>> components |
| Map<Vertex<T>, List<T>> components = new LinkedHashMap<>(); |
| for (Vertex<T> vertex : vertexList) { |
| if (vertex.predecessor == null) { |
| // this vertex is the root of a component |
| // if component is non-trivial we will hit a child |
| } else { |
| // find the root ancestor of this vertex |
| Vertex<T> root = vertex; |
| while (root.predecessor != null) { |
| root = root.predecessor; |
| } |
| List<T> component = components.get(root); |
| if (component == null) { |
| component = new ArrayList<>(2); |
| component.add(root.id); |
| components.put(root, component); |
| } |
| component.add(vertex.id); |
| } |
| } |
| List<T[]> result = new ArrayList<>(components.size()); |
| for (List<T> component : components.values()) { |
| if (component.size() > 1) { |
| result.add(component.toArray((T[]) Array.newInstance(clazz, component.size()))); |
| } |
| } |
| return result; |
| } |
| |
| // /** |
| // * Performs a depth-first search of this graph and records interesting |
| // * info with each vertex, including DFS finish time. Employs a recursive |
| // * helper method <code>DFSVisit</code>. |
| // * <p> |
| // * Although this method is not used, it is the basis of the |
| // * non-recursive <code>DFS</code> method. |
| // * </p> |
| // */ |
| // private void recursiveDFS() { |
| // // initialize |
| // // all vertex.color initially Vertex.WHITE; |
| // // all vertex.predecessor initially null; |
| // time = 0; |
| // for (Iterator allV = vertexList.iterator(); allV.hasNext();) { |
| // Vertex nextVertex = (Vertex) allV.next(); |
| // if (nextVertex.color == Vertex.WHITE) { |
| // DFSVisit(nextVertex); |
| // } |
| // } |
| // } |
| // |
| // /** |
| // * Helper method. Performs a depth first search of this graph. |
| // * |
| // * @param vertex the vertex to visit |
| // */ |
| // private void DFSVisit(Vertex vertex) { |
| // // mark vertex as discovered |
| // vertex.color = Vertex.GREY; |
| // List adj = vertex.adjacent; |
| // for (Iterator allAdjacent=adj.iterator(); allAdjacent.hasNext();) { |
| // Vertex adjVertex = (Vertex) allAdjacent.next(); |
| // if (adjVertex.color == Vertex.WHITE) { |
| // // explore edge from vertex to adjVertex |
| // adjVertex.predecessor = vertex; |
| // DFSVisit(adjVertex); |
| // } else if (adjVertex.color == Vertex.GREY) { |
| // // back edge (grey vertex means visit in progress) |
| // cycles = true; |
| // } |
| // } |
| // // done exploring vertex |
| // vertex.color = Vertex.BLACK; |
| // time++; |
| // vertex.finishTime = time; |
| // } |
| |
| /** |
| * Performs a depth-first search of this graph and records interesting |
| * info with each vertex, including DFS finish time. Does not employ |
| * recursion. |
| */ |
| @SuppressWarnings({"unchecked"}) |
| private void DFS() { |
| // state machine rendition of the standard recursive DFS algorithm |
| int state; |
| final int NEXT_VERTEX = 1; |
| final int START_DFS_VISIT = 2; |
| final int NEXT_ADJACENT = 3; |
| final int AFTER_NEXTED_DFS_VISIT = 4; |
| // use precomputed objects to avoid garbage |
| final Integer NEXT_VERTEX_OBJECT = NEXT_VERTEX; |
| final Integer AFTER_NEXTED_DFS_VISIT_OBJECT = AFTER_NEXTED_DFS_VISIT; |
| // initialize |
| // all vertex.color initially Vertex.WHITE; |
| // all vertex.predecessor initially null; |
| time = 0; |
| // for a stack, append to the end of an array-based list |
| List<Object> stack = new ArrayList<>(Math.max(1, vertexList.size())); |
| Iterator<Vertex<T>> allAdjacent = null; |
| Vertex<T> vertex = null; |
| Iterator<Vertex<T>> allV = vertexList.iterator(); |
| state = NEXT_VERTEX; |
| nextStateLoop: while (true) { |
| switch (state) { |
| case NEXT_VERTEX : |
| // on entry, "allV" contains vertexes yet to be visited |
| if (!allV.hasNext()) { |
| // all done |
| break nextStateLoop; |
| } |
| Vertex<T> nextVertex = allV.next(); |
| if (nextVertex.color == Vertex.WHITE) { |
| stack.add(NEXT_VERTEX_OBJECT); |
| vertex = nextVertex; |
| state = START_DFS_VISIT; |
| continue nextStateLoop; |
| } |
| //else |
| state = NEXT_VERTEX; |
| continue nextStateLoop; |
| case START_DFS_VISIT : |
| // on entry, "vertex" contains the vertex to be visited |
| // top of stack is return code |
| // mark the vertex as discovered |
| vertex.color = Vertex.GREY; |
| allAdjacent = vertex.adjacent.iterator(); |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| case NEXT_ADJACENT : |
| // on entry, "allAdjacent" contains adjacent vertexes to |
| // be visited; "vertex" contains vertex being visited |
| if (allAdjacent.hasNext()) { |
| Vertex<T> adjVertex = allAdjacent.next(); |
| if (adjVertex.color == Vertex.WHITE) { |
| // explore edge from vertex to adjVertex |
| adjVertex.predecessor = vertex; |
| stack.add(allAdjacent); |
| stack.add(vertex); |
| stack.add(AFTER_NEXTED_DFS_VISIT_OBJECT); |
| vertex = adjVertex; |
| state = START_DFS_VISIT; |
| continue nextStateLoop; |
| } |
| if (adjVertex.color == Vertex.GREY) { |
| // back edge (grey means visit in progress) |
| cycles = true; |
| } |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| } |
| //else done exploring vertex |
| vertex.color = Vertex.BLACK; |
| time++; |
| vertex.finishTime = time; |
| state = ((Integer) stack.remove(stack.size() - 1)).intValue(); |
| continue nextStateLoop; |
| case AFTER_NEXTED_DFS_VISIT : |
| // on entry, stack contains "vertex" and "allAjacent" |
| vertex = (Vertex<T>) stack.remove(stack.size() - 1); |
| allAdjacent = (Iterator<Vertex<T>>) stack.remove(stack.size() - 1); |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| } |
| } |
| } |
| |
| public Collection<Edge<T>> getEdges() { |
| int size = 0; |
| for (Vertex<T> vertex : vertexList) { |
| size += vertex.adjacent.size(); |
| } |
| Collection<Edge<T>> res = new LinkedHashSet<>(size, (float) 1.); |
| vertexList.forEach(vertex -> vertex.adjacent.forEach(adjacent -> res.add(new Edge<>(vertex.id, adjacent.id)))); |
| return res; |
| } |
| |
| } |
| |
| /** |
| * Data structure for holding the multi-part outcome of |
| * <code>ComputeVertexOrder.computeVertexOrder</code>. |
| */ |
| public static class VertexOrder<T> { |
| /** |
| * Creates an instance with the given values. |
| * @param vertexes initial value of <code>vertexes</code> field |
| * @param hasCycles initial value of <code>hasCycles</code> field |
| * @param knots initial value of <code>knots</code> field |
| */ |
| public VertexOrder(T[] vertexes, boolean hasCycles, T[][] knots) { |
| this.vertexes = vertexes; |
| this.hasCycles = hasCycles; |
| this.knots = knots; |
| } |
| |
| /** |
| * A list of vertexes ordered so as to honor the reference |
| * relationships between them wherever possible. |
| */ |
| public T[] vertexes; |
| /** |
| * <code>true</code> if any of the vertexes in <code>vertexes</code> |
| * are involved in non-trivial cycles in the reference graph. |
| */ |
| public boolean hasCycles; |
| /** |
| * A list of knots in the reference graph. This list is empty if |
| * the reference graph does not contain cycles. If the reference graph |
| * contains cycles, each element is a knot of two or more vertexes that |
| * are involved in a cycle of mutually dependent references. |
| */ |
| public T[][] knots; |
| } |
| |
| /** |
| * Sorts the given list of vertexes in a manner that honors the given |
| * reference relationships between them. That is, if A references |
| * B, then the resulting order will list B before A if possible. |
| * For graphs that do not contain cycles, the result is the same as a conventional |
| * topological sort. For graphs containing cycles, the order is based on |
| * ordering the strongly connected components of the graph. This has the |
| * effect of keeping each knot of vertexes together without otherwise |
| * affecting the order of vertexes not involved in a cycle. For a graph G, |
| * the algorithm performs in O(|G|) space and time. |
| * <p> |
| * When there is an arbitrary choice, vertexes are ordered as supplied. |
| * If there are no constraints on the order of the vertexes, they are returned |
| * in the reverse order of how they are supplied. |
| * </p> |
| * <p> Ref: Cormen, Leiserson, and Rivest <it>Introduction to |
| * Algorithms</it>, McGraw-Hill, 1990. The strongly-connected-components |
| * algorithm is in section 23.5. |
| * </p> |
| * |
| * @param vertexes a list of vertexes |
| * @param references a list of pairs [A,B] meaning that A references B |
| * @return an object describing the resulting order |
| */ |
| static <T> VertexOrder<T> computeVertexOrder(SortedSet<T> vertexes, List<T[]> references, Class<T> clazz) { |
| final Digraph<T> g1 = computeGraph(vertexes, references, clazz); |
| return computeVertexOrder(g1, clazz); |
| } |
| |
| @SuppressWarnings("unchecked") |
| public static <T> VertexOrder<T> computeVertexOrder(final Digraph<T> g1, Class<T> clazz) { |
| Assert.isNotNull(g1); |
| // Create the transposed graph. This time, define the vertexes |
| // in decreasing order of depth-first finish time in g1 |
| // interchange "to" and "from" to reverse edges from g1 |
| final Digraph<T> g2 = new Digraph<>(clazz); |
| // add vertexes |
| List<T> resortedVertexes = g1.idsByDFSFinishTime(false); |
| for (T object : resortedVertexes) { |
| g2.addVertex(object); |
| } |
| for (Vertex<T> vertex : g1.vertexList) { |
| for (Vertex<T> adjacent : vertex.adjacent) { |
| // N.B. this is the transposed graph |
| g2.addEdge(adjacent.id, vertex.id); |
| } |
| } |
| g2.freeze(); |
| |
| // Return the vertexes in increasing order of depth-first finish time in g2 |
| List<T> sortedVertexList = g2.idsByDFSFinishTime(true); |
| T[] orderedVertexes = (T[]) Array.newInstance(clazz, sortedVertexList.size()); |
| sortedVertexList.toArray(orderedVertexes); |
| T[][] knots; |
| boolean hasCycles = g2.containsCycles(); |
| if (hasCycles) { |
| List<T[]> knotList = g2.nonTrivialComponents(); |
| Class<?> arrayClass = Array.newInstance(clazz, 0).getClass(); |
| knots = (T[][]) Array.newInstance(arrayClass, knotList.size()); |
| knotList.toArray(knots); |
| } else { |
| knots = (T[][]) Array.newInstance(clazz, 0, 0); |
| } |
| return new VertexOrder<>(orderedVertexes, hasCycles, knots); |
| } |
| |
| /** |
| * Given a VertexOrder and a VertexFilter, remove all vertexes |
| * matching the filter from the ordering. |
| */ |
| @SuppressWarnings("unchecked") |
| static <T> VertexOrder<T> filterVertexOrder(VertexOrder<T> order, Predicate<T> filter, Class<T> clazz) { |
| // Optimize common case where nothing is to be filtered |
| // and cache the results of applying the filter |
| int filteredCount = 0; |
| boolean[] filterMatches = new boolean[order.vertexes.length]; |
| for (int i = 0; i < order.vertexes.length; i++) { |
| filterMatches[i] = filter.test(order.vertexes[i]); |
| if (filterMatches[i]) |
| filteredCount++; |
| } |
| |
| // No vertexes match the filter, so return the order unmodified |
| if (filteredCount == 0) { |
| return order; |
| } |
| |
| // Otherwise we need to eliminate mention of vertexes matching the filter |
| // from the list of vertexes |
| T[] reducedVertexes = (T[]) Array.newInstance(clazz, order.vertexes.length - filteredCount); |
| for (int i = 0, j = 0; i < order.vertexes.length; i++) { |
| if (!filterMatches[i]) { |
| reducedVertexes[j] = order.vertexes[i]; |
| j++; |
| } |
| } |
| |
| // and from the knots list |
| List<T[]> reducedKnots = new ArrayList<>(order.knots.length); |
| for (T[] knot : order.knots) { |
| List<T> knotList = new ArrayList<>(knot.length); |
| for (T vertex : knot) { |
| if (!filter.test(vertex)) { |
| knotList.add(vertex); |
| } |
| } |
| // Keep knots containing 2 or more vertexes in the specified subset |
| if (knotList.size() > 1) { |
| reducedKnots.add(knotList.toArray((T[]) Array.newInstance(clazz, knotList.size()))); |
| } |
| } |
| Class<?> arrayClass = Array.newInstance(clazz, 0).getClass(); |
| return new VertexOrder<>(reducedVertexes, reducedKnots.size() > 0, reducedKnots.toArray((T[][]) Array.newInstance(arrayClass, reducedKnots.size()))); |
| } |
| |
| public static <T> Digraph<T> computeGraph(Collection<T> vertexes, Collection<T[]> references, Class<T> clazz) { |
| final Digraph<T> g1 = new Digraph<>(clazz); |
| // add vertexes |
| for (T name : vertexes) { |
| g1.addVertex(name); |
| } |
| // add edges |
| for (T[] ref : references) { |
| if (ref.length != 2) { |
| throw new IllegalArgumentException(); |
| } |
| T p = ref[0]; |
| T q = ref[1]; |
| if (p == null || q == null) { |
| throw new IllegalArgumentException(); |
| } |
| // p has a reference to q |
| // therefore create an edge from q to p |
| // to cause q to come before p in eventual result |
| g1.addEdge(q, p); |
| } |
| g1.freeze(); |
| return g1; |
| } |
| |
| /** |
| * Builds a digraph excluding the nodes that do not match filter, but keeps transitive edges. Ie if A->B->C and B is removed, |
| * result would be A->C. |
| * |
| * Complexity is O(#edge + #vertex). It implements a dynamic recursive deep-first graph traversing algorithm to compute |
| * resutling edges. |
| * |
| * @param initialGraph |
| * @param filterOut a filter to exclude nodes. |
| * @param clazz |
| * @return the filtered graph. |
| */ |
| public static <T> Digraph<T> buildFilteredDigraph(Digraph<T> initialGraph, Predicate<T> filterOut, Class<T> clazz) { |
| Digraph<T> filteredGraph = new Digraph<>(clazz); |
| // build vertices |
| for (Vertex<T> vertex : initialGraph.vertexList) { |
| T id = vertex.id; |
| if (!filterOut.test(id)) { |
| filteredGraph.addVertex(id); |
| } |
| } |
| // Takes an id as input, and returns the nodes in the filteredGraph that are adjacent to this node |
| // so that if initial graph has A->B and B->C and B->D and B is removed, this function return C and D |
| // when invoked on A. |
| Function<T, Set<T>> computeAdjacents = new Function<T, Set<T>>() { |
| private Set<T> processing = new HashSet<>(); |
| // Store intermediary results to not repeat same computations with the same expected results |
| private Map<T, Set<T>> adjacentsMap = new HashMap<>(initialGraph.vertexList.size(), 1.f); |
| |
| @Override |
| public Set<T> apply(T id) { |
| if (adjacentsMap.containsKey(id)) { |
| return adjacentsMap.get(id); |
| } else if (processing.contains(id)) { |
| // in a cycle, skip processing as no new edge is to expect. |
| // But don't store result, return directly! |
| return Collections.emptySet(); |
| } |
| processing.add(id); |
| Set<T> resolvedAdjacents = new HashSet<>(); |
| initialGraph.vertexMap.get(id).adjacent.forEach(adjacent -> { |
| if (filteredGraph.vertexMap.keySet().contains(adjacent.id)) { |
| // adjacent in target graph, just take it. |
| resolvedAdjacents.add(adjacent.id); |
| } else { |
| // adjacent filtered out, take its resolved existing adjacents |
| resolvedAdjacents.addAll(apply(adjacent.id)); |
| } |
| }); |
| adjacentsMap.put(id, resolvedAdjacents); |
| processing.remove(id); |
| return resolvedAdjacents; |
| } |
| }; |
| filteredGraph.vertexMap.keySet().forEach(id -> { |
| computeAdjacents.apply(id).forEach(adjacent -> { |
| filteredGraph.addEdge(id, adjacent); |
| }); |
| }); |
| |
| return filteredGraph; |
| } |
| } |