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 com.google.common.graph.GraphConstants.Presence;
20
21 /**
22 * Standard implementation of {@link MutableGraph} that supports both directed and undirected
23 * graphs. Instances of this class should be constructed with {@link GraphBuilder}.
24 *
25 * <p>Time complexities for mutation methods are all O(1) except for {@code removeNode(N node)},
26 * which is in O(d_node) where d_node is the degree of {@code node}.
27 *
28 * @author James Sexton
29 * @param <N> Node parameter type
30 */
31 @ElementTypesAreNonnullByDefault
32 final class StandardMutableGraph<N> extends ForwardingGraph<N> implements MutableGraph<N> {
33 private final MutableValueGraph<N, Presence> backingValueGraph;
34
35 /** Constructs a {@link MutableGraph} with the properties specified in {@code builder}. */
36 StandardMutableGraph(AbstractGraphBuilder<? super N> builder) {
37 this.backingValueGraph = new StandardMutableValueGraph<>(builder);
38 }
39
40 @Override
41 BaseGraph<N> delegate() {
42 return backingValueGraph;
43 }
44
45 @Override
46 public boolean addNode(N node) {
47 return backingValueGraph.addNode(node);
48 }
49
50 @Override
51 public boolean putEdge(N nodeU, N nodeV) {
52 return backingValueGraph.putEdgeValue(nodeU, nodeV, Presence.EDGE_EXISTS) == null;
53 }
54
55 @Override
56 public boolean putEdge(EndpointPair<N> endpoints) {
57 validateEndpoints(endpoints);
58 return putEdge(endpoints.nodeU(), endpoints.nodeV());
59 }
60
61 @Override
62 public boolean removeNode(N node) {
63 return backingValueGraph.removeNode(node);
64 }
65
66 @Override
67 public boolean removeEdge(N nodeU, N nodeV) {
68 return backingValueGraph.removeEdge(nodeU, nodeV) != null;
69 }
70
71 @Override
72 public boolean removeEdge(EndpointPair<N> endpoints) {
73 validateEndpoints(endpoints);
74 return removeEdge(endpoints.nodeU(), endpoints.nodeV());
75 }
76 }