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}. */ StandardMutableNetwork(NetworkBuilder<? super N, ? super E> builder)48 StandardMutableNetwork(NetworkBuilder<? super N, ? super E> builder) { 49 super(builder); 50 } 51 52 @Override 53 @CanIgnoreReturnValue addNode(N node)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 addNodeInternal(N node)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 addEdge(N nodeU, N nodeV, E edge)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 addEdge(EndpointPair<N> endpoints, E edge)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 removeNode(N node)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 removeEdge(E edge)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 newConnections()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 } 177