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