Java example source code file (Graphs.java)

This example Java source code file (Graphs.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

annotation, endpoints, function, graph, map, mutablegraph, mutablenetwork, network, object, override, predicate, set, string, util

The Graphs.java Java example source code

/*
 * Copyright (C) 2014 The Guava 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 com.google.common.graph;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.graph.GraphConstants.ENDPOINTS_GRAPH_DIRECTEDNESS;
import static com.google.common.graph.GraphConstants.NETWORK_WITH_PARALLEL_EDGE;

import com.google.common.annotations.Beta;
import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.errorprone.annotations.CanIgnoreReturnValue;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import javax.annotation.Nullable;

/**
 * Static utility methods for {@link Graph} instances.
 *
 * @author Joshua O'Madadhain
 * @since 20.0
 */
@Beta
public final class Graphs {

  private static final String GRAPH_FORMAT = "%s, nodes: %s, edges: %s";
  private static final String DIRECTED_FORMAT = "<%s -> %s>";
  private static final String UNDIRECTED_FORMAT = "[%s, %s]";

  private Graphs() {}

  /**
   * Returns the node at the other end of {@code edge} from {@code node}.
   *
   * @throws IllegalArgumentException if {@code edge} is not incident to {@code node}
   */
  public static <N> N oppositeNode(Network graph, Object edge, Object node) {
    checkNotNull(node, "node");
    Endpoints<N> endpoints = graph.incidentNodes(edge);
    if (node.equals(endpoints.nodeA())) {
      return endpoints.nodeB();
    } else {
      checkArgument(node.equals(endpoints.nodeB()),
          "Edge %s is not incident to node %s", edge, node);
      return endpoints.nodeA();
    }
  }

  /**
   * Returns the subset of nodes in {@code graph} that have no predecessors.
   *
   * <p>Note that in an undirected graph, this is equivalent to all isolated nodes.
   */
  public static <N> Set roots(final Graph graph) {
    return Sets.filter(graph.nodes(), new Predicate<N>() {
      @Override
      public boolean apply(N node) {
        return graph.predecessors(node).isEmpty();
      }
    });
  }

  /**
   * Returns an unmodifiable view of edges that are parallel to {@code edge}, i.e. the set of edges
   * that connect the same nodes in the same direction (if any). An edge is not parallel to itself.
   *
   * @throws IllegalArgumentException if {@code edge} is not present in {@code graph}
   */
  public static <N, E> Set parallelEdges(Network graph, Object edge) {
    Endpoints<N> endpoints = graph.incidentNodes(edge); // Verifies that edge is in graph
    if (!graph.allowsParallelEdges()) {
      return ImmutableSet.of();
    }
    return Sets.difference(graph.edgesConnecting(endpoints.nodeA(), endpoints.nodeB()),
        ImmutableSet.of(edge)); // An edge is not parallel to itself.
  }

  /**
   * Adds {@code edge} to {@code graph} with the specified {@code endpoints}.
   */
  @CanIgnoreReturnValue
  public static <N, E> boolean addEdge(MutableNetwork graph, E edge, Endpoints endpoints) {
    checkNotNull(graph, "graph");
    checkNotNull(edge, "edge");
    checkNotNull(endpoints, "endpoints");
    checkArgument(endpoints.isDirected() == graph.isDirected(),
        ENDPOINTS_GRAPH_DIRECTEDNESS, endpoints.isDirected(), graph.isDirected());
    return graph.addEdge(edge, endpoints.nodeA(), endpoints.nodeB());
  }

  /**
   * Creates a mutable copy of {@code graph}, using the same nodes.
   */
  public static <N> MutableGraph copyOf(Graph graph) {
    return copyOfInternal(
        graph,
        GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()),
        Predicates.alwaysTrue());
  }

  @SuppressWarnings("unchecked")
  private static <N> MutableGraph copyOfInternal(
      Graph<N> graph, GraphBuilder copyBuilder, Predicate nodePredicate) {
    checkNotNull(graph, "graph");
    checkNotNull(nodePredicate, "nodePredicate");
    // TODO(b/28087289): we can remove this restriction when Graph supports parallel edges
    checkArgument(!((graph instanceof Network) && ((Network<N, ?>) graph).allowsParallelEdges()),
        NETWORK_WITH_PARALLEL_EDGE);
    MutableGraph<N> copy = copyBuilder.build();

    for (N node : Sets.filter(graph.nodes(), nodePredicate)) {
      copy.addNode(node);
      for (N successor : Sets.filter(graph.successors(node), nodePredicate)) {
        // TODO(b/28087289): Ensure that multiplicity is preserved if parallel edges are supported.
        copy.addEdge(node, successor);
      }
    }

    return copy;
  }

  /**
   * Copies all nodes from {@code src} into {@code dest}.
   */
  public static <N> void copyNodes(Graph src, MutableGraph dest) {
    copyNodesInternal(src, dest, Predicates.alwaysTrue());
  }

  private static <N, E> void copyNodesInternal(
      Graph<N> src, MutableGraph dest, Predicate nodePredicate) {
    checkNotNull(src, "src");
    checkNotNull(dest, "dest");
    checkNotNull(nodePredicate, "nodePredicate");
    for (N node : Sets.filter(src.nodes(), nodePredicate)) {
      dest.addNode(node);
    }
  }

  /**
   * Creates a mutable copy of {@code graph}, using the same node and edge elements.
   */
  public static <N, E> MutableNetwork copyOf(Network graph) {
    return copyOfInternal(
        graph,
        NetworkBuilder.from(graph)
            .expectedNodeCount(graph.nodes().size())
            .expectedEdgeCount(graph.edges().size()),
        Predicates.alwaysTrue(),
        Predicates.alwaysTrue());
  }

  private static <N, E> MutableNetwork copyOfInternal(
      Network<N, E> graph,
      NetworkBuilder<N, E> copyBuilder,
      Predicate<? super N> nodePredicate,
      Predicate<? super E> edgePredicate) {
    checkNotNull(graph, "graph");
    checkNotNull(nodePredicate, "nodePredicate");
    checkNotNull(edgePredicate, "edgePredicate");
    MutableNetwork<N, E> copy = copyBuilder.build();

    copyNodesInternal(graph, copy, nodePredicate);
    copyEdgesInternal(graph, copy, edgePredicate);

    return copy;
  }

  /**
   * Copies all nodes from {@code src} into {@code dest}.
   */
  public static <N> void copyNodes(Graph src, MutableNetwork dest) {
    copyNodesInternal(src, dest, Predicates.alwaysTrue());
  }

  private static <N, E> void copyNodesInternal(
      Graph<N> src, MutableNetwork dest, Predicate nodePredicate) {
    checkNotNull(src, "src");
    checkNotNull(dest, "dest");
    checkNotNull(nodePredicate, "nodePredicate");
    for (N node : Sets.filter(src.nodes(), nodePredicate)) {
      dest.addNode(node);
    }
  }

  /**
   * Copies edges from {@code src} into {@code dest}.
   * <p>
   * This method DOES NOT copy over edges if their incident nodes are not already in {@code dest}.
   */
  public static <N, E> void copyEdges(Network src, MutableNetwork dest) {
    copyEdgesInternal(src, dest, Predicates.alwaysTrue());
  }

  private static <N, E> void copyEdgesInternal(
      Network<N, E> src, MutableNetwork dest, Predicate edgePredicate) {
    checkNotNull(src, "src");
    checkNotNull(dest, "dest");
    checkNotNull(edgePredicate, "edgePredicate");
    for (E edge : Sets.filter(src.edges(), edgePredicate)) {
      Endpoints<N> endpoints = src.incidentNodes(edge);
      if (dest.nodes().containsAll(endpoints)) {
        addEdge(dest, edge, endpoints);
      }
    }
  }

  /**
   * Returns true iff {@code graph1} and {@code graph2} have the same node connections.
   *
   * <p>Note: {@link Network} instances can only be equal to other {@link Network} instances.
   * In particular, {@link Graph}s that are not also {@link Network}s cannot be equal
   * to {@link Network}s.
   *
   * @see Network#equals(Object)
   */
  public static boolean equal(@Nullable Graph<?> graph1, @Nullable Graph graph2) {
    // If both graphs are Network instances, use equal(Network, Network) instead
    if (graph1 instanceof Network && graph2 instanceof Network) {
      return equal((Network<?, ?>) graph1, (Network) graph2);
    }

    // Otherwise, if either graph is a Network (but not both), they can't be equal.
    if (graph1 instanceof Network || graph2 instanceof Network) {
      return false;
    }

    if (graph1 == graph2) {
      return true;
    }

    if (graph1 == null || graph2 == null) {
      return false;
    }

    if (!graph1.nodes().equals(graph2.nodes())) {
      return false;
    }

    for (Object node : graph1.nodes()) {
      if (!graph1.successors(node).equals(graph2.successors(node))) {
        return false;
      }
      boolean bothUndirected = !graph1.isDirected() && !graph2.isDirected();
      if (!bothUndirected && !graph1.predecessors(node).equals(graph2.predecessors(node))) {
        return false;
      }
    }

    return true;
  }

  /**
   * Returns true iff {@code graph1} and {@code graph2} have the same node/edge relationships.
   *
   * @see Network#equals(Object)
   */
  public static boolean equal(@Nullable Network<?, ?> graph1, @Nullable Network graph2) {
    if (graph1 == graph2) {
      return true;
    }

    if (graph1 == null || graph2 == null) {
      return false;
    }

    if (graph1.edges().size() != graph2.edges().size()) {
      return false;
    }

    if (!graph1.nodes().equals(graph2.nodes())) {
      return false;
    }

    for (Object node : graph1.nodes()) {
      if (!graph1.inEdges(node).equals(graph2.inEdges(node))) {
        return false;
      }
      boolean bothUndirected = !graph1.isDirected() && !graph2.isDirected();
      if (!bothUndirected && !graph1.outEdges(node).equals(graph2.outEdges(node))) {
        return false;
      }
    }

    return true;
  }

  /**
   * Returns the hash code of {@code graph}.
   *
   * @see Graph#hashCode()
   */
  public static int hashCode(Graph<?> graph) {
    if (graph instanceof Network) {
      return hashCode((Network<?, ?>) graph);
    }
    return nodeToAdjacentNodes(graph).hashCode();
  }

  /**
   * Returns the hash code of {@code graph}.
   *
   * @see Network#hashCode()
   */
  public static int hashCode(Network<?, ?> graph) {
    return nodeToIncidentEdges(graph).hashCode();
  }

  /**
   * Returns a string representation of {@code graph}. Encodes edge direction if {@code graph}
   * is directed.
   */
  public static String toString(Graph<?> graph) {
    if (graph instanceof Network) {
      return toString((Network<?, ?>) graph);
    }
    return String.format(GRAPH_FORMAT,
        getPropertiesString(graph),
        graph.nodes(),
        adjacentNodesString(graph));
  }

  /**
   * Returns a string representation of {@code graph}. Encodes edge direction if {@code graph}
   * is directed.
   */
  public static String toString(Network<?, ?> graph) {
    return String.format(GRAPH_FORMAT,
        getPropertiesString(graph),
        graph.nodes(),
        Maps.asMap(graph.edges(), edgeToIncidentNodesString(graph)));
  }

  /**
   * Returns a String of the adjacent node relationships for {@code graph}.
   */
  private static <N> String adjacentNodesString(final Graph graph) {
    checkNotNull(graph, "graph");
    List<String> adjacencies = new ArrayList();
    // This will list each undirected edge twice (once as [n1, n2] and once as [n2, n1]); this is OK
    for (N node : graph.nodes()) {
      for (N successor : graph.successors(node)) {
        adjacencies.add(
            String.format(
                graph.isDirected() ? DIRECTED_FORMAT : UNDIRECTED_FORMAT,
                node, successor));
      }
    }

    return String.format("{%s}", Joiner.on(", ").join(adjacencies));
  }

  /**
   * Returns a map that is a live view of {@code graph}, with nodes as keys
   * and the set of incident edges as values.
   */
  private static <N, E> Map> nodeToIncidentEdges(final Network graph) {
    checkNotNull(graph, "graph");
    return Maps.asMap(graph.nodes(), new Function<N, Set() {
      @Override
      public Set<E> apply(N node) {
        return graph.incidentEdges(node);
      }
    });
  }

  /**
   * Returns a map that is a live view of {@code graph}, with nodes as keys
   * and the set of adjacent nodes as values.
   */
  private static <N> Map> nodeToAdjacentNodes(final Graph graph) {
    checkNotNull(graph, "graph");
    return Maps.asMap(graph.nodes(), new Function<N, Set() {
      @Override
      public Set<N> apply(N node) {
        return graph.adjacentNodes(node);
      }
    });
  }

  /**
   * Returns a function that transforms an edge into a string representation of its incident nodes
   * in {@code graph}. The function's {@code apply} method will throw an
   * {@link IllegalArgumentException} if {@code graph} does not contain {@code edge}.
   */
  private static Function<Object, String> edgeToIncidentNodesString(final Network graph) {
    checkNotNull(graph, "graph");
    return new Function<Object, String>() {
      @Override
      public String apply(Object edge) {
        return graph.incidentNodes(edge).toString();
      }
    };
 }

  /**
   * Returns a string representation of the properties of {@code graph}.
   */
  // TODO(b/28087289): add allowsParallelEdges() once that's supported
  private static String getPropertiesString(Graph<?> graph) {
    if (graph instanceof Network) {
      return getPropertiesString((Network<?, ?>) graph);
    }
    return String.format("isDirected: %s, allowsSelfLoops: %s",
        graph.isDirected(), graph.allowsSelfLoops());
  }

  /**
   * Returns a string representation of the properties of {@code graph}.
   */
  private static String getPropertiesString(Network<?, ?> graph) {
    return String.format("isDirected: %s, allowsParallelEdges: %s, allowsSelfLoops: %s",
        graph.isDirected(), graph.allowsParallelEdges(), graph.allowsSelfLoops());
  }
}