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