1 /*
2 * Copyright (C) 2016 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 import static java.util.Objects.requireNonNull;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.base.Function;
24 import com.google.common.collect.ImmutableMap;
25 import com.google.common.collect.Maps;
26 import com.google.errorprone.annotations.CanIgnoreReturnValue;
27 import com.google.errorprone.annotations.Immutable;
28
29 /**
30 * A {@link ValueGraph} whose elements and structural relationships will never change. Instances of
31 * this class may be obtained with {@link #copyOf(ValueGraph)}.
32 *
33 * <p>See the Guava User's Guide's <a
34 * href="https://github.com/google/guava/wiki/GraphsExplained#immutable-implementations">discussion
35 * of the {@code Immutable*} types</a> for more information on the properties and guarantees
36 * provided by this class.
37 *
38 * @author James Sexton
39 * @author Jens Nyman
40 * @param <N> Node parameter type
41 * @param <V> Value parameter type
42 * @since 20.0
43 */
44 @Beta
45 @Immutable(containerOf = {"N", "V"})
46 @SuppressWarnings("Immutable") // Extends StandardValueGraph but uses ImmutableMaps.
47 @ElementTypesAreNonnullByDefault
48 public final class ImmutableValueGraph<N, V> extends StandardValueGraph<N, V> {
49
50 private ImmutableValueGraph(ValueGraph<N, V> graph) {
51 super(ValueGraphBuilder.from(graph), getNodeConnections(graph), graph.edges().size());
52 }
53
54 /** Returns an immutable copy of {@code graph}. */
55 public static <N, V> ImmutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) {
56 return (graph instanceof ImmutableValueGraph)
57 ? (ImmutableValueGraph<N, V>) graph
58 : new ImmutableValueGraph<N, V>(graph);
59 }
60
61 /**
62 * Simply returns its argument.
63 *
64 * @deprecated no need to use this
65 */
66 @Deprecated
67 public static <N, V> ImmutableValueGraph<N, V> copyOf(ImmutableValueGraph<N, V> graph) {
68 return checkNotNull(graph);
69 }
70
71 @Override
72 public ElementOrder<N> incidentEdgeOrder() {
73 return ElementOrder.stable();
74 }
75
76 @Override
77 public ImmutableGraph<N> asGraph() {
78 return new ImmutableGraph<N>(this); // safe because the view is effectively immutable
79 }
80
81 private static <N, V> ImmutableMap<N, GraphConnections<N, V>> getNodeConnections(
82 ValueGraph<N, V> graph) {
83 // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
84 // whatever ordering the graph's nodes do, so ImmutableSortedMap is unnecessary even if the
85 // input nodes are sorted.
86 ImmutableMap.Builder<N, GraphConnections<N, V>> nodeConnections = ImmutableMap.builder();
87 for (N node : graph.nodes()) {
88 nodeConnections.put(node, connectionsOf(graph, node));
89 }
90 return nodeConnections.build();
91 }
92
93 private static <N, V> GraphConnections<N, V> connectionsOf(
94 final ValueGraph<N, V> graph, final N node) {
95 Function<N, V> successorNodeToValueFn =
96 new Function<N, V>() {
97 @Override
98 public V apply(N successorNode) {
99 // requireNonNull is safe because the endpoint pair comes from the graph.
100 return requireNonNull(graph.edgeValueOrDefault(node, successorNode, null));
101 }
102 };
103 return graph.isDirected()
104 ? DirectedGraphConnections.ofImmutable(
105 node, graph.incidentEdges(node), successorNodeToValueFn)
106 : UndirectedGraphConnections.ofImmutable(
107 Maps.asMap(graph.adjacentNodes(node), successorNodeToValueFn));
108 }
109
110 /**
111 * A builder for creating {@link ImmutableValueGraph} instances, especially {@code static final}
112 * graphs. Example:
113 *
114 * <pre>{@code
115 * static final ImmutableValueGraph<City, Distance> CITY_ROAD_DISTANCE_GRAPH =
116 * ValueGraphBuilder.undirected()
117 * .<City, Distance>immutable()
118 * .putEdgeValue(PARIS, BERLIN, kilometers(1060))
119 * .putEdgeValue(PARIS, BRUSSELS, kilometers(317))
120 * .putEdgeValue(BERLIN, BRUSSELS, kilometers(764))
121 * .addNode(REYKJAVIK)
122 * .build();
123 * }</pre>
124 *
125 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
126 * multiple graphs in series. Each new graph contains all the elements of the ones created before
127 * it.
128 *
129 * @since 28.0
130 */
131 public static class Builder<N, V> {
132
133 private final MutableValueGraph<N, V> mutableValueGraph;
134
135 Builder(ValueGraphBuilder<N, V> graphBuilder) {
136 // The incidentEdgeOrder for immutable graphs is always stable. However, we don't want to
137 // modify this builder, so we make a copy instead.
138 this.mutableValueGraph =
139 graphBuilder.copy().incidentEdgeOrder(ElementOrder.<N>stable()).build();
140 }
141
142 /**
143 * Adds {@code node} if it is not already present.
144 *
145 * <p><b>Nodes must be unique</b>, just as {@code Map} keys must be. They must also be non-null.
146 *
147 * @return this {@code Builder} object
148 */
149 @CanIgnoreReturnValue
150 public ImmutableValueGraph.Builder<N, V> addNode(N node) {
151 mutableValueGraph.addNode(node);
152 return this;
153 }
154
155 /**
156 * Adds an edge connecting {@code nodeU} to {@code nodeV} if one is not already present, and
157 * sets a value for that edge to {@code value} (overwriting the existing value, if any).
158 *
159 * <p>If the graph is directed, the resultant edge will be directed; otherwise, it will be
160 * undirected.
161 *
162 * <p>Values do not have to be unique. However, values must be non-null.
163 *
164 * <p>If {@code nodeU} and {@code nodeV} are not already present in this graph, this method will
165 * silently {@link #addNode(Object) add} {@code nodeU} and {@code nodeV} to the graph.
166 *
167 * @return this {@code Builder} object
168 * @throws IllegalArgumentException if the introduction of the edge would violate {@link
169 * #allowsSelfLoops()}
170 */
171 @CanIgnoreReturnValue
172 public ImmutableValueGraph.Builder<N, V> putEdgeValue(N nodeU, N nodeV, V value) {
173 mutableValueGraph.putEdgeValue(nodeU, nodeV, value);
174 return this;
175 }
176
177 /**
178 * Adds an edge connecting {@code endpoints} if one is not already present, and sets a value for
179 * that edge to {@code value} (overwriting the existing value, if any).
180 *
181 * <p>If the graph is directed, the resultant edge will be directed; otherwise, it will be
182 * undirected.
183 *
184 * <p>If this graph is directed, {@code endpoints} must be ordered.
185 *
186 * <p>Values do not have to be unique. However, values must be non-null.
187 *
188 * <p>If either or both endpoints are not already present in this graph, this method will
189 * silently {@link #addNode(Object) add} each missing endpoint to the graph.
190 *
191 * @return this {@code Builder} object
192 * @throws IllegalArgumentException if the introduction of the edge would violate {@link
193 * #allowsSelfLoops()}
194 * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed
195 */
196 @CanIgnoreReturnValue
197 public ImmutableValueGraph.Builder<N, V> putEdgeValue(EndpointPair<N> endpoints, V value) {
198 mutableValueGraph.putEdgeValue(endpoints, value);
199 return this;
200 }
201
202 /**
203 * Returns a newly-created {@code ImmutableValueGraph} based on the contents of this {@code
204 * Builder}.
205 */
206 public ImmutableValueGraph<N, V> build() {
207 return ImmutableValueGraph.copyOf(mutableValueGraph);
208 }
209 }
210 }