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.Iterator;
24 import java.util.Map;
25 import java.util.Set;
26 import java.util.TreeMap;
27 import javax.annotation.CheckForNull;
28
29 /**
30 * Standard implementation of {@link ValueGraph} that supports the options supplied by {@link
31 * AbstractGraphBuilder}.
32 *
33 * <p>This class maintains a map of nodes to {@link GraphConnections}.
34 *
35 * <p>Collection-returning accessors return unmodifiable views: the view returned will reflect
36 * changes to the graph (if the graph is mutable) but may not be modified by the user.
37 *
38 * <p>The time complexity of all collection-returning accessors is O(1), since views are returned.
39 *
40 * @author James Sexton
41 * @author Joshua O'Madadhain
42 * @author Omar Darwish
43 * @param <N> Node parameter type
44 * @param <V> Value parameter type
45 */
46 @ElementTypesAreNonnullByDefault
47 class StandardValueGraph<N, V> extends AbstractValueGraph<N, V> {
48 private final boolean isDirected;
49 private final boolean allowsSelfLoops;
50 private final ElementOrder<N> nodeOrder;
51
52 final MapIteratorCache<N, GraphConnections<N, V>> nodeConnections;
53
54 long edgeCount; // must be updated when edges are added or removed
55
56 /** Constructs a graph with the properties specified in {@code builder}. */
57 StandardValueGraph(AbstractGraphBuilder<? super N> builder) {
58 this(
59 builder,
60 builder.nodeOrder.<N, GraphConnections<N, V>>createMap(
61 builder.expectedNodeCount.or(DEFAULT_NODE_COUNT)),
62 0L);
63 }
64
65 /**
66 * Constructs a graph with the properties specified in {@code builder}, initialized with the given
67 * node map.
68 */
69 StandardValueGraph(
70 AbstractGraphBuilder<? super N> builder,
71 Map<N, GraphConnections<N, V>> nodeConnections,
72 long edgeCount) {
73 this.isDirected = builder.directed;
74 this.allowsSelfLoops = builder.allowsSelfLoops;
75 this.nodeOrder = builder.nodeOrder.cast();
76 // Prefer the heavier "MapRetrievalCache" for nodes if lookup is expensive.
77 this.nodeConnections =
78 (nodeConnections instanceof TreeMap)
79 ? new MapRetrievalCache<N, GraphConnections<N, V>>(nodeConnections)
80 : new MapIteratorCache<N, GraphConnections<N, V>>(nodeConnections);
81 this.edgeCount = checkNonNegative(edgeCount);
82 }
83
84 @Override
85 public Set<N> nodes() {
86 return nodeConnections.unmodifiableKeySet();
87 }
88
89 @Override
90 public boolean isDirected() {
91 return isDirected;
92 }
93
94 @Override
95 public boolean allowsSelfLoops() {
96 return allowsSelfLoops;
97 }
98
99 @Override
100 public ElementOrder<N> nodeOrder() {
101 return nodeOrder;
102 }
103
104 @Override
105 public Set<N> adjacentNodes(N node) {
106 return checkedConnections(node).adjacentNodes();
107 }
108
109 @Override
110 public Set<N> predecessors(N node) {
111 return checkedConnections(node).predecessors();
112 }
113
114 @Override
115 public Set<N> successors(N node) {
116 return checkedConnections(node).successors();
117 }
118
119 @Override
120 public Set<EndpointPair<N>> incidentEdges(N node) {
121 final GraphConnections<N, V> connections = checkedConnections(node);
122
123 return new IncidentEdgeSet<N>(this, node) {
124 @Override
125 public Iterator<EndpointPair<N>> iterator() {
126 return connections.incidentEdgeIterator(node);
127 }
128 };
129 }
130
131 @Override
132 public boolean hasEdgeConnecting(N nodeU, N nodeV) {
133 return hasEdgeConnectingInternal(checkNotNull(nodeU), checkNotNull(nodeV));
134 }
135
136 @Override
137 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
138 checkNotNull(endpoints);
139 return isOrderingCompatible(endpoints)
140 && hasEdgeConnectingInternal(endpoints.nodeU(), endpoints.nodeV());
141 }
142
143 @Override
144 @CheckForNull
145 public V edgeValueOrDefault(N nodeU, N nodeV, @CheckForNull V defaultValue) {
146 return edgeValueOrDefaultInternal(checkNotNull(nodeU), checkNotNull(nodeV), defaultValue);
147 }
148
149 @Override
150 @CheckForNull
151 public V edgeValueOrDefault(EndpointPair<N> endpoints, @CheckForNull V defaultValue) {
152 validateEndpoints(endpoints);
153 return edgeValueOrDefaultInternal(endpoints.nodeU(), endpoints.nodeV(), defaultValue);
154 }
155
156 @Override
157 protected long edgeCount() {
158 return edgeCount;
159 }
160
161 private final GraphConnections<N, V> checkedConnections(N node) {
162 GraphConnections<N, V> connections = nodeConnections.get(node);
163 if (connections == null) {
164 checkNotNull(node);
165 throw new IllegalArgumentException("Node " + node + " is not an element of this graph.");
166 }
167 return connections;
168 }
169
170 final boolean containsNode(@CheckForNull N node) {
171 return nodeConnections.containsKey(node);
172 }
173
174 private final boolean hasEdgeConnectingInternal(N nodeU, N nodeV) {
175 GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
176 return (connectionsU != null) && connectionsU.successors().contains(nodeV);
177 }
178
179 @CheckForNull
180 private final V edgeValueOrDefaultInternal(N nodeU, N nodeV, @CheckForNull V defaultValue) {
181 GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
182 V value = (connectionsU == null) ? null : connectionsU.value(nodeV);
183 // TODO(cpovirk): Switch back to a ternary once our checker allows it.
184 if (value == null) {
185 return defaultValue;
186 } else {
187 return value;
188 }
189 }
190 }