001/*
002 * Copyright (C) 2016 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.graph;
018
019import static com.google.common.base.Preconditions.checkState;
020import static com.google.common.graph.GraphConstants.GRAPH_STRING_FORMAT;
021
022import com.google.common.annotations.Beta;
023import com.google.common.collect.UnmodifiableIterator;
024import com.google.common.math.IntMath;
025import com.google.common.primitives.Ints;
026import java.util.AbstractSet;
027import java.util.Set;
028import javax.annotation.Nullable;
029
030/**
031 * This class provides a skeletal implementation of {@link Graph}. It is recommended to extend this
032 * class rather than implement {@link Graph} directly.
033 *
034 * @author James Sexton
035 * @param <N> Node parameter type
036 * @since 20.0
037 */
038@Beta
039public abstract class AbstractGraph<N> implements Graph<N> {
040
041  /**
042   * Returns the number of edges in this graph; used to calculate the size of {@link #edges()}. The
043   * default implementation is O(|N|). You can manually keep track of the number of edges and
044   * override this method for better performance.
045   */
046  protected long edgeCount() {
047    long degreeSum = 0L;
048    for (N node : nodes()) {
049      degreeSum += degree(node);
050    }
051    // According to the degree sum formula, this is equal to twice the number of edges.
052    checkState((degreeSum & 1) == 0);
053    return degreeSum >>> 1;
054  }
055
056  /**
057   * A reasonable default implementation of {@link Graph#edges()} defined in terms of {@link
058   * #nodes()} and {@link #successors(Object)}.
059   */
060  @Override
061  public Set<EndpointPair<N>> edges() {
062    return new AbstractSet<EndpointPair<N>>() {
063      @Override
064      public UnmodifiableIterator<EndpointPair<N>> iterator() {
065        return EndpointPairIterator.of(AbstractGraph.this);
066      }
067
068      @Override
069      public int size() {
070        return Ints.saturatedCast(edgeCount());
071      }
072
073      @Override
074      public boolean contains(@Nullable Object obj) {
075        if (!(obj instanceof EndpointPair)) {
076          return false;
077        }
078        EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
079        return isDirected() == endpointPair.isOrdered()
080            && nodes().contains(endpointPair.nodeU())
081            && successors(endpointPair.nodeU()).contains(endpointPair.nodeV());
082      }
083    };
084  }
085
086  @Override
087  public int degree(Object node) {
088    if (isDirected()) {
089      return IntMath.saturatedAdd(predecessors(node).size(), successors(node).size());
090    } else {
091      Set<N> neighbors = adjacentNodes(node);
092      int selfLoopCount = (allowsSelfLoops() && neighbors.contains(node)) ? 1 : 0;
093      return IntMath.saturatedAdd(neighbors.size(), selfLoopCount);
094    }
095  }
096
097  @Override
098  public int inDegree(Object node) {
099    return isDirected() ? predecessors(node).size() : degree(node);
100  }
101
102  @Override
103  public int outDegree(Object node) {
104    return isDirected() ? successors(node).size() : degree(node);
105  }
106
107  /** Returns a string representation of this graph. */
108  @Override
109  public String toString() {
110    String propertiesString =
111        String.format("isDirected: %s, allowsSelfLoops: %s", isDirected(), allowsSelfLoops());
112    return String.format(GRAPH_STRING_FORMAT, propertiesString, nodes(), edges());
113  }
114}