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