001/*
002 * Copyright (C) 2014 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.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.base.Function;
023import com.google.common.collect.ImmutableMap;
024import com.google.common.collect.Maps;
025import com.google.errorprone.annotations.Immutable;
026import java.util.Map;
027
028/**
029 * A {@link Network} whose elements and structural relationships will never change. Instances of
030 * this class may be obtained with {@link #copyOf(Network)}.
031 *
032 * <p>See the Guava User's Guide's <a
033 * href="https://github.com/google/guava/wiki/GraphsExplained#immutable-implementations">discussion
034 * of the {@code Immutable*} types</a> for more information on the properties and guarantees
035 * provided by this class.
036 *
037 * @author James Sexton
038 * @author Joshua O'Madadhain
039 * @author Omar Darwish
040 * @param <N> Node parameter type
041 * @param <E> Edge parameter type
042 * @since 20.0
043 */
044@Beta
045@Immutable(containerOf = {"N", "E"})
046@SuppressWarnings("Immutable") // Extends ConfigurableNetwork but uses ImmutableMaps.
047public final class ImmutableNetwork<N, E> extends ConfigurableNetwork<N, E> {
048
049  private ImmutableNetwork(Network<N, E> network) {
050    super(
051        NetworkBuilder.from(network), getNodeConnections(network), getEdgeToReferenceNode(network));
052  }
053
054  /** Returns an immutable copy of {@code network}. */
055  public static <N, E> ImmutableNetwork<N, E> copyOf(Network<N, E> network) {
056    return (network instanceof ImmutableNetwork)
057        ? (ImmutableNetwork<N, E>) network
058        : new ImmutableNetwork<N, E>(network);
059  }
060
061  /**
062   * Simply returns its argument.
063   *
064   * @deprecated no need to use this
065   */
066  @Deprecated
067  public static <N, E> ImmutableNetwork<N, E> copyOf(ImmutableNetwork<N, E> network) {
068    return checkNotNull(network);
069  }
070
071  @Override
072  public ImmutableGraph<N> asGraph() {
073    return new ImmutableGraph<N>(super.asGraph()); // safe because the view is effectively immutable
074  }
075
076  private static <N, E> Map<N, NetworkConnections<N, E>> getNodeConnections(Network<N, E> network) {
077    // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
078    // whatever ordering the network's nodes do, so ImmutableSortedMap is unnecessary even if the
079    // input nodes are sorted.
080    ImmutableMap.Builder<N, NetworkConnections<N, E>> nodeConnections = ImmutableMap.builder();
081    for (N node : network.nodes()) {
082      nodeConnections.put(node, connectionsOf(network, node));
083    }
084    return nodeConnections.build();
085  }
086
087  private static <N, E> Map<E, N> getEdgeToReferenceNode(Network<N, E> network) {
088    // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
089    // whatever ordering the network's edges do, so ImmutableSortedMap is unnecessary even if the
090    // input edges are sorted.
091    ImmutableMap.Builder<E, N> edgeToReferenceNode = ImmutableMap.builder();
092    for (E edge : network.edges()) {
093      edgeToReferenceNode.put(edge, network.incidentNodes(edge).nodeU());
094    }
095    return edgeToReferenceNode.build();
096  }
097
098  private static <N, E> NetworkConnections<N, E> connectionsOf(Network<N, E> network, N node) {
099    if (network.isDirected()) {
100      Map<E, N> inEdgeMap = Maps.asMap(network.inEdges(node), sourceNodeFn(network));
101      Map<E, N> outEdgeMap = Maps.asMap(network.outEdges(node), targetNodeFn(network));
102      int selfLoopCount = network.edgesConnecting(node, node).size();
103      return network.allowsParallelEdges()
104          ? DirectedMultiNetworkConnections.ofImmutable(inEdgeMap, outEdgeMap, selfLoopCount)
105          : DirectedNetworkConnections.ofImmutable(inEdgeMap, outEdgeMap, selfLoopCount);
106    } else {
107      Map<E, N> incidentEdgeMap =
108          Maps.asMap(network.incidentEdges(node), adjacentNodeFn(network, node));
109      return network.allowsParallelEdges()
110          ? UndirectedMultiNetworkConnections.ofImmutable(incidentEdgeMap)
111          : UndirectedNetworkConnections.ofImmutable(incidentEdgeMap);
112    }
113  }
114
115  private static <N, E> Function<E, N> sourceNodeFn(final Network<N, E> network) {
116    return new Function<E, N>() {
117      @Override
118      public N apply(E edge) {
119        return network.incidentNodes(edge).source();
120      }
121    };
122  }
123
124  private static <N, E> Function<E, N> targetNodeFn(final Network<N, E> network) {
125    return new Function<E, N>() {
126      @Override
127      public N apply(E edge) {
128        return network.incidentNodes(edge).target();
129      }
130    };
131  }
132
133  private static <N, E> Function<E, N> adjacentNodeFn(final Network<N, E> network, final N node) {
134    return new Function<E, N>() {
135      @Override
136      public N apply(E edge) {
137        return network.incidentNodes(edge).adjacentNode(node);
138      }
139    };
140  }
141}