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