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.Set;
037import org.checkerframework.checker.nullness.compatqual.NullableDecl;
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
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(),
074                new Function<E, EndpointPair<N>>() {
075                  @Override
076                  public EndpointPair<N> apply(E edge) {
077                    return incidentNodes(edge);
078                  }
079                });
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(@NullableDecl 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 boolean isDirected() {
111        return AbstractNetwork.this.isDirected();
112      }
113
114      @Override
115      public boolean allowsSelfLoops() {
116        return AbstractNetwork.this.allowsSelfLoops();
117      }
118
119      @Override
120      public Set<N> adjacentNodes(N node) {
121        return AbstractNetwork.this.adjacentNodes(node);
122      }
123
124      @Override
125      public Set<N> predecessors(N node) {
126        return AbstractNetwork.this.predecessors(node);
127      }
128
129      @Override
130      public Set<N> successors(N node) {
131        return AbstractNetwork.this.successors(node);
132      }
133
134      // DO NOT override the AbstractGraph *degree() implementations.
135    };
136  }
137
138  @Override
139  public int degree(N node) {
140    if (isDirected()) {
141      return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size());
142    } else {
143      return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size());
144    }
145  }
146
147  @Override
148  public int inDegree(N node) {
149    return isDirected() ? inEdges(node).size() : degree(node);
150  }
151
152  @Override
153  public int outDegree(N node) {
154    return isDirected() ? outEdges(node).size() : degree(node);
155  }
156
157  @Override
158  public Set<E> adjacentEdges(E edge) {
159    EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network.
160    Set<E> endpointPairIncidentEdges =
161        Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV()));
162    return Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge));
163  }
164
165  @Override
166  public Set<E> edgesConnecting(N nodeU, N nodeV) {
167    Set<E> outEdgesU = outEdges(nodeU);
168    Set<E> inEdgesV = inEdges(nodeV);
169    return outEdgesU.size() <= inEdgesV.size()
170        ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV)))
171        : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU)));
172  }
173
174  @Override
175  public Set<E> edgesConnecting(EndpointPair<N> endpoints) {
176    validateEndpoints(endpoints);
177    return edgesConnecting(endpoints.nodeU(), endpoints.nodeV());
178  }
179
180  private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) {
181    return new Predicate<E>() {
182      @Override
183      public boolean apply(E edge) {
184        return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck);
185      }
186    };
187  }
188
189  @Override
190  @NullableDecl
191  public E edgeConnectingOrNull(N nodeU, N nodeV) {
192    Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV);
193    switch (edgesConnecting.size()) {
194      case 0:
195        return null;
196      case 1:
197        return edgesConnecting.iterator().next();
198      default:
199        throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV));
200    }
201  }
202
203  @Override
204  @NullableDecl
205  public E edgeConnectingOrNull(EndpointPair<N> endpoints) {
206    validateEndpoints(endpoints);
207    return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV());
208  }
209
210  @Override
211  public boolean hasEdgeConnecting(N nodeU, N nodeV) {
212    checkNotNull(nodeU);
213    checkNotNull(nodeV);
214    return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
215  }
216
217  @Override
218  public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
219    checkNotNull(endpoints);
220    if (!isOrderingCompatible(endpoints)) {
221      return false;
222    }
223    return hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV());
224  }
225
226  /**
227   * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with
228   * the directionality of this graph.
229   */
230  protected final void validateEndpoints(EndpointPair<?> endpoints) {
231    checkNotNull(endpoints);
232    checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH);
233  }
234
235  protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
236    return endpoints.isOrdered() || !this.isDirected();
237  }
238
239  @Override
240  public final boolean equals(@NullableDecl Object obj) {
241    if (obj == this) {
242      return true;
243    }
244    if (!(obj instanceof Network)) {
245      return false;
246    }
247    Network<?, ?> other = (Network<?, ?>) obj;
248
249    return isDirected() == other.isDirected()
250        && nodes().equals(other.nodes())
251        && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other));
252  }
253
254  @Override
255  public final int hashCode() {
256    return edgeIncidentNodesMap(this).hashCode();
257  }
258
259  /** Returns a string representation of this network. */
260  @Override
261  public String toString() {
262    return "isDirected: "
263        + isDirected()
264        + ", allowsParallelEdges: "
265        + allowsParallelEdges()
266        + ", allowsSelfLoops: "
267        + allowsSelfLoops()
268        + ", nodes: "
269        + nodes()
270        + ", edges: "
271        + edgeIncidentNodesMap(this);
272  }
273
274  private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) {
275    Function<E, EndpointPair<N>> edgeToIncidentNodesFn =
276        new Function<E, EndpointPair<N>>() {
277          @Override
278          public EndpointPair<N> apply(E edge) {
279            return network.incidentNodes(edge);
280          }
281        };
282    return Maps.asMap(network.edges(), edgeToIncidentNodesFn);
283  }
284}