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 javax.annotation.CheckForNull; 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 053@ElementTypesAreNonnullByDefault 054public abstract class AbstractNetwork<N, E> implements Network<N, E> { 055 056 @Override 057 public Graph<N> asGraph() { 058 return new AbstractGraph<N>() { 059 @Override 060 public Set<N> nodes() { 061 return AbstractNetwork.this.nodes(); 062 } 063 064 @Override 065 public Set<EndpointPair<N>> edges() { 066 if (allowsParallelEdges()) { 067 return super.edges(); // Defer to AbstractGraph implementation. 068 } 069 070 // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping). 071 return new AbstractSet<EndpointPair<N>>() { 072 @Override 073 public Iterator<EndpointPair<N>> iterator() { 074 return Iterators.transform( 075 AbstractNetwork.this.edges().iterator(), 076 new Function<E, EndpointPair<N>>() { 077 @Override 078 public EndpointPair<N> apply(E edge) { 079 return incidentNodes(edge); 080 } 081 }); 082 } 083 084 @Override 085 public int size() { 086 return AbstractNetwork.this.edges().size(); 087 } 088 089 // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe 090 // operations only in weird cases like checking for an EndpointPair<ArrayList> in a 091 // Network<LinkedList>. 092 @SuppressWarnings("unchecked") 093 @Override 094 public boolean contains(@CheckForNull Object obj) { 095 if (!(obj instanceof EndpointPair)) { 096 return false; 097 } 098 EndpointPair<?> endpointPair = (EndpointPair<?>) obj; 099 return isOrderingCompatible(endpointPair) 100 && nodes().contains(endpointPair.nodeU()) 101 && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV()); 102 } 103 }; 104 } 105 106 @Override 107 public ElementOrder<N> nodeOrder() { 108 return AbstractNetwork.this.nodeOrder(); 109 } 110 111 @Override 112 public ElementOrder<N> incidentEdgeOrder() { 113 // TODO(b/142723300): Return AbstractNetwork.this.incidentEdgeOrder() once Network has that 114 // method. 115 return ElementOrder.unordered(); 116 } 117 118 @Override 119 public boolean isDirected() { 120 return AbstractNetwork.this.isDirected(); 121 } 122 123 @Override 124 public boolean allowsSelfLoops() { 125 return AbstractNetwork.this.allowsSelfLoops(); 126 } 127 128 @Override 129 public Set<N> adjacentNodes(N node) { 130 return AbstractNetwork.this.adjacentNodes(node); 131 } 132 133 @Override 134 public Set<N> predecessors(N node) { 135 return AbstractNetwork.this.predecessors(node); 136 } 137 138 @Override 139 public Set<N> successors(N node) { 140 return AbstractNetwork.this.successors(node); 141 } 142 143 // DO NOT override the AbstractGraph *degree() implementations. 144 }; 145 } 146 147 @Override 148 public int degree(N node) { 149 if (isDirected()) { 150 return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size()); 151 } else { 152 return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size()); 153 } 154 } 155 156 @Override 157 public int inDegree(N node) { 158 return isDirected() ? inEdges(node).size() : degree(node); 159 } 160 161 @Override 162 public int outDegree(N node) { 163 return isDirected() ? outEdges(node).size() : degree(node); 164 } 165 166 @Override 167 public Set<E> adjacentEdges(E edge) { 168 EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network. 169 Set<E> endpointPairIncidentEdges = 170 Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV())); 171 return Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge)); 172 } 173 174 @Override 175 public Set<E> edgesConnecting(N nodeU, N nodeV) { 176 Set<E> outEdgesU = outEdges(nodeU); 177 Set<E> inEdgesV = inEdges(nodeV); 178 return outEdgesU.size() <= inEdgesV.size() 179 ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV))) 180 : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU))); 181 } 182 183 @Override 184 public Set<E> edgesConnecting(EndpointPair<N> endpoints) { 185 validateEndpoints(endpoints); 186 return edgesConnecting(endpoints.nodeU(), endpoints.nodeV()); 187 } 188 189 private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) { 190 return new Predicate<E>() { 191 @Override 192 public boolean apply(E edge) { 193 return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck); 194 } 195 }; 196 } 197 198 @Override 199 public Optional<E> edgeConnecting(N nodeU, N nodeV) { 200 return Optional.ofNullable(edgeConnectingOrNull(nodeU, nodeV)); 201 } 202 203 @Override 204 public Optional<E> edgeConnecting(EndpointPair<N> endpoints) { 205 validateEndpoints(endpoints); 206 return edgeConnecting(endpoints.nodeU(), endpoints.nodeV()); 207 } 208 209 @Override 210 @CheckForNull 211 public E edgeConnectingOrNull(N nodeU, N nodeV) { 212 Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV); 213 switch (edgesConnecting.size()) { 214 case 0: 215 return null; 216 case 1: 217 return edgesConnecting.iterator().next(); 218 default: 219 throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV)); 220 } 221 } 222 223 @Override 224 @CheckForNull 225 public E edgeConnectingOrNull(EndpointPair<N> endpoints) { 226 validateEndpoints(endpoints); 227 return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV()); 228 } 229 230 @Override 231 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 232 checkNotNull(nodeU); 233 checkNotNull(nodeV); 234 return nodes().contains(nodeU) && successors(nodeU).contains(nodeV); 235 } 236 237 @Override 238 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 239 checkNotNull(endpoints); 240 if (!isOrderingCompatible(endpoints)) { 241 return false; 242 } 243 return hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV()); 244 } 245 246 /** 247 * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with 248 * the directionality of this graph. 249 */ 250 protected final void validateEndpoints(EndpointPair<?> endpoints) { 251 checkNotNull(endpoints); 252 checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH); 253 } 254 255 protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) { 256 return endpoints.isOrdered() || !this.isDirected(); 257 } 258 259 @Override 260 public final boolean equals(@CheckForNull Object obj) { 261 if (obj == this) { 262 return true; 263 } 264 if (!(obj instanceof Network)) { 265 return false; 266 } 267 Network<?, ?> other = (Network<?, ?>) obj; 268 269 return isDirected() == other.isDirected() 270 && nodes().equals(other.nodes()) 271 && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other)); 272 } 273 274 @Override 275 public final int hashCode() { 276 return edgeIncidentNodesMap(this).hashCode(); 277 } 278 279 /** Returns a string representation of this network. */ 280 @Override 281 public String toString() { 282 return "isDirected: " 283 + isDirected() 284 + ", allowsParallelEdges: " 285 + allowsParallelEdges() 286 + ", allowsSelfLoops: " 287 + allowsSelfLoops() 288 + ", nodes: " 289 + nodes() 290 + ", edges: " 291 + edgeIncidentNodesMap(this); 292 } 293 294 private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) { 295 Function<E, EndpointPair<N>> edgeToIncidentNodesFn = 296 new Function<E, EndpointPair<N>>() { 297 @Override 298 public EndpointPair<N> apply(E edge) { 299 return network.incidentNodes(edge); 300 } 301 }; 302 return Maps.asMap(network.edges(), edgeToIncidentNodesFn); 303 } 304}