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