/*
 * Copyright (C) 2017 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.base.Preconditions.checkState;

import com.google.common.base.Function;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterators;
import com.google.common.collect.Sets;
import com.google.common.collect.UnmodifiableIterator;
import com.google.common.math.IntMath;
import com.google.common.primitives.Ints;
import java.util.AbstractSet;
import java.util.Set;
import org.checkerframework.checker.nullness.qual.Nullable;

This class provides a skeletal implementation of BaseGraph.

The methods implemented in this class should not be overridden unless the subclass admits a more efficient implementation.

Author:James Sexton
Type parameters:
  • <N> – Node parameter type
/** * This class provides a skeletal implementation of {@link BaseGraph}. * * <p>The methods implemented in this class should not be overridden unless the subclass admits a * more efficient implementation. * * @author James Sexton * @param <N> Node parameter type */
abstract class AbstractBaseGraph<N> implements BaseGraph<N> {
Returns the number of edges in this graph; used to calculate the size of edges(). This implementation requires O(|N|) time. Classes extending this one may manually keep track of the number of edges as the graph is updated, and override this method for better performance.
/** * Returns the number of edges in this graph; used to calculate the size of {@link #edges()}. This * implementation requires O(|N|) time. Classes extending this one may manually keep track of the * number of edges as the graph is updated, and override this method for better performance. */
protected long edgeCount() { long degreeSum = 0L; for (N node : nodes()) { degreeSum += degree(node); } // According to the degree sum formula, this is equal to twice the number of edges. checkState((degreeSum & 1) == 0); return degreeSum >>> 1; }
An implementation of BaseGraph.edges() defined in terms of BaseGraph.nodes() and BaseGraph.successors(Object).
/** * An implementation of {@link BaseGraph#edges()} defined in terms of {@link #nodes()} and {@link * #successors(Object)}. */
@Override public Set<EndpointPair<N>> edges() { return new AbstractSet<EndpointPair<N>>() { @Override public UnmodifiableIterator<EndpointPair<N>> iterator() { return EndpointPairIterator.of(AbstractBaseGraph.this); } @Override public int size() { return Ints.saturatedCast(edgeCount()); } @Override public boolean remove(Object o) { throw new UnsupportedOperationException(); } // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe // operations only in weird cases like checking for an EndpointPair<ArrayList> in a // Graph<LinkedList>. @SuppressWarnings("unchecked") @Override public boolean contains(@Nullable Object obj) { if (!(obj instanceof EndpointPair)) { return false; } EndpointPair<?> endpointPair = (EndpointPair<?>) obj; return isDirected() == endpointPair.isOrdered() && nodes().contains(endpointPair.nodeU()) && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV()); } }; } @Override public Set<EndpointPair<N>> incidentEdges(N node) { checkNotNull(node); checkArgument(nodes().contains(node), "Node %s is not an element of this graph.", node); return IncidentEdgeSet.of(this, node); } @Override public int degree(N node) { if (isDirected()) { return IntMath.saturatedAdd(predecessors(node).size(), successors(node).size()); } else { Set<N> neighbors = adjacentNodes(node); int selfLoopCount = (allowsSelfLoops() && neighbors.contains(node)) ? 1 : 0; return IntMath.saturatedAdd(neighbors.size(), selfLoopCount); } } @Override public int inDegree(N node) { return isDirected() ? predecessors(node).size() : degree(node); } @Override public int outDegree(N node) { return isDirected() ? successors(node).size() : degree(node); } @Override public boolean hasEdgeConnecting(N nodeU, N nodeV) { checkNotNull(nodeU); checkNotNull(nodeV); return nodes().contains(nodeU) && successors(nodeU).contains(nodeV); } private abstract static class IncidentEdgeSet<N> extends AbstractSet<EndpointPair<N>> { protected final N node; protected final BaseGraph<N> graph; public static <N> IncidentEdgeSet<N> of(BaseGraph<N> graph, N node) { return graph.isDirected() ? new Directed<>(graph, node) : new Undirected<>(graph, node); } private IncidentEdgeSet(BaseGraph<N> graph, N node) { this.graph = graph; this.node = node; } @Override public boolean remove(Object o) { throw new UnsupportedOperationException(); } private static final class Directed<N> extends IncidentEdgeSet<N> { private Directed(BaseGraph<N> graph, N node) { super(graph, node); } @Override public UnmodifiableIterator<EndpointPair<N>> iterator() { return Iterators.unmodifiableIterator( Iterators.concat( Iterators.transform( graph.predecessors(node).iterator(), new Function<N, EndpointPair<N>>() { @Override public EndpointPair<N> apply(N predecessor) { return EndpointPair.ordered(predecessor, node); } }), Iterators.transform( // filter out 'node' from successors (already covered by predecessors, above) Sets.difference(graph.successors(node), ImmutableSet.of(node)).iterator(), new Function<N, EndpointPair<N>>() { @Override public EndpointPair<N> apply(N successor) { return EndpointPair.ordered(node, successor); } }))); } @Override public int size() { return graph.inDegree(node) + graph.outDegree(node) - (graph.successors(node).contains(node) ? 1 : 0); } @Override public boolean contains(@Nullable Object obj) { if (!(obj instanceof EndpointPair)) { return false; } EndpointPair<?> endpointPair = (EndpointPair<?>) obj; if (!endpointPair.isOrdered()) { return false; } Object source = endpointPair.source(); Object target = endpointPair.target(); return (node.equals(source) && graph.successors(node).contains(target)) || (node.equals(target) && graph.predecessors(node).contains(source)); } } private static final class Undirected<N> extends IncidentEdgeSet<N> { private Undirected(BaseGraph<N> graph, N node) { super(graph, node); } @Override public UnmodifiableIterator<EndpointPair<N>> iterator() { return Iterators.unmodifiableIterator( Iterators.transform( graph.adjacentNodes(node).iterator(), new Function<N, EndpointPair<N>>() { @Override public EndpointPair<N> apply(N adjacentNode) { return EndpointPair.unordered(node, adjacentNode); } })); } @Override public int size() { return graph.adjacentNodes(node).size(); } @Override public boolean contains(@Nullable Object obj) { if (!(obj instanceof EndpointPair)) { return false; } EndpointPair<?> endpointPair = (EndpointPair<?>) obj; if (endpointPair.isOrdered()) { return false; } Set<N> adjacent = graph.adjacentNodes(node); Object nodeU = endpointPair.nodeU(); Object nodeV = endpointPair.nodeV(); return (node.equals(nodeV) && adjacent.contains(nodeU)) || (node.equals(nodeU) && adjacent.contains(nodeV)); } } } }