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.Immutable; 028 029/** 030 * A {@link Graph} whose elements and structural relationships will never change. Instances of this 031 * class may be obtained with {@link #copyOf(Graph)}. 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 Joshua O'Madadhain 040 * @author Omar Darwish 041 * @param <N> Node parameter type 042 * @since 20.0 043 */ 044@Beta 045@Immutable(containerOf = {"N"}) 046public class ImmutableGraph<N> extends ForwardingGraph<N> { 047 @SuppressWarnings("Immutable") // The backing graph must be immutable. 048 private final BaseGraph<N> backingGraph; 049 050 ImmutableGraph(BaseGraph<N> backingGraph) { 051 this.backingGraph = backingGraph; 052 } 053 054 /** Returns an immutable copy of {@code graph}. */ 055 public static <N> ImmutableGraph<N> copyOf(Graph<N> graph) { 056 return (graph instanceof ImmutableGraph) 057 ? (ImmutableGraph<N>) graph 058 : new ImmutableGraph<N>( 059 new ConfigurableValueGraph<N, Presence>( 060 GraphBuilder.from(graph), getNodeConnections(graph), graph.edges().size())); 061 } 062 063 /** 064 * Simply returns its argument. 065 * 066 * @deprecated no need to use this 067 */ 068 @Deprecated 069 public static <N> ImmutableGraph<N> copyOf(ImmutableGraph<N> graph) { 070 return checkNotNull(graph); 071 } 072 073 private static <N> ImmutableMap<N, GraphConnections<N, Presence>> getNodeConnections( 074 Graph<N> graph) { 075 // ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have 076 // whatever ordering the graph's nodes do, so ImmutableSortedMap is unnecessary even if the 077 // input nodes are sorted. 078 ImmutableMap.Builder<N, GraphConnections<N, Presence>> nodeConnections = ImmutableMap.builder(); 079 for (N node : graph.nodes()) { 080 nodeConnections.put(node, connectionsOf(graph, node)); 081 } 082 return nodeConnections.build(); 083 } 084 085 private static <N> GraphConnections<N, Presence> connectionsOf(Graph<N> graph, N node) { 086 Function<Object, Presence> edgeValueFn = Functions.constant(Presence.EDGE_EXISTS); 087 return graph.isDirected() 088 ? DirectedGraphConnections.ofImmutable( 089 graph.predecessors(node), Maps.asMap(graph.successors(node), edgeValueFn)) 090 : UndirectedGraphConnections.ofImmutable( 091 Maps.asMap(graph.adjacentNodes(node), edgeValueFn)); 092 } 093 094 @Override 095 protected BaseGraph<N> delegate() { 096 return backingGraph; 097 } 098}