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.ENDPOINTS_MISMATCH; 022import static com.google.common.graph.GraphConstants.MULTIPLE_EDGES_CONNECTING; 023import static java.util.Collections.unmodifiableSet; 024 025import com.google.common.annotations.Beta; 026import com.google.common.base.Function; 027import com.google.common.base.Predicate; 028import com.google.common.collect.ImmutableSet; 029import com.google.common.collect.Iterators; 030import com.google.common.collect.Maps; 031import com.google.common.collect.Sets; 032import com.google.common.math.IntMath; 033import java.util.AbstractSet; 034import java.util.Iterator; 035import java.util.Map; 036import java.util.Optional; 037import java.util.Set; 038import org.checkerframework.checker.nullness.qual.Nullable; 039 040/** 041 * This class provides a skeletal implementation of {@link Network}. It is recommended to extend 042 * this class rather than implement {@link Network} directly. 043 * 044 * <p>The methods implemented in this class should not be overridden unless the subclass admits a 045 * more efficient implementation. 046 * 047 * @author James Sexton 048 * @param <N> Node parameter type 049 * @param <E> Edge parameter type 050 * @since 20.0 051 */ 052@Beta 053public abstract class AbstractNetwork<N, E> implements Network<N, E> { 054 055 @Override 056 public Graph<N> asGraph() { 057 return new AbstractGraph<N>() { 058 @Override 059 public Set<N> nodes() { 060 return AbstractNetwork.this.nodes(); 061 } 062 063 @Override 064 public Set<EndpointPair<N>> edges() { 065 if (allowsParallelEdges()) { 066 return super.edges(); // Defer to AbstractGraph implementation. 067 } 068 069 // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping). 070 return new AbstractSet<EndpointPair<N>>() { 071 @Override 072 public Iterator<EndpointPair<N>> iterator() { 073 return Iterators.transform( 074 AbstractNetwork.this.edges().iterator(), 075 new Function<E, EndpointPair<N>>() { 076 @Override 077 public EndpointPair<N> apply(E edge) { 078 return incidentNodes(edge); 079 } 080 }); 081 } 082 083 @Override 084 public int size() { 085 return AbstractNetwork.this.edges().size(); 086 } 087 088 // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe 089 // operations only in weird cases like checking for an EndpointPair<ArrayList> in a 090 // Network<LinkedList>. 091 @SuppressWarnings("unchecked") 092 @Override 093 public boolean contains(@Nullable Object obj) { 094 if (!(obj instanceof EndpointPair)) { 095 return false; 096 } 097 EndpointPair<?> endpointPair = (EndpointPair<?>) obj; 098 return isOrderingCompatible(endpointPair) 099 && nodes().contains(endpointPair.nodeU()) 100 && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV()); 101 } 102 }; 103 } 104 105 @Override 106 public ElementOrder<N> nodeOrder() { 107 return AbstractNetwork.this.nodeOrder(); 108 } 109 110 @Override 111 public boolean isDirected() { 112 return AbstractNetwork.this.isDirected(); 113 } 114 115 @Override 116 public boolean allowsSelfLoops() { 117 return AbstractNetwork.this.allowsSelfLoops(); 118 } 119 120 @Override 121 public Set<N> adjacentNodes(N node) { 122 return AbstractNetwork.this.adjacentNodes(node); 123 } 124 125 @Override 126 public Set<N> predecessors(N node) { 127 return AbstractNetwork.this.predecessors(node); 128 } 129 130 @Override 131 public Set<N> successors(N node) { 132 return AbstractNetwork.this.successors(node); 133 } 134 135 // DO NOT override the AbstractGraph *degree() implementations. 136 }; 137 } 138 139 @Override 140 public int degree(N node) { 141 if (isDirected()) { 142 return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size()); 143 } else { 144 return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size()); 145 } 146 } 147 148 @Override 149 public int inDegree(N node) { 150 return isDirected() ? inEdges(node).size() : degree(node); 151 } 152 153 @Override 154 public int outDegree(N node) { 155 return isDirected() ? outEdges(node).size() : degree(node); 156 } 157 158 @Override 159 public Set<E> adjacentEdges(E edge) { 160 EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network. 161 Set<E> endpointPairIncidentEdges = 162 Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV())); 163 return Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge)); 164 } 165 166 @Override 167 public Set<E> edgesConnecting(N nodeU, N nodeV) { 168 Set<E> outEdgesU = outEdges(nodeU); 169 Set<E> inEdgesV = inEdges(nodeV); 170 return outEdgesU.size() <= inEdgesV.size() 171 ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV))) 172 : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU))); 173 } 174 175 @Override 176 public Set<E> edgesConnecting(EndpointPair<N> endpoints) { 177 validateEndpoints(endpoints); 178 return edgesConnecting(endpoints.nodeU(), endpoints.nodeV()); 179 } 180 181 private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) { 182 return new Predicate<E>() { 183 @Override 184 public boolean apply(E edge) { 185 return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck); 186 } 187 }; 188 } 189 190 @Override 191 public Optional<E> edgeConnecting(N nodeU, N nodeV) { 192 return Optional.ofNullable(edgeConnectingOrNull(nodeU, nodeV)); 193 } 194 195 @Override 196 public Optional<E> edgeConnecting(EndpointPair<N> endpoints) { 197 validateEndpoints(endpoints); 198 return edgeConnecting(endpoints.nodeU(), endpoints.nodeV()); 199 } 200 201 @Override 202 public @Nullable E edgeConnectingOrNull(N nodeU, N nodeV) { 203 Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV); 204 switch (edgesConnecting.size()) { 205 case 0: 206 return null; 207 case 1: 208 return edgesConnecting.iterator().next(); 209 default: 210 throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV)); 211 } 212 } 213 214 @Override 215 public @Nullable E edgeConnectingOrNull(EndpointPair<N> endpoints) { 216 validateEndpoints(endpoints); 217 return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV()); 218 } 219 220 @Override 221 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 222 return !edgesConnecting(nodeU, nodeV).isEmpty(); 223 } 224 225 @Override 226 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 227 checkNotNull(endpoints); 228 if (!isOrderingCompatible(endpoints)) { 229 return false; 230 } 231 return !edgesConnecting(endpoints.nodeU(), endpoints.nodeV()).isEmpty(); 232 } 233 234 /** 235 * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with 236 * the directionality of this graph. 237 */ 238 protected final void validateEndpoints(EndpointPair<?> endpoints) { 239 checkNotNull(endpoints); 240 checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH); 241 } 242 243 protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) { 244 return endpoints.isOrdered() || !this.isDirected(); 245 } 246 247 @Override 248 public final boolean equals(@Nullable Object obj) { 249 if (obj == this) { 250 return true; 251 } 252 if (!(obj instanceof Network)) { 253 return false; 254 } 255 Network<?, ?> other = (Network<?, ?>) obj; 256 257 return isDirected() == other.isDirected() 258 && nodes().equals(other.nodes()) 259 && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other)); 260 } 261 262 @Override 263 public final int hashCode() { 264 return edgeIncidentNodesMap(this).hashCode(); 265 } 266 267 /** Returns a string representation of this network. */ 268 @Override 269 public String toString() { 270 return "isDirected: " 271 + isDirected() 272 + ", allowsParallelEdges: " 273 + allowsParallelEdges() 274 + ", allowsSelfLoops: " 275 + allowsSelfLoops() 276 + ", nodes: " 277 + nodes() 278 + ", edges: " 279 + edgeIncidentNodesMap(this); 280 } 281 282 private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) { 283 Function<E, EndpointPair<N>> edgeToIncidentNodesFn = 284 new Function<E, EndpointPair<N>>() { 285 @Override 286 public EndpointPair<N> apply(E edge) { 287 return network.incidentNodes(edge); 288 } 289 }; 290 return Maps.asMap(network.edges(), edgeToIncidentNodesFn); 291 } 292}