View Javadoc
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 com.google.common.graph.GraphConstants.DEFAULT_NODE_COUNT;
21  import static com.google.common.graph.Graphs.checkNonNegative;
22  
23  import java.util.Map;
24  import java.util.Set;
25  import java.util.TreeMap;
26  import javax.annotation.Nullable;
27  
28  /**
29   * Configurable implementation of {@link ValueGraph} that supports the options supplied by {@link
30   * AbstractGraphBuilder}.
31   *
32   * <p>This class maintains a map of nodes to {@link GraphConnections}.
33   *
34   * <p>Collection-returning accessors return unmodifiable views: the view returned will reflect
35   * changes to the graph (if the graph is mutable) but may not be modified by the user.
36   *
37   * <p>The time complexity of all collection-returning accessors is O(1), since views are returned.
38   *
39   * @author James Sexton
40   * @author Joshua O'Madadhain
41   * @author Omar Darwish
42   * @param <N> Node parameter type
43   * @param <V> Value parameter type
44   */
45  class ConfigurableValueGraph<N, V> extends AbstractValueGraph<N, V> {
46    private final boolean isDirected;
47    private final boolean allowsSelfLoops;
48    private final ElementOrder<N> nodeOrder;
49  
50    protected final MapIteratorCache<N, GraphConnections<N, V>> nodeConnections;
51  
52    protected long edgeCount; // must be updated when edges are added or removed
53  
54    /** Constructs a graph with the properties specified in {@code builder}. */
55    ConfigurableValueGraph(AbstractGraphBuilder<? super N> builder) {
56      this(
57          builder,
58          builder.nodeOrder.<N, GraphConnections<N, V>>createMap(
59              builder.expectedNodeCount.or(DEFAULT_NODE_COUNT)),
60          0L);
61    }
62  
63    /**
64     * Constructs a graph with the properties specified in {@code builder}, initialized with the given
65     * node map.
66     */
67    ConfigurableValueGraph(
68        AbstractGraphBuilder<? super N> builder,
69        Map<N, GraphConnections<N, V>> nodeConnections,
70        long edgeCount) {
71      this.isDirected = builder.directed;
72      this.allowsSelfLoops = builder.allowsSelfLoops;
73      this.nodeOrder = builder.nodeOrder.cast();
74      // Prefer the heavier "MapRetrievalCache" for nodes if lookup is expensive.
75      this.nodeConnections =
76          (nodeConnections instanceof TreeMap)
77              ? new MapRetrievalCache<N, GraphConnections<N, V>>(nodeConnections)
78              : new MapIteratorCache<N, GraphConnections<N, V>>(nodeConnections);
79      this.edgeCount = checkNonNegative(edgeCount);
80    }
81  
82    @Override
83    public Set<N> nodes() {
84      return nodeConnections.unmodifiableKeySet();
85    }
86  
87    @Override
88    public boolean isDirected() {
89      return isDirected;
90    }
91  
92    @Override
93    public boolean allowsSelfLoops() {
94      return allowsSelfLoops;
95    }
96  
97    @Override
98    public ElementOrder<N> nodeOrder() {
99      return nodeOrder;
100   }
101 
102   @Override
103   public Set<N> adjacentNodes(N node) {
104     return checkedConnections(node).adjacentNodes();
105   }
106 
107   @Override
108   public Set<N> predecessors(N node) {
109     return checkedConnections(node).predecessors();
110   }
111 
112   @Override
113   public Set<N> successors(N node) {
114     return checkedConnections(node).successors();
115   }
116 
117   @Override
118   public boolean hasEdgeConnecting(N nodeU, N nodeV) {
119     checkNotNull(nodeU);
120     checkNotNull(nodeV);
121     GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
122     return (connectionsU != null) && connectionsU.successors().contains(nodeV);
123   }
124 
125   @Override
126   @Nullable
127   public V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
128     checkNotNull(nodeU);
129     checkNotNull(nodeV);
130     GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
131     V value = (connectionsU == null) ? null : connectionsU.value(nodeV);
132     return value == null ? defaultValue : value;
133   }
134 
135   @Override
136   protected long edgeCount() {
137     return edgeCount;
138   }
139 
140   protected final GraphConnections<N, V> checkedConnections(N node) {
141     GraphConnections<N, V> connections = nodeConnections.get(node);
142     if (connections == null) {
143       checkNotNull(node);
144       throw new IllegalArgumentException("Node " + node + " is not an element of this graph.");
145     }
146     return connections;
147   }
148 
149   protected final boolean containsNode(@Nullable N node) {
150     return nodeConnections.containsKey(node);
151   }
152 }