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.GRAPH_STRING_FORMAT;
020
021import com.google.common.annotations.Beta;
022import com.google.common.base.Function;
023import com.google.common.collect.ImmutableSet;
024import com.google.common.collect.Iterators;
025import com.google.common.collect.Maps;
026import com.google.common.collect.Sets;
027import com.google.common.math.IntMath;
028import java.util.AbstractSet;
029import java.util.Iterator;
030import java.util.Map;
031import java.util.Set;
032import javax.annotation.Nullable;
033
034/**
035 * This class provides a skeletal implementation of {@link Network}. It is recommended to extend
036 * this class rather than implement {@link Network} directly.
037 *
038 * @author James Sexton
039 * @param <N> Node parameter type
040 * @param <E> Edge parameter type
041 * @since 20.0
042 */
043@Beta
044public abstract class AbstractNetwork<N, E> implements Network<N, E> {
045
046  @Override
047  public Graph<N> asGraph() {
048    return new AbstractGraph<N>() {
049      @Override
050      public Set<N> nodes() {
051        return AbstractNetwork.this.nodes();
052      }
053
054      @Override
055      public Set<EndpointPair<N>> edges() {
056        if (allowsParallelEdges()) {
057          return super.edges(); // Defer to AbstractGraph implementation.
058        }
059
060        // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping).
061        return new AbstractSet<EndpointPair<N>>() {
062          @Override
063          public Iterator<EndpointPair<N>> iterator() {
064            return Iterators.transform(
065                AbstractNetwork.this.edges().iterator(),
066                new Function<E, EndpointPair<N>>() {
067                  @Override
068                  public EndpointPair<N> apply(E edge) {
069                    return incidentNodes(edge);
070                  }
071                });
072          }
073
074          @Override
075          public int size() {
076            return AbstractNetwork.this.edges().size();
077          }
078
079          @Override
080          public boolean contains(@Nullable Object obj) {
081            if (!(obj instanceof EndpointPair)) {
082              return false;
083            }
084            EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
085            return isDirected() == endpointPair.isOrdered()
086                && nodes().contains(endpointPair.nodeU())
087                && successors(endpointPair.nodeU()).contains(endpointPair.nodeV());
088          }
089        };
090      }
091
092      @Override
093      public ElementOrder<N> nodeOrder() {
094        return AbstractNetwork.this.nodeOrder();
095      }
096
097      @Override
098      public boolean isDirected() {
099        return AbstractNetwork.this.isDirected();
100      }
101
102      @Override
103      public boolean allowsSelfLoops() {
104        return AbstractNetwork.this.allowsSelfLoops();
105      }
106
107      @Override
108      public Set<N> adjacentNodes(Object node) {
109        return AbstractNetwork.this.adjacentNodes(node);
110      }
111
112      @Override
113      public Set<N> predecessors(Object node) {
114        return AbstractNetwork.this.predecessors(node);
115      }
116
117      @Override
118      public Set<N> successors(Object node) {
119        return AbstractNetwork.this.successors(node);
120      }
121
122      // DO NOT override the AbstractGraph *degree() implementations.
123    };
124  }
125
126  @Override
127  public int degree(Object node) {
128    if (isDirected()) {
129      return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size());
130    } else {
131      return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size());
132    }
133  }
134
135  @Override
136  public int inDegree(Object node) {
137    return isDirected() ? inEdges(node).size() : degree(node);
138  }
139
140  @Override
141  public int outDegree(Object node) {
142    return isDirected() ? outEdges(node).size() : degree(node);
143  }
144
145  @Override
146  public Set<E> adjacentEdges(Object edge) {
147    EndpointPair<?> endpointPair = incidentNodes(edge); // Verifies that edge is in this network.
148    Set<E> endpointPairIncidentEdges =
149        Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV()));
150    return Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge));
151  }
152
153  /** Returns a string representation of this network. */
154  @Override
155  public String toString() {
156    String propertiesString =
157        String.format(
158            "isDirected: %s, allowsParallelEdges: %s, allowsSelfLoops: %s",
159            isDirected(), allowsParallelEdges(), allowsSelfLoops());
160    return String.format(GRAPH_STRING_FORMAT, propertiesString, nodes(), edgeIncidentNodesMap());
161  }
162
163  private Map<E, EndpointPair<N>> edgeIncidentNodesMap() {
164    Function<E, EndpointPair<N>> edgeToIncidentNodesFn =
165        new Function<E, EndpointPair<N>>() {
166          @Override
167          public EndpointPair<N> apply(E edge) {
168            return incidentNodes(edge);
169          }
170        };
171    return Maps.asMap(edges(), edgeToIncidentNodesFn);
172  }
173}