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