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