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