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