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.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Preconditions.checkState;
22 import static com.google.common.graph.GraphConstants.SELF_LOOPS_NOT_ALLOWED;
23 import static com.google.common.graph.Graphs.checkNonNegative;
24 import static com.google.common.graph.Graphs.checkPositive;
25 import static java.util.Objects.requireNonNull;
26
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import javax.annotation.CheckForNull;
29
30 /**
31 * Standard implementation of {@link MutableValueGraph} that supports both directed and undirected
32 * graphs. Instances of this class should be constructed with {@link ValueGraphBuilder}.
33 *
34 * <p>Time complexities for mutation methods are all O(1) except for {@code removeNode(N node)},
35 * which is in O(d_node) where d_node is the degree of {@code node}.
36 *
37 * @author James Sexton
38 * @author Joshua O'Madadhain
39 * @author Omar Darwish
40 * @param <N> Node parameter type
41 * @param <V> Value parameter type
42 */
43 @ElementTypesAreNonnullByDefault
44 final class StandardMutableValueGraph<N, V> extends StandardValueGraph<N, V>
45 implements MutableValueGraph<N, V> {
46
47 private final ElementOrder<N> incidentEdgeOrder;
48
49 /** Constructs a mutable graph with the properties specified in {@code builder}. */
50 StandardMutableValueGraph(AbstractGraphBuilder<? super N> builder) {
51 super(builder);
52 incidentEdgeOrder = builder.incidentEdgeOrder.cast();
53 }
54
55 @Override
56 public ElementOrder<N> incidentEdgeOrder() {
57 return incidentEdgeOrder;
58 }
59
60 @Override
61 @CanIgnoreReturnValue
62 public boolean addNode(N node) {
63 checkNotNull(node, "node");
64
65 if (containsNode(node)) {
66 return false;
67 }
68
69 addNodeInternal(node);
70 return true;
71 }
72
73 /**
74 * Adds {@code node} to the graph and returns the associated {@link GraphConnections}.
75 *
76 * @throws IllegalStateException if {@code node} is already present
77 */
78 @CanIgnoreReturnValue
79 private GraphConnections<N, V> addNodeInternal(N node) {
80 GraphConnections<N, V> connections = newConnections();
81 checkState(nodeConnections.put(node, connections) == null);
82 return connections;
83 }
84
85 @Override
86 @CanIgnoreReturnValue
87 @CheckForNull
88 public V putEdgeValue(N nodeU, N nodeV, V value) {
89 checkNotNull(nodeU, "nodeU");
90 checkNotNull(nodeV, "nodeV");
91 checkNotNull(value, "value");
92
93 if (!allowsSelfLoops()) {
94 checkArgument(!nodeU.equals(nodeV), SELF_LOOPS_NOT_ALLOWED, nodeU);
95 }
96
97 GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
98 if (connectionsU == null) {
99 connectionsU = addNodeInternal(nodeU);
100 }
101 V previousValue = connectionsU.addSuccessor(nodeV, value);
102 GraphConnections<N, V> connectionsV = nodeConnections.get(nodeV);
103 if (connectionsV == null) {
104 connectionsV = addNodeInternal(nodeV);
105 }
106 connectionsV.addPredecessor(nodeU, value);
107 if (previousValue == null) {
108 checkPositive(++edgeCount);
109 }
110 return previousValue;
111 }
112
113 @Override
114 @CanIgnoreReturnValue
115 @CheckForNull
116 public V putEdgeValue(EndpointPair<N> endpoints, V value) {
117 validateEndpoints(endpoints);
118 return putEdgeValue(endpoints.nodeU(), endpoints.nodeV(), value);
119 }
120
121 @Override
122 @CanIgnoreReturnValue
123 public boolean removeNode(N node) {
124 checkNotNull(node, "node");
125
126 GraphConnections<N, V> connections = nodeConnections.get(node);
127 if (connections == null) {
128 return false;
129 }
130
131 if (allowsSelfLoops()) {
132 // Remove self-loop (if any) first, so we don't get CME while removing incident edges.
133 if (connections.removeSuccessor(node) != null) {
134 connections.removePredecessor(node);
135 --edgeCount;
136 }
137 }
138
139 for (N successor : connections.successors()) {
140 // requireNonNull is safe because the node is a successor.
141 requireNonNull(nodeConnections.getWithoutCaching(successor)).removePredecessor(node);
142 --edgeCount;
143 }
144 if (isDirected()) { // In undirected graphs, the successor and predecessor sets are equal.
145 for (N predecessor : connections.predecessors()) {
146 // requireNonNull is safe because the node is a predecessor.
147 checkState(
148 requireNonNull(nodeConnections.getWithoutCaching(predecessor)).removeSuccessor(node)
149 != null);
150 --edgeCount;
151 }
152 }
153 nodeConnections.remove(node);
154 checkNonNegative(edgeCount);
155 return true;
156 }
157
158 @Override
159 @CanIgnoreReturnValue
160 @CheckForNull
161 public V removeEdge(N nodeU, N nodeV) {
162 checkNotNull(nodeU, "nodeU");
163 checkNotNull(nodeV, "nodeV");
164
165 GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
166 GraphConnections<N, V> connectionsV = nodeConnections.get(nodeV);
167 if (connectionsU == null || connectionsV == null) {
168 return null;
169 }
170
171 V previousValue = connectionsU.removeSuccessor(nodeV);
172 if (previousValue != null) {
173 connectionsV.removePredecessor(nodeU);
174 checkNonNegative(--edgeCount);
175 }
176 return previousValue;
177 }
178
179 @Override
180 @CanIgnoreReturnValue
181 @CheckForNull
182 public V removeEdge(EndpointPair<N> endpoints) {
183 validateEndpoints(endpoints);
184 return removeEdge(endpoints.nodeU(), endpoints.nodeV());
185 }
186
187 private GraphConnections<N, V> newConnections() {
188 return isDirected()
189 ? DirectedGraphConnections.<N, V>of(incidentEdgeOrder)
190 : UndirectedGraphConnections.<N, V>of(incidentEdgeOrder);
191 }
192 }