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