001/* 002 * Copyright (C) 2016 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; 020import static java.util.Objects.requireNonNull; 021 022import com.google.common.annotations.Beta; 023import com.google.common.base.Function; 024import com.google.common.collect.ImmutableMap; 025import com.google.common.collect.Maps; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import com.google.errorprone.annotations.Immutable; 028 029/** 030 * A {@link ValueGraph} whose elements and structural relationships will never change. Instances of 031 * this class may be obtained with {@link #copyOf(ValueGraph)}. 032 * 033 * <p>See the Guava User's Guide's <a 034 * href="https://github.com/google/guava/wiki/GraphsExplained#immutable-implementations">discussion 035 * of the {@code Immutable*} types</a> for more information on the properties and guarantees 036 * provided by this class. 037 * 038 * @author James Sexton 039 * @author Jens Nyman 040 * @param <N> Node parameter type 041 * @param <V> Value parameter type 042 * @since 20.0 043 */ 044@Beta 045@Immutable(containerOf = {"N", "V"}) 046@SuppressWarnings("Immutable") // Extends StandardValueGraph but uses ImmutableMaps. 047@ElementTypesAreNonnullByDefault 048public final class ImmutableValueGraph<N, V> extends StandardValueGraph<N, V> { 049 050 private ImmutableValueGraph(ValueGraph<N, V> graph) { 051 super(ValueGraphBuilder.from(graph), getNodeConnections(graph), graph.edges().size()); 052 } 053 054 /** Returns an immutable copy of {@code graph}. */ 055 public static <N, V> ImmutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) { 056 return (graph instanceof ImmutableValueGraph) 057 ? (ImmutableValueGraph<N, V>) graph 058 : new ImmutableValueGraph<N, V>(graph); 059 } 060 061 /** 062 * Simply returns its argument. 063 * 064 * @deprecated no need to use this 065 */ 066 @Deprecated 067 public static <N, V> ImmutableValueGraph<N, V> copyOf(ImmutableValueGraph<N, V> graph) { 068 return checkNotNull(graph); 069 } 070 071 @Override 072 public ElementOrder<N> incidentEdgeOrder() { 073 return ElementOrder.stable(); 074 } 075 076 @Override 077 public ImmutableGraph<N> asGraph() { 078 return new ImmutableGraph<>(this); // safe because the view is effectively immutable 079 } 080 081 private static <N, V> ImmutableMap<N, GraphConnections<N, V>> getNodeConnections( 082 ValueGraph<N, V> graph) { 083 // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have 084 // whatever ordering the graph's nodes do, so ImmutableSortedMap is unnecessary even if the 085 // input nodes are sorted. 086 ImmutableMap.Builder<N, GraphConnections<N, V>> nodeConnections = ImmutableMap.builder(); 087 for (N node : graph.nodes()) { 088 nodeConnections.put(node, connectionsOf(graph, node)); 089 } 090 return nodeConnections.buildOrThrow(); 091 } 092 093 private static <N, V> GraphConnections<N, V> connectionsOf(ValueGraph<N, V> graph, N node) { 094 Function<N, V> successorNodeToValueFn = 095 (N successorNode) -> 096 // requireNonNull is safe because the endpoint pair comes from the graph. 097 requireNonNull(graph.edgeValueOrDefault(node, successorNode, null)); 098 return graph.isDirected() 099 ? DirectedGraphConnections.ofImmutable( 100 node, graph.incidentEdges(node), successorNodeToValueFn) 101 : UndirectedGraphConnections.ofImmutable( 102 Maps.asMap(graph.adjacentNodes(node), successorNodeToValueFn)); 103 } 104 105 /** 106 * A builder for creating {@link ImmutableValueGraph} instances, especially {@code static final} 107 * graphs. Example: 108 * 109 * <pre>{@code 110 * static final ImmutableValueGraph<City, Distance> CITY_ROAD_DISTANCE_GRAPH = 111 * ValueGraphBuilder.undirected() 112 * .<City, Distance>immutable() 113 * .putEdgeValue(PARIS, BERLIN, kilometers(1060)) 114 * .putEdgeValue(PARIS, BRUSSELS, kilometers(317)) 115 * .putEdgeValue(BERLIN, BRUSSELS, kilometers(764)) 116 * .addNode(REYKJAVIK) 117 * .build(); 118 * }</pre> 119 * 120 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 121 * multiple graphs in series. Each new graph contains all the elements of the ones created before 122 * it. 123 * 124 * @since 28.0 125 */ 126 public static class Builder<N, V> { 127 128 private final MutableValueGraph<N, V> mutableValueGraph; 129 130 Builder(ValueGraphBuilder<N, V> graphBuilder) { 131 // The incidentEdgeOrder for immutable graphs is always stable. However, we don't want to 132 // modify this builder, so we make a copy instead. 133 this.mutableValueGraph = 134 graphBuilder.copy().incidentEdgeOrder(ElementOrder.<N>stable()).build(); 135 } 136 137 /** 138 * Adds {@code node} if it is not already present. 139 * 140 * <p><b>Nodes must be unique</b>, just as {@code Map} keys must be. They must also be non-null. 141 * 142 * @return this {@code Builder} object 143 */ 144 @CanIgnoreReturnValue 145 public ImmutableValueGraph.Builder<N, V> addNode(N node) { 146 mutableValueGraph.addNode(node); 147 return this; 148 } 149 150 /** 151 * Adds an edge connecting {@code nodeU} to {@code nodeV} if one is not already present, and 152 * sets a value for that edge to {@code value} (overwriting the existing value, if any). 153 * 154 * <p>If the graph is directed, the resultant edge will be directed; otherwise, it will be 155 * undirected. 156 * 157 * <p>Values do not have to be unique. However, values must be non-null. 158 * 159 * <p>If {@code nodeU} and {@code nodeV} are not already present in this graph, this method will 160 * silently {@link #addNode(Object) add} {@code nodeU} and {@code nodeV} to the graph. 161 * 162 * @return this {@code Builder} object 163 * @throws IllegalArgumentException if the introduction of the edge would violate {@link 164 * #allowsSelfLoops()} 165 */ 166 @CanIgnoreReturnValue 167 public ImmutableValueGraph.Builder<N, V> putEdgeValue(N nodeU, N nodeV, V value) { 168 mutableValueGraph.putEdgeValue(nodeU, nodeV, value); 169 return this; 170 } 171 172 /** 173 * Adds an edge connecting {@code endpoints} if one is not already present, and sets a value for 174 * that edge to {@code value} (overwriting the existing value, if any). 175 * 176 * <p>If the graph is directed, the resultant edge will be directed; otherwise, it will be 177 * undirected. 178 * 179 * <p>If this graph is directed, {@code endpoints} must be ordered. 180 * 181 * <p>Values do not have to be unique. However, values must be non-null. 182 * 183 * <p>If either or both endpoints are not already present in this graph, this method will 184 * silently {@link #addNode(Object) add} each missing endpoint to the graph. 185 * 186 * @return this {@code Builder} object 187 * @throws IllegalArgumentException if the introduction of the edge would violate {@link 188 * #allowsSelfLoops()} 189 * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed 190 */ 191 @CanIgnoreReturnValue 192 public ImmutableValueGraph.Builder<N, V> putEdgeValue(EndpointPair<N> endpoints, V value) { 193 mutableValueGraph.putEdgeValue(endpoints, value); 194 return this; 195 } 196 197 /** 198 * Returns a newly-created {@code ImmutableValueGraph} based on the contents of this {@code 199 * Builder}. 200 */ 201 public ImmutableValueGraph<N, V> build() { 202 return ImmutableValueGraph.copyOf(mutableValueGraph); 203 } 204 } 205}