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}