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