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
045public final class ImmutableNetwork<N, E> extends ConfigurableNetwork<N, E> {
046
047  private ImmutableNetwork(Network<N, E> network) {
048    super(
049        NetworkBuilder.from(network), getNodeConnections(network), getEdgeToReferenceNode(network));
050  }
051
052  /** Returns an immutable copy of {@code network}. */
053  public static <N, E> ImmutableNetwork<N, E> copyOf(Network<N, E> network) {
054    return (network instanceof ImmutableNetwork)
055        ? (ImmutableNetwork<N, E>) network
056        : new ImmutableNetwork<N, E>(network);
057  }
058
059  /**
060   * Simply returns its argument.
061   *
062   * @deprecated no need to use this
063   */
064  @Deprecated
065  public static <N, E> ImmutableNetwork<N, E> copyOf(ImmutableNetwork<N, E> network) {
066    return checkNotNull(network);
067  }
068
069  @Override
070  public ImmutableGraph<N> asGraph() {
071    final Graph<N> asGraph = super.asGraph();
072    return new ImmutableGraph<N>() {
073      @Override
074      protected Graph<N> delegate() {
075        return asGraph; // safe because the graph view is effectively immutable
076      }
077    };
078  }
079
080  private static <N, E> Map<N, NetworkConnections<N, E>> getNodeConnections(Network<N, E> network) {
081    // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
082    // whatever ordering the network's nodes do, so ImmutableSortedMap is unnecessary even if the
083    // input nodes are sorted.
084    ImmutableMap.Builder<N, NetworkConnections<N, E>> nodeConnections = ImmutableMap.builder();
085    for (N node : network.nodes()) {
086      nodeConnections.put(node, connectionsOf(network, node));
087    }
088    return nodeConnections.build();
089  }
090
091  private static <N, E> Map<E, N> getEdgeToReferenceNode(Network<N, E> network) {
092    // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
093    // whatever ordering the network's edges do, so ImmutableSortedMap is unnecessary even if the
094    // input edges are sorted.
095    ImmutableMap.Builder<E, N> edgeToReferenceNode = ImmutableMap.builder();
096    for (E edge : network.edges()) {
097      edgeToReferenceNode.put(edge, network.incidentNodes(edge).nodeU());
098    }
099    return edgeToReferenceNode.build();
100  }
101
102  private static <N, E> NetworkConnections<N, E> connectionsOf(Network<N, E> network, N node) {
103    if (network.isDirected()) {
104      Map<E, N> inEdgeMap = Maps.asMap(network.inEdges(node), sourceNodeFn(network));
105      Map<E, N> outEdgeMap = Maps.asMap(network.outEdges(node), targetNodeFn(network));
106      int selfLoopCount = network.edgesConnecting(node, node).size();
107      return network.allowsParallelEdges()
108          ? DirectedMultiNetworkConnections.ofImmutable(inEdgeMap, outEdgeMap, selfLoopCount)
109          : DirectedNetworkConnections.ofImmutable(inEdgeMap, outEdgeMap, selfLoopCount);
110    } else {
111      Map<E, N> incidentEdgeMap =
112          Maps.asMap(network.incidentEdges(node), adjacentNodeFn(network, node));
113      return network.allowsParallelEdges()
114          ? UndirectedMultiNetworkConnections.ofImmutable(incidentEdgeMap)
115          : UndirectedNetworkConnections.ofImmutable(incidentEdgeMap);
116    }
117  }
118
119  private static <N, E> Function<E, N> sourceNodeFn(final Network<N, E> network) {
120    return new Function<E, N>() {
121      @Override
122      public N apply(E edge) {
123        return network.incidentNodes(edge).source();
124      }
125    };
126  }
127
128  private static <N, E> Function<E, N> targetNodeFn(final Network<N, E> network) {
129    return new Function<E, N>() {
130      @Override
131      public N apply(E edge) {
132        return network.incidentNodes(edge).target();
133      }
134    };
135  }
136
137  private static <N, E> Function<E, N> adjacentNodeFn(final Network<N, E> network, final N node) {
138    return new Function<E, N>() {
139      @Override
140      public N apply(E edge) {
141        return network.incidentNodes(edge).adjacentNode(node);
142      }
143    };
144  }
145}