View Javadoc
1   /*
2    * Copyright (C) 2014 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.graph;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.base.Function;
23  import com.google.common.collect.ImmutableMap;
24  import com.google.common.collect.Maps;
25  import com.google.errorprone.annotations.Immutable;
26  import java.util.Map;
27  
28  /**
29   * A {@link Network} whose elements and structural relationships will never change. Instances of
30   * this class may be obtained with {@link #copyOf(Network)}.
31   *
32   * <p>See the Guava User's Guide's <a
33   * href="https://github.com/google/guava/wiki/GraphsExplained#immutable-implementations">discussion
34   * of the {@code Immutable*} types</a> for more information on the properties and guarantees
35   * provided by this class.
36   *
37   * @author James Sexton
38   * @author Joshua O'Madadhain
39   * @author Omar Darwish
40   * @param <N> Node parameter type
41   * @param <E> Edge parameter type
42   * @since 20.0
43   */
44  @Beta
45  @Immutable(containerOf = {"N", "E"})
46  @SuppressWarnings("Immutable") // Extends ConfigurableNetwork but uses ImmutableMaps.
47  public final class ImmutableNetwork<N, E> extends ConfigurableNetwork<N, E> {
48  
49    private ImmutableNetwork(Network<N, E> network) {
50      super(
51          NetworkBuilder.from(network), getNodeConnections(network), getEdgeToReferenceNode(network));
52    }
53  
54    /** Returns an immutable copy of {@code network}. */
55    public static <N, E> ImmutableNetwork<N, E> copyOf(Network<N, E> network) {
56      return (network instanceof ImmutableNetwork)
57          ? (ImmutableNetwork<N, E>) network
58          : new ImmutableNetwork<N, E>(network);
59    }
60  
61    /**
62     * Simply returns its argument.
63     *
64     * @deprecated no need to use this
65     */
66    @Deprecated
67    public static <N, E> ImmutableNetwork<N, E> copyOf(ImmutableNetwork<N, E> network) {
68      return checkNotNull(network);
69    }
70  
71    @Override
72    public ImmutableGraph<N> asGraph() {
73      return new ImmutableGraph<N>(super.asGraph()); // safe because the view is effectively immutable
74    }
75  
76    private static <N, E> Map<N, NetworkConnections<N, E>> getNodeConnections(Network<N, E> network) {
77      // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
78      // whatever ordering the network's nodes do, so ImmutableSortedMap is unnecessary even if the
79      // input nodes are sorted.
80      ImmutableMap.Builder<N, NetworkConnections<N, E>> nodeConnections = ImmutableMap.builder();
81      for (N node : network.nodes()) {
82        nodeConnections.put(node, connectionsOf(network, node));
83      }
84      return nodeConnections.build();
85    }
86  
87    private static <N, E> Map<E, N> getEdgeToReferenceNode(Network<N, E> network) {
88      // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
89      // whatever ordering the network's edges do, so ImmutableSortedMap is unnecessary even if the
90      // input edges are sorted.
91      ImmutableMap.Builder<E, N> edgeToReferenceNode = ImmutableMap.builder();
92      for (E edge : network.edges()) {
93        edgeToReferenceNode.put(edge, network.incidentNodes(edge).nodeU());
94      }
95      return edgeToReferenceNode.build();
96    }
97  
98    private static <N, E> NetworkConnections<N, E> connectionsOf(Network<N, E> network, N node) {
99      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 }