001/* 002 * Copyright (C) 2016 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.graph; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.graph.GraphConstants.EDGE_REMOVED_FROM_GRAPH; 022import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH; 023import static com.google.common.graph.GraphConstants.MULTIPLE_EDGES_CONNECTING; 024import static com.google.common.graph.GraphConstants.NODE_PAIR_REMOVED_FROM_GRAPH; 025import static com.google.common.graph.GraphConstants.NODE_REMOVED_FROM_GRAPH; 026import static java.util.Collections.unmodifiableSet; 027 028import com.google.common.annotations.Beta; 029import com.google.common.base.Predicate; 030import com.google.common.collect.ImmutableSet; 031import com.google.common.collect.Iterators; 032import com.google.common.collect.Maps; 033import com.google.common.collect.Sets; 034import com.google.common.math.IntMath; 035import java.util.AbstractSet; 036import java.util.Iterator; 037import java.util.Map; 038import java.util.Optional; 039import java.util.Set; 040import javax.annotation.CheckForNull; 041 042/** 043 * This class provides a skeletal implementation of {@link Network}. It is recommended to extend 044 * this class rather than implement {@link Network} directly. 045 * 046 * <p>The methods implemented in this class should not be overridden unless the subclass admits a 047 * more efficient implementation. 048 * 049 * @author James Sexton 050 * @param <N> Node parameter type 051 * @param <E> Edge parameter type 052 * @since 20.0 053 */ 054@Beta 055@ElementTypesAreNonnullByDefault 056public abstract class AbstractNetwork<N, E> implements Network<N, E> { 057 @Override 058 public Graph<N> asGraph() { 059 return new AbstractGraph<N>() { 060 @Override 061 public Set<N> nodes() { 062 return AbstractNetwork.this.nodes(); 063 } 064 065 @Override 066 public Set<EndpointPair<N>> edges() { 067 if (allowsParallelEdges()) { 068 return super.edges(); // Defer to AbstractGraph implementation. 069 } 070 071 // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping). 072 return new AbstractSet<EndpointPair<N>>() { 073 @Override 074 public Iterator<EndpointPair<N>> iterator() { 075 return Iterators.transform( 076 AbstractNetwork.this.edges().iterator(), edge -> incidentNodes(edge)); 077 } 078 079 @Override 080 public int size() { 081 return AbstractNetwork.this.edges().size(); 082 } 083 084 // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe 085 // operations only in weird cases like checking for an EndpointPair<ArrayList> in a 086 // Network<LinkedList>. 087 @SuppressWarnings("unchecked") 088 @Override 089 public boolean contains(@CheckForNull Object obj) { 090 if (!(obj instanceof EndpointPair)) { 091 return false; 092 } 093 EndpointPair<?> endpointPair = (EndpointPair<?>) obj; 094 return isOrderingCompatible(endpointPair) 095 && nodes().contains(endpointPair.nodeU()) 096 && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV()); 097 } 098 }; 099 } 100 101 @Override 102 public ElementOrder<N> nodeOrder() { 103 return AbstractNetwork.this.nodeOrder(); 104 } 105 106 @Override 107 public ElementOrder<N> incidentEdgeOrder() { 108 // TODO(b/142723300): Return AbstractNetwork.this.incidentEdgeOrder() once Network has that 109 // method. 110 return ElementOrder.unordered(); 111 } 112 113 @Override 114 public boolean isDirected() { 115 return AbstractNetwork.this.isDirected(); 116 } 117 118 @Override 119 public boolean allowsSelfLoops() { 120 return AbstractNetwork.this.allowsSelfLoops(); 121 } 122 123 @Override 124 public Set<N> adjacentNodes(N node) { 125 return AbstractNetwork.this.adjacentNodes(node); 126 } 127 128 @Override 129 public Set<N> predecessors(N node) { 130 return AbstractNetwork.this.predecessors(node); 131 } 132 133 @Override 134 public Set<N> successors(N node) { 135 return AbstractNetwork.this.successors(node); 136 } 137 138 // DO NOT override the AbstractGraph *degree() implementations. 139 }; 140 } 141 142 @Override 143 public int degree(N node) { 144 if (isDirected()) { 145 return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size()); 146 } else { 147 return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size()); 148 } 149 } 150 151 @Override 152 public int inDegree(N node) { 153 return isDirected() ? inEdges(node).size() : degree(node); 154 } 155 156 @Override 157 public int outDegree(N node) { 158 return isDirected() ? outEdges(node).size() : degree(node); 159 } 160 161 @Override 162 public Set<E> adjacentEdges(E edge) { 163 EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network. 164 Set<E> endpointPairIncidentEdges = 165 Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV())); 166 return edgeInvalidatableSet( 167 Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge)), edge); 168 } 169 170 @Override 171 public Set<E> edgesConnecting(N nodeU, N nodeV) { 172 Set<E> outEdgesU = outEdges(nodeU); 173 Set<E> inEdgesV = inEdges(nodeV); 174 return nodePairInvalidatableSet( 175 outEdgesU.size() <= inEdgesV.size() 176 ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV))) 177 : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU))), 178 nodeU, 179 nodeV); 180 } 181 182 @Override 183 public Set<E> edgesConnecting(EndpointPair<N> endpoints) { 184 validateEndpoints(endpoints); 185 return edgesConnecting(endpoints.nodeU(), endpoints.nodeV()); 186 } 187 188 private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) { 189 return new Predicate<E>() { 190 @Override 191 public boolean apply(E edge) { 192 return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck); 193 } 194 }; 195 } 196 197 @Override 198 public Optional<E> edgeConnecting(N nodeU, N nodeV) { 199 return Optional.ofNullable(edgeConnectingOrNull(nodeU, nodeV)); 200 } 201 202 @Override 203 public Optional<E> edgeConnecting(EndpointPair<N> endpoints) { 204 validateEndpoints(endpoints); 205 return edgeConnecting(endpoints.nodeU(), endpoints.nodeV()); 206 } 207 208 @Override 209 @CheckForNull 210 public E edgeConnectingOrNull(N nodeU, N nodeV) { 211 Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV); 212 switch (edgesConnecting.size()) { 213 case 0: 214 return null; 215 case 1: 216 return edgesConnecting.iterator().next(); 217 default: 218 throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV)); 219 } 220 } 221 222 @Override 223 @CheckForNull 224 public E edgeConnectingOrNull(EndpointPair<N> endpoints) { 225 validateEndpoints(endpoints); 226 return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV()); 227 } 228 229 @Override 230 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 231 checkNotNull(nodeU); 232 checkNotNull(nodeV); 233 return nodes().contains(nodeU) && successors(nodeU).contains(nodeV); 234 } 235 236 @Override 237 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 238 checkNotNull(endpoints); 239 if (!isOrderingCompatible(endpoints)) { 240 return false; 241 } 242 return hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV()); 243 } 244 245 /** 246 * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with 247 * the directionality of this graph. 248 */ 249 protected final void validateEndpoints(EndpointPair<?> endpoints) { 250 checkNotNull(endpoints); 251 checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH); 252 } 253 254 protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) { 255 return endpoints.isOrdered() == this.isDirected(); 256 } 257 258 @Override 259 public final boolean equals(@CheckForNull Object obj) { 260 if (obj == this) { 261 return true; 262 } 263 if (!(obj instanceof Network)) { 264 return false; 265 } 266 Network<?, ?> other = (Network<?, ?>) obj; 267 268 return isDirected() == other.isDirected() 269 && nodes().equals(other.nodes()) 270 && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other)); 271 } 272 273 @Override 274 public final int hashCode() { 275 return edgeIncidentNodesMap(this).hashCode(); 276 } 277 278 /** Returns a string representation of this network. */ 279 @Override 280 public String toString() { 281 return "isDirected: " 282 + isDirected() 283 + ", allowsParallelEdges: " 284 + allowsParallelEdges() 285 + ", allowsSelfLoops: " 286 + allowsSelfLoops() 287 + ", nodes: " 288 + nodes() 289 + ", edges: " 290 + edgeIncidentNodesMap(this); 291 } 292 293 /** 294 * Returns a {@link Set} whose methods throw {@link IllegalStateException} when the given edge is 295 * not present in this network. 296 * 297 * @since 33.1.0 298 */ 299 protected final <T> Set<T> edgeInvalidatableSet(Set<T> set, E edge) { 300 return InvalidatableSet.of( 301 set, () -> edges().contains(edge), () -> String.format(EDGE_REMOVED_FROM_GRAPH, edge)); 302 } 303 304 /** 305 * Returns a {@link Set} whose methods throw {@link IllegalStateException} when the given node is 306 * not present in this network. 307 * 308 * @since 33.1.0 309 */ 310 protected final <T> Set<T> nodeInvalidatableSet(Set<T> set, N node) { 311 return InvalidatableSet.of( 312 set, () -> nodes().contains(node), () -> String.format(NODE_REMOVED_FROM_GRAPH, node)); 313 } 314 315 /** 316 * Returns a {@link Set} whose methods throw {@link IllegalStateException} when either of the 317 * given nodes is not present in this network. 318 * 319 * @since 33.1.0 320 */ 321 protected final <T> Set<T> nodePairInvalidatableSet(Set<T> set, N nodeU, N nodeV) { 322 return InvalidatableSet.of( 323 set, 324 () -> nodes().contains(nodeU) && nodes().contains(nodeV), 325 () -> String.format(NODE_PAIR_REMOVED_FROM_GRAPH, nodeU, nodeV)); 326 } 327 328 private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) { 329 return Maps.asMap(network.edges(), network::incidentNodes); 330 } 331}