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.base.Functions; 024import com.google.common.collect.ImmutableMap; 025import com.google.common.collect.Maps; 026import com.google.common.graph.GraphConstants.Presence; 027import com.google.errorprone.annotations.CanIgnoreReturnValue; 028import com.google.errorprone.annotations.Immutable; 029 030/** 031 * A {@link Graph} whose elements and structural relationships will never change. Instances of this 032 * class may be obtained with {@link #copyOf(Graph)}. 033 * 034 * <p>See the Guava User's Guide's <a 035 * href="https://github.com/google/guava/wiki/GraphsExplained#immutable-implementations">discussion 036 * of the {@code Immutable*} types</a> for more information on the properties and guarantees 037 * provided by this class. 038 * 039 * @author James Sexton 040 * @author Joshua O'Madadhain 041 * @author Omar Darwish 042 * @author Jens Nyman 043 * @param <N> Node parameter type 044 * @since 20.0 045 */ 046@Beta 047@Immutable(containerOf = {"N"}) 048public class ImmutableGraph<N> extends ForwardingGraph<N> { 049 @SuppressWarnings("Immutable") // The backing graph must be immutable. 050 private final BaseGraph<N> backingGraph; 051 052 ImmutableGraph(BaseGraph<N> backingGraph) { 053 this.backingGraph = backingGraph; 054 } 055 056 /** Returns an immutable copy of {@code graph}. */ 057 public static <N> ImmutableGraph<N> copyOf(Graph<N> graph) { 058 return (graph instanceof ImmutableGraph) 059 ? (ImmutableGraph<N>) graph 060 : new ImmutableGraph<N>( 061 new ConfigurableValueGraph<N, Presence>( 062 GraphBuilder.from(graph), getNodeConnections(graph), graph.edges().size())); 063 } 064 065 /** 066 * Simply returns its argument. 067 * 068 * @deprecated no need to use this 069 */ 070 @Deprecated 071 public static <N> ImmutableGraph<N> copyOf(ImmutableGraph<N> graph) { 072 return checkNotNull(graph); 073 } 074 075 private static <N> ImmutableMap<N, GraphConnections<N, Presence>> getNodeConnections( 076 Graph<N> graph) { 077 // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have 078 // whatever ordering the graph's nodes do, so ImmutableSortedMap is unnecessary even if the 079 // input nodes are sorted. 080 ImmutableMap.Builder<N, GraphConnections<N, Presence>> nodeConnections = ImmutableMap.builder(); 081 for (N node : graph.nodes()) { 082 nodeConnections.put(node, connectionsOf(graph, node)); 083 } 084 return nodeConnections.build(); 085 } 086 087 private static <N> GraphConnections<N, Presence> connectionsOf(Graph<N> graph, N node) { 088 Function<Object, Presence> edgeValueFn = Functions.constant(Presence.EDGE_EXISTS); 089 return graph.isDirected() 090 ? DirectedGraphConnections.ofImmutable( 091 graph.predecessors(node), Maps.asMap(graph.successors(node), edgeValueFn)) 092 : UndirectedGraphConnections.ofImmutable( 093 Maps.asMap(graph.adjacentNodes(node), edgeValueFn)); 094 } 095 096 @Override 097 protected BaseGraph<N> delegate() { 098 return backingGraph; 099 } 100 101 /** 102 * A builder for creating {@link ImmutableGraph} instances, especially {@code static final} 103 * graphs. Example: 104 * 105 * <pre>{@code 106 * static final ImmutableGraph<Country> COUNTRY_ADJACENCY_GRAPH = 107 * GraphBuilder.undirected() 108 * .<Country>immutable() 109 * .putEdge(FRANCE, GERMANY) 110 * .putEdge(FRANCE, BELGIUM) 111 * .putEdge(GERMANY, BELGIUM) 112 * .addNode(ICELAND) 113 * .build(); 114 * }</pre> 115 * 116 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 117 * multiple graphs in series. Each new graph contains all the elements of the ones created before 118 * it. 119 * 120 * @since 28.0 121 */ 122 public static class Builder<N> { 123 124 private final MutableGraph<N> mutableGraph; 125 126 Builder(GraphBuilder<N> graphBuilder) { 127 this.mutableGraph = graphBuilder.build(); 128 } 129 130 /** 131 * Adds {@code node} if it is not already present. 132 * 133 * <p><b>Nodes must be unique</b>, just as {@code Map} keys must be. They must also be non-null. 134 * 135 * @return this {@code Builder} object 136 */ 137 @CanIgnoreReturnValue 138 public Builder<N> addNode(N node) { 139 mutableGraph.addNode(node); 140 return this; 141 } 142 143 /** 144 * Adds an edge connecting {@code nodeU} to {@code nodeV} if one is not already present. 145 * 146 * <p>If the graph is directed, the resultant edge will be directed; otherwise, it will be 147 * undirected. 148 * 149 * <p>If {@code nodeU} and {@code nodeV} are not already present in this graph, this method will 150 * silently {@link #addNode(Object) add} {@code nodeU} and {@code nodeV} to the graph. 151 * 152 * @return this {@code Builder} object 153 * @throws IllegalArgumentException if the introduction of the edge would violate {@link 154 * #allowsSelfLoops()} 155 */ 156 @CanIgnoreReturnValue 157 public Builder<N> putEdge(N nodeU, N nodeV) { 158 mutableGraph.putEdge(nodeU, nodeV); 159 return this; 160 } 161 162 /** 163 * Adds an edge connecting {@code endpoints} (in the order, if any, specified by {@code 164 * endpoints}) if one is not already present. 165 * 166 * <p>If this graph is directed, {@code endpoints} must be ordered and the added edge will be 167 * directed; if it is undirected, the added edge will be undirected. 168 * 169 * <p>If this graph is directed, {@code endpoints} must be ordered. 170 * 171 * <p>If either or both endpoints are not already present in this graph, this method will 172 * silently {@link #addNode(Object) add} each missing endpoint to the graph. 173 * 174 * @return this {@code Builder} object 175 * @throws IllegalArgumentException if the introduction of the edge would violate {@link 176 * #allowsSelfLoops()} 177 * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed 178 */ 179 @CanIgnoreReturnValue 180 public Builder<N> putEdge(EndpointPair<N> endpoints) { 181 mutableGraph.putEdge(endpoints); 182 return this; 183 } 184 185 /** 186 * Returns a newly-created {@code ImmutableGraph} based on the contents of this {@code Builder}. 187 */ 188 public ImmutableGraph<N> build() { 189 return ImmutableGraph.copyOf(mutableGraph); 190 } 191 } 192}