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.PARALLEL_EDGES_NOT_ALLOWED;
23 import static com.google.common.graph.GraphConstants.REUSING_EDGE;
24 import static com.google.common.graph.GraphConstants.SELF_LOOPS_NOT_ALLOWED;
25 import static java.util.Objects.requireNonNull;
26
27 import com.google.common.collect.ImmutableList;
28 import com.google.errorprone.annotations.CanIgnoreReturnValue;
29
30 /**
31 * Standard implementation of {@link MutableNetwork} that supports both directed and undirected
32 * graphs. Instances of this class should be constructed with {@link NetworkBuilder}.
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 <E> Edge parameter type
42 */
43 @ElementTypesAreNonnullByDefault
44 final class StandardMutableNetwork<N, E> extends StandardNetwork<N, E>
45 implements MutableNetwork<N, E> {
46
47 /** Constructs a mutable graph with the properties specified in {@code builder}. */
48 StandardMutableNetwork(NetworkBuilder<? super N, ? super E> builder) {
49 super(builder);
50 }
51
52 @Override
53 @CanIgnoreReturnValue
54 public boolean addNode(N node) {
55 checkNotNull(node, "node");
56
57 if (containsNode(node)) {
58 return false;
59 }
60
61 addNodeInternal(node);
62 return true;
63 }
64
65 /**
66 * Adds {@code node} to the graph and returns the associated {@link NetworkConnections}.
67 *
68 * @throws IllegalStateException if {@code node} is already present
69 */
70 @CanIgnoreReturnValue
71 private NetworkConnections<N, E> addNodeInternal(N node) {
72 NetworkConnections<N, E> connections = newConnections();
73 checkState(nodeConnections.put(node, connections) == null);
74 return connections;
75 }
76
77 @Override
78 @CanIgnoreReturnValue
79 public boolean addEdge(N nodeU, N nodeV, E edge) {
80 checkNotNull(nodeU, "nodeU");
81 checkNotNull(nodeV, "nodeV");
82 checkNotNull(edge, "edge");
83
84 if (containsEdge(edge)) {
85 EndpointPair<N> existingIncidentNodes = incidentNodes(edge);
86 EndpointPair<N> newIncidentNodes = EndpointPair.of(this, nodeU, nodeV);
87 checkArgument(
88 existingIncidentNodes.equals(newIncidentNodes),
89 REUSING_EDGE,
90 edge,
91 existingIncidentNodes,
92 newIncidentNodes);
93 return false;
94 }
95 NetworkConnections<N, E> connectionsU = nodeConnections.get(nodeU);
96 if (!allowsParallelEdges()) {
97 checkArgument(
98 !(connectionsU != null && connectionsU.successors().contains(nodeV)),
99 PARALLEL_EDGES_NOT_ALLOWED,
100 nodeU,
101 nodeV);
102 }
103 boolean isSelfLoop = nodeU.equals(nodeV);
104 if (!allowsSelfLoops()) {
105 checkArgument(!isSelfLoop, SELF_LOOPS_NOT_ALLOWED, nodeU);
106 }
107
108 if (connectionsU == null) {
109 connectionsU = addNodeInternal(nodeU);
110 }
111 connectionsU.addOutEdge(edge, nodeV);
112 NetworkConnections<N, E> connectionsV = nodeConnections.get(nodeV);
113 if (connectionsV == null) {
114 connectionsV = addNodeInternal(nodeV);
115 }
116 connectionsV.addInEdge(edge, nodeU, isSelfLoop);
117 edgeToReferenceNode.put(edge, nodeU);
118 return true;
119 }
120
121 @Override
122 @CanIgnoreReturnValue
123 public boolean addEdge(EndpointPair<N> endpoints, E edge) {
124 validateEndpoints(endpoints);
125 return addEdge(endpoints.nodeU(), endpoints.nodeV(), edge);
126 }
127
128 @Override
129 @CanIgnoreReturnValue
130 public boolean removeNode(N node) {
131 checkNotNull(node, "node");
132
133 NetworkConnections<N, E> connections = nodeConnections.get(node);
134 if (connections == null) {
135 return false;
136 }
137
138 // Since views are returned, we need to copy the edges that will be removed.
139 // Thus we avoid modifying the underlying view while iterating over it.
140 for (E edge : ImmutableList.copyOf(connections.incidentEdges())) {
141 removeEdge(edge);
142 }
143 nodeConnections.remove(node);
144 return true;
145 }
146
147 @Override
148 @CanIgnoreReturnValue
149 public boolean removeEdge(E edge) {
150 checkNotNull(edge, "edge");
151
152 N nodeU = edgeToReferenceNode.get(edge);
153 if (nodeU == null) {
154 return false;
155 }
156
157 // requireNonNull is safe because of the edgeToReferenceNode check above.
158 NetworkConnections<N, E> connectionsU = requireNonNull(nodeConnections.get(nodeU));
159 N nodeV = connectionsU.adjacentNode(edge);
160 NetworkConnections<N, E> connectionsV = requireNonNull(nodeConnections.get(nodeV));
161 connectionsU.removeOutEdge(edge);
162 connectionsV.removeInEdge(edge, allowsSelfLoops() && nodeU.equals(nodeV));
163 edgeToReferenceNode.remove(edge);
164 return true;
165 }
166
167 private NetworkConnections<N, E> newConnections() {
168 return isDirected()
169 ? allowsParallelEdges()
170 ? DirectedMultiNetworkConnections.<N, E>of()
171 : DirectedNetworkConnections.<N, E>of()
172 : allowsParallelEdges()
173 ? UndirectedMultiNetworkConnections.<N, E>of()
174 : UndirectedNetworkConnections.<N, E>of();
175 }
176 }