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.graph.GraphConstants.DEFAULT_EDGE_COUNT;
22 import static com.google.common.graph.GraphConstants.DEFAULT_NODE_COUNT;
23 import static com.google.common.graph.GraphConstants.EDGE_NOT_IN_GRAPH;
24 import static com.google.common.graph.GraphConstants.NODE_NOT_IN_GRAPH;
25 import static java.util.Objects.requireNonNull;
26
27 import com.google.common.collect.ImmutableSet;
28 import java.util.Map;
29 import java.util.Set;
30 import java.util.TreeMap;
31
32 /**
33 * Standard implementation of {@link Network} that supports the options supplied by {@link
34 * NetworkBuilder}.
35 *
36 * <p>This class maintains a map of nodes to {@link NetworkConnections}. This class also maintains a
37 * map of edges to reference nodes. The reference node is defined to be the edge's source node on
38 * directed graphs, and an arbitrary endpoint of the edge on undirected graphs.
39 *
40 * <p>Collection-returning accessors return unmodifiable views: the view returned will reflect
41 * changes to the graph (if the graph is mutable) but may not be modified by the user.
42 *
43 * <p>The time complexity of all collection-returning accessors is O(1), since views are returned.
44 *
45 * @author James Sexton
46 * @author Joshua O'Madadhain
47 * @author Omar Darwish
48 * @param <N> Node parameter type
49 * @param <E> Edge parameter type
50 */
51 @ElementTypesAreNonnullByDefault
52 class StandardNetwork<N, E> extends AbstractNetwork<N, E> {
53 private final boolean isDirected;
54 private final boolean allowsParallelEdges;
55 private final boolean allowsSelfLoops;
56 private final ElementOrder<N> nodeOrder;
57 private final ElementOrder<E> edgeOrder;
58
59 final MapIteratorCache<N, NetworkConnections<N, E>> nodeConnections;
60
61 // We could make this a Map<E, EndpointPair<N>>. It would make incidentNodes(edge) slightly
62 // faster, but also make Networks consume 5 to 20+% (increasing with average degree) more memory.
63 final MapIteratorCache<E, N> edgeToReferenceNode; // referenceNode == source if directed
64
65 /** Constructs a graph with the properties specified in {@code builder}. */
66 StandardNetwork(NetworkBuilder<? super N, ? super E> builder) {
67 this(
68 builder,
69 builder.nodeOrder.<N, NetworkConnections<N, E>>createMap(
70 builder.expectedNodeCount.or(DEFAULT_NODE_COUNT)),
71 builder.edgeOrder.<E, N>createMap(builder.expectedEdgeCount.or(DEFAULT_EDGE_COUNT)));
72 }
73
74 /**
75 * Constructs a graph with the properties specified in {@code builder}, initialized with the given
76 * node and edge maps.
77 */
78 StandardNetwork(
79 NetworkBuilder<? super N, ? super E> builder,
80 Map<N, NetworkConnections<N, E>> nodeConnections,
81 Map<E, N> edgeToReferenceNode) {
82 this.isDirected = builder.directed;
83 this.allowsParallelEdges = builder.allowsParallelEdges;
84 this.allowsSelfLoops = builder.allowsSelfLoops;
85 this.nodeOrder = builder.nodeOrder.cast();
86 this.edgeOrder = builder.edgeOrder.cast();
87 // Prefer the heavier "MapRetrievalCache" for nodes if lookup is expensive. This optimizes
88 // methods that access the same node(s) repeatedly, such as Graphs.removeEdgesConnecting().
89 this.nodeConnections =
90 (nodeConnections instanceof TreeMap)
91 ? new MapRetrievalCache<N, NetworkConnections<N, E>>(nodeConnections)
92 : new MapIteratorCache<N, NetworkConnections<N, E>>(nodeConnections);
93 this.edgeToReferenceNode = new MapIteratorCache<>(edgeToReferenceNode);
94 }
95
96 @Override
97 public Set<N> nodes() {
98 return nodeConnections.unmodifiableKeySet();
99 }
100
101 @Override
102 public Set<E> edges() {
103 return edgeToReferenceNode.unmodifiableKeySet();
104 }
105
106 @Override
107 public boolean isDirected() {
108 return isDirected;
109 }
110
111 @Override
112 public boolean allowsParallelEdges() {
113 return allowsParallelEdges;
114 }
115
116 @Override
117 public boolean allowsSelfLoops() {
118 return allowsSelfLoops;
119 }
120
121 @Override
122 public ElementOrder<N> nodeOrder() {
123 return nodeOrder;
124 }
125
126 @Override
127 public ElementOrder<E> edgeOrder() {
128 return edgeOrder;
129 }
130
131 @Override
132 public Set<E> incidentEdges(N node) {
133 return checkedConnections(node).incidentEdges();
134 }
135
136 @Override
137 public EndpointPair<N> incidentNodes(E edge) {
138 N nodeU = checkedReferenceNode(edge);
139 // requireNonNull is safe because checkedReferenceNode made sure the edge is in the network.
140 N nodeV = requireNonNull(nodeConnections.get(nodeU)).adjacentNode(edge);
141 return EndpointPair.of(this, nodeU, nodeV);
142 }
143
144 @Override
145 public Set<N> adjacentNodes(N node) {
146 return checkedConnections(node).adjacentNodes();
147 }
148
149 @Override
150 public Set<E> edgesConnecting(N nodeU, N nodeV) {
151 NetworkConnections<N, E> connectionsU = checkedConnections(nodeU);
152 if (!allowsSelfLoops && nodeU == nodeV) { // just an optimization, only check reference equality
153 return ImmutableSet.of();
154 }
155 checkArgument(containsNode(nodeV), NODE_NOT_IN_GRAPH, nodeV);
156 return connectionsU.edgesConnecting(nodeV);
157 }
158
159 @Override
160 public Set<E> inEdges(N node) {
161 return checkedConnections(node).inEdges();
162 }
163
164 @Override
165 public Set<E> outEdges(N node) {
166 return checkedConnections(node).outEdges();
167 }
168
169 @Override
170 public Set<N> predecessors(N node) {
171 return checkedConnections(node).predecessors();
172 }
173
174 @Override
175 public Set<N> successors(N node) {
176 return checkedConnections(node).successors();
177 }
178
179 final NetworkConnections<N, E> checkedConnections(N node) {
180 NetworkConnections<N, E> connections = nodeConnections.get(node);
181 if (connections == null) {
182 checkNotNull(node);
183 throw new IllegalArgumentException(String.format(NODE_NOT_IN_GRAPH, node));
184 }
185 return connections;
186 }
187
188 final N checkedReferenceNode(E edge) {
189 N referenceNode = edgeToReferenceNode.get(edge);
190 if (referenceNode == null) {
191 checkNotNull(edge);
192 throw new IllegalArgumentException(String.format(EDGE_NOT_IN_GRAPH, edge));
193 }
194 return referenceNode;
195 }
196
197 final boolean containsNode(N node) {
198 return nodeConnections.containsKey(node);
199 }
200
201 final boolean containsEdge(E edge) {
202 return edgeToReferenceNode.containsKey(edge);
203 }
204 }