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