java/dagger/internal/codegen/DaggerGraphs.java

/*
 * Copyright (C) 2018 The Dagger Authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package dagger.internal.codegen;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.graph.SuccessorsFunction;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/** Utility methods for {@link com.google.common.graph} types. */
final class DaggerGraphs {
  /**
   * Returns a shortest path from {@code nodeU} to {@code nodeV} in {@code graph} as a list of the
   * nodes visited in sequence, including both {@code nodeU} and {@code nodeV}. (Note that there may
   * be many possible shortest paths.)
   *
   * <p>If {@code nodeV} is not {@link
   * com.google.common.graph.Graphs#reachableNodes(com.google.common.graph.Graph, Object) reachable}
   * from {@code nodeU}, the list returned is empty.
   *
   * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not present in {@code
   *     graph}
   */
  static <N> ImmutableList<N> shortestPath(SuccessorsFunction<N> graph, N nodeU, N nodeV) {
    if (nodeU.equals(nodeV)) {
      return ImmutableList.of(nodeU);
    }
    Set<N> successors = ImmutableSet.copyOf(graph.successors(nodeU));
    if (successors.contains(nodeV)) {
      return ImmutableList.of(nodeU, nodeV);
    }

    Map<N, N> visitedNodeToPathPredecessor = new HashMap<>(); // encodes shortest path tree
    for (N node : successors) {
      visitedNodeToPathPredecessor.put(node, nodeU);
    }
    Queue<N> currentNodes = new ArrayDeque<N>(successors);
    Queue<N> nextNodes = new ArrayDeque<N>();

    // Perform a breadth-first traversal starting with the successors of nodeU.
    while (!currentNodes.isEmpty()) {
      while (!currentNodes.isEmpty()) {
        N currentNode = currentNodes.remove();
        for (N nextNode : graph.successors(currentNode)) {
          if (visitedNodeToPathPredecessor.containsKey(nextNode)) {
            continue; // we already have a shortest path to nextNode
          }
          visitedNodeToPathPredecessor.put(nextNode, currentNode);
          if (nextNode.equals(nodeV)) {
            ImmutableList.Builder<N> builder = ImmutableList.builder();
            N node = nodeV;
            builder.add(node);
            while (!node.equals(nodeU)) {
              node = visitedNodeToPathPredecessor.get(node);
              builder.add(node);
            }
            return builder.build().reverse();
          }
          nextNodes.add(nextNode);
        }
      }
      Queue<N> emptyQueue = currentNodes;
      currentNodes = nextNodes;
      nextNodes = emptyQueue; // reusing empty queue faster than allocating new one
    }

    return ImmutableList.of();
  }

  private DaggerGraphs() {}
}