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