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.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.graph.GraphConstants.EDGE_REMOVED_FROM_GRAPH;
022import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH;
023import static com.google.common.graph.GraphConstants.MULTIPLE_EDGES_CONNECTING;
024import static com.google.common.graph.GraphConstants.NODE_PAIR_REMOVED_FROM_GRAPH;
025import static com.google.common.graph.GraphConstants.NODE_REMOVED_FROM_GRAPH;
026import static java.util.Collections.unmodifiableSet;
027
028import com.google.common.annotations.Beta;
029import com.google.common.base.Predicate;
030import com.google.common.collect.ImmutableSet;
031import com.google.common.collect.Iterators;
032import com.google.common.collect.Maps;
033import com.google.common.collect.Sets;
034import com.google.common.math.IntMath;
035import java.util.AbstractSet;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.Optional;
039import java.util.Set;
040import javax.annotation.CheckForNull;
041
042/**
043 * This class provides a skeletal implementation of {@link Network}. It is recommended to extend
044 * this class rather than implement {@link Network} directly.
045 *
046 * <p>The methods implemented in this class should not be overridden unless the subclass admits a
047 * more efficient implementation.
048 *
049 * @author James Sexton
050 * @param <N> Node parameter type
051 * @param <E> Edge parameter type
052 * @since 20.0
053 */
054@Beta
055@ElementTypesAreNonnullByDefault
056public abstract class AbstractNetwork<N, E> implements Network<N, E> {
057  @Override
058  public Graph<N> asGraph() {
059    return new AbstractGraph<N>() {
060      @Override
061      public Set<N> nodes() {
062        return AbstractNetwork.this.nodes();
063      }
064
065      @Override
066      public Set<EndpointPair<N>> edges() {
067        if (allowsParallelEdges()) {
068          return super.edges(); // Defer to AbstractGraph implementation.
069        }
070
071        // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping).
072        return new AbstractSet<EndpointPair<N>>() {
073          @Override
074          public Iterator<EndpointPair<N>> iterator() {
075            return Iterators.transform(
076                AbstractNetwork.this.edges().iterator(), edge -> incidentNodes(edge));
077          }
078
079          @Override
080          public int size() {
081            return AbstractNetwork.this.edges().size();
082          }
083
084          // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe
085          // operations only in weird cases like checking for an EndpointPair<ArrayList> in a
086          // Network<LinkedList>.
087          @SuppressWarnings("unchecked")
088          @Override
089          public boolean contains(@CheckForNull Object obj) {
090            if (!(obj instanceof EndpointPair)) {
091              return false;
092            }
093            EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
094            return isOrderingCompatible(endpointPair)
095                && nodes().contains(endpointPair.nodeU())
096                && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV());
097          }
098        };
099      }
100
101      @Override
102      public ElementOrder<N> nodeOrder() {
103        return AbstractNetwork.this.nodeOrder();
104      }
105
106      @Override
107      public ElementOrder<N> incidentEdgeOrder() {
108        // TODO(b/142723300): Return AbstractNetwork.this.incidentEdgeOrder() once Network has that
109        //   method.
110        return ElementOrder.unordered();
111      }
112
113      @Override
114      public boolean isDirected() {
115        return AbstractNetwork.this.isDirected();
116      }
117
118      @Override
119      public boolean allowsSelfLoops() {
120        return AbstractNetwork.this.allowsSelfLoops();
121      }
122
123      @Override
124      public Set<N> adjacentNodes(N node) {
125        return AbstractNetwork.this.adjacentNodes(node);
126      }
127
128      @Override
129      public Set<N> predecessors(N node) {
130        return AbstractNetwork.this.predecessors(node);
131      }
132
133      @Override
134      public Set<N> successors(N node) {
135        return AbstractNetwork.this.successors(node);
136      }
137
138      // DO NOT override the AbstractGraph *degree() implementations.
139    };
140  }
141
142  @Override
143  public int degree(N node) {
144    if (isDirected()) {
145      return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size());
146    } else {
147      return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size());
148    }
149  }
150
151  @Override
152  public int inDegree(N node) {
153    return isDirected() ? inEdges(node).size() : degree(node);
154  }
155
156  @Override
157  public int outDegree(N node) {
158    return isDirected() ? outEdges(node).size() : degree(node);
159  }
160
161  @Override
162  public Set<E> adjacentEdges(E edge) {
163    EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network.
164    Set<E> endpointPairIncidentEdges =
165        Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV()));
166    return edgeInvalidatableSet(
167        Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge)), edge);
168  }
169
170  @Override
171  public Set<E> edgesConnecting(N nodeU, N nodeV) {
172    Set<E> outEdgesU = outEdges(nodeU);
173    Set<E> inEdgesV = inEdges(nodeV);
174    return nodePairInvalidatableSet(
175        outEdgesU.size() <= inEdgesV.size()
176            ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV)))
177            : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU))),
178        nodeU,
179        nodeV);
180  }
181
182  @Override
183  public Set<E> edgesConnecting(EndpointPair<N> endpoints) {
184    validateEndpoints(endpoints);
185    return edgesConnecting(endpoints.nodeU(), endpoints.nodeV());
186  }
187
188  private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) {
189    return new Predicate<E>() {
190      @Override
191      public boolean apply(E edge) {
192        return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck);
193      }
194    };
195  }
196
197  @Override
198  public Optional<E> edgeConnecting(N nodeU, N nodeV) {
199    return Optional.ofNullable(edgeConnectingOrNull(nodeU, nodeV));
200  }
201
202  @Override
203  public Optional<E> edgeConnecting(EndpointPair<N> endpoints) {
204    validateEndpoints(endpoints);
205    return edgeConnecting(endpoints.nodeU(), endpoints.nodeV());
206  }
207
208  @Override
209  @CheckForNull
210  public E edgeConnectingOrNull(N nodeU, N nodeV) {
211    Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV);
212    switch (edgesConnecting.size()) {
213      case 0:
214        return null;
215      case 1:
216        return edgesConnecting.iterator().next();
217      default:
218        throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV));
219    }
220  }
221
222  @Override
223  @CheckForNull
224  public E edgeConnectingOrNull(EndpointPair<N> endpoints) {
225    validateEndpoints(endpoints);
226    return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV());
227  }
228
229  @Override
230  public boolean hasEdgeConnecting(N nodeU, N nodeV) {
231    checkNotNull(nodeU);
232    checkNotNull(nodeV);
233    return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
234  }
235
236  @Override
237  public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
238    checkNotNull(endpoints);
239    if (!isOrderingCompatible(endpoints)) {
240      return false;
241    }
242    return hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV());
243  }
244
245  /**
246   * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with
247   * the directionality of this graph.
248   */
249  protected final void validateEndpoints(EndpointPair<?> endpoints) {
250    checkNotNull(endpoints);
251    checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH);
252  }
253
254  protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
255    return endpoints.isOrdered() == this.isDirected();
256  }
257
258  @Override
259  public final boolean equals(@CheckForNull Object obj) {
260    if (obj == this) {
261      return true;
262    }
263    if (!(obj instanceof Network)) {
264      return false;
265    }
266    Network<?, ?> other = (Network<?, ?>) obj;
267
268    return isDirected() == other.isDirected()
269        && nodes().equals(other.nodes())
270        && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other));
271  }
272
273  @Override
274  public final int hashCode() {
275    return edgeIncidentNodesMap(this).hashCode();
276  }
277
278  /** Returns a string representation of this network. */
279  @Override
280  public String toString() {
281    return "isDirected: "
282        + isDirected()
283        + ", allowsParallelEdges: "
284        + allowsParallelEdges()
285        + ", allowsSelfLoops: "
286        + allowsSelfLoops()
287        + ", nodes: "
288        + nodes()
289        + ", edges: "
290        + edgeIncidentNodesMap(this);
291  }
292
293  /**
294   * Returns a {@link Set} whose methods throw {@link IllegalStateException} when the given edge is
295   * not present in this network.
296   *
297   * @since 33.1.0
298   */
299  protected final <T> Set<T> edgeInvalidatableSet(Set<T> set, E edge) {
300    return InvalidatableSet.of(
301        set, () -> edges().contains(edge), () -> String.format(EDGE_REMOVED_FROM_GRAPH, edge));
302  }
303
304  /**
305   * Returns a {@link Set} whose methods throw {@link IllegalStateException} when the given node is
306   * not present in this network.
307   *
308   * @since 33.1.0
309   */
310  protected final <T> Set<T> nodeInvalidatableSet(Set<T> set, N node) {
311    return InvalidatableSet.of(
312        set, () -> nodes().contains(node), () -> String.format(NODE_REMOVED_FROM_GRAPH, node));
313  }
314
315  /**
316   * Returns a {@link Set} whose methods throw {@link IllegalStateException} when either of the
317   * given nodes is not present in this network.
318   *
319   * @since 33.1.0
320   */
321  protected final <T> Set<T> nodePairInvalidatableSet(Set<T> set, N nodeU, N nodeV) {
322    return InvalidatableSet.of(
323        set,
324        () -> nodes().contains(nodeU) && nodes().contains(nodeV),
325        () -> String.format(NODE_PAIR_REMOVED_FROM_GRAPH, nodeU, nodeV));
326  }
327
328  private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) {
329    return Maps.asMap(network.edges(), network::incidentNodes);
330  }
331}