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