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