content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you 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 org.apache.calcite.util.graph;
  
  import org.apache.calcite.util.Pair;
  
  import com.google.common.collect.ImmutableList;
  
  import java.util.AbstractList;
  import java.util.ArrayList;
  import java.util.Comparator;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  import static java.util.Objects.requireNonNull;
  
  /**
   * Miscellaneous graph utilities.
   */
  public class Graphs {
    private Graphs() {
    }
  
    public static <V, E extends DefaultEdge> List<V> predecessorListOf(
        DirectedGraph<V, E> graph, V vertex) {
      final List<E> edges = graph.getInwardEdges(vertex);
      return new AbstractList<V>() {
        @Override public V get(int index) {
          //noinspection unchecked
          return (V) edges.get(index).source;
        }
  
        @Override public int size() {
          return edges.size();
        }
      };
    }
  
    /** Returns a map of the shortest paths between any pair of nodes. */
    public static <V, E extends DefaultEdge> FrozenGraph<V, E> makeImmutable(
        DirectedGraph<V, E> graph) {
      DefaultDirectedGraph<V, E> graph1 = (DefaultDirectedGraph<V, E>) graph;
      Map<Pair<V, V>, int[]> shortestDistances = new HashMap<>();
      for (DefaultDirectedGraph.VertexInfo<V, E> arc
          : graph1.vertexMap.values()) {
        for (E edge : arc.outEdges) {
          final V source = graph1.source(edge);
          final V target = graph1.target(edge);
          shortestDistances.put(Pair.of(source, target), new int[] {1});
        }
      }
      while (true) {
        // Take a copy of the map's keys to avoid
        // ConcurrentModificationExceptions.
        final List<Pair<V, V>> previous =
            ImmutableList.copyOf(shortestDistances.keySet());
        boolean changed = false;
        for (E edge : graph.edgeSet()) {
          for (Pair<V, V> edge2 : previous) {
            if (edge.target.equals(edge2.left)) {
              final Pair<V, V> key = Pair.of(graph1.source(edge), edge2.right);
              int[] bestDistance = shortestDistances.get(key);
              int[] arc2Distance =
                  requireNonNull(shortestDistances.get(edge2),
                      () -> "shortestDistances.get(edge2) for " + edge2);
              if ((bestDistance == null)
                  || (bestDistance[0] > (arc2Distance[0] + 1))) {
                shortestDistances.put(key, new int[] {arc2Distance[0] + 1});
                changed = true;
              }
            }
          }
        }
        if (!changed) {
          break;
        }
      }
      return new FrozenGraph<>(graph1, shortestDistances);
    }
  
    /**
     * Immutable grap.
     *
     * @param <V> Vertex type
     * @param <E> Edge type
     */
    public static class FrozenGraph<V extends Object, E extends DefaultEdge> {
      private final DefaultDirectedGraph<V, E> graph;
      private final Map<Pair<V, V>, int[]> shortestDistances;
  
      /** Creates a frozen graph as a copy of another graph. */
      FrozenGraph(DefaultDirectedGraph<V, E> graph,
          Map<Pair<V, V>, int[]> shortestDistances) {
        this.graph = graph;
        this.shortestDistances = shortestDistances;
      }
  
      /**
       * Returns an iterator of all paths between two nodes,
       * in non-decreasing order of path lengths.
       *
       * <p>The current implementation is not optimal.
       */
      public List<List<V>> getPaths(V from, V to) {
        List<List<V>> list = new ArrayList<>();
        if (from.equals(to)) {
          list.add(ImmutableList.of(from));
        }
        findPaths(from, to, list);
        list.sort(Comparator.comparingInt(List::size));
        return list;
      }
  
      /**
       * Returns the shortest distance between two points, -1, if there is no path.
       *
       * @param from From
       * @param to To
       * @return The shortest distance, -1, if there is no path.
       */
      public int getShortestDistance(V from, V to) {
        if (from.equals(to)) {
          return 0;
        }
        int[] distance = shortestDistances.get(Pair.of(from, to));
        return distance == null ? -1 : distance[0];
      }
  
      private void findPaths(V from, V to, List<List<V>> list) {
        if (getShortestDistance(from, to) == -1) {
          return;
        }
  //      final E edge = graph.getEdge(from, to);
  //      if (edge != null) {
  //        list.add(ImmutableList.of(from, to));
  //      }
        final List<V> prefix = new ArrayList<>();
        prefix.add(from);
        findPathsExcluding(from, to, list, new HashSet<>(), prefix);
      }
  
      /**
       * Finds all paths from "from" to "to" of length 2 or greater, such that the
       * intermediate nodes are not contained in "excludedNodes".
       */
      private void findPathsExcluding(V from, V to, List<List<V>> list,
          Set<V> excludedNodes, List<V> prefix) {
        excludedNodes.add(from);
        for (E edge : graph.edges) {
          if (edge.source.equals(from)) {
            final V target = graph.target(edge);
            if (target.equals(to)) {
              // We found a path.
              prefix.add(target);
              list.add(ImmutableList.copyOf(prefix));
              prefix.remove(prefix.size() - 1);
            } else if (excludedNodes.contains(target)) {
              // ignore it
            } else {
              prefix.add(target);
              findPathsExcluding(target, to, list, excludedNodes, prefix);
              prefix.remove(prefix.size() - 1);
            }
          }
        }
        excludedNodes.remove(from);
      }
    }
  }
  