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.checkNotNull; 020import static com.google.common.graph.GraphConstants.NOT_AVAILABLE_ON_UNDIRECTED; 021 022import com.google.common.annotations.Beta; 023import com.google.common.base.Objects; 024import com.google.common.collect.Iterators; 025import com.google.common.collect.UnmodifiableIterator; 026import com.google.errorprone.annotations.Immutable; 027import javax.annotation.CheckForNull; 028 029/** 030 * An immutable pair representing the two endpoints of an edge in a graph. The {@link EndpointPair} 031 * of a directed edge is an ordered pair of nodes ({@link #source()} and {@link #target()}). The 032 * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and 033 * {@link #nodeV()}). 034 * 035 * <p>The edge is a self-loop if, and only if, the two endpoints are equal. 036 * 037 * @author James Sexton 038 * @since 20.0 039 */ 040@Beta 041@Immutable(containerOf = {"N"}) 042@ElementTypesAreNonnullByDefault 043public abstract class EndpointPair<N> implements Iterable<N> { 044 private final N nodeU; 045 private final N nodeV; 046 047 private EndpointPair(N nodeU, N nodeV) { 048 this.nodeU = checkNotNull(nodeU); 049 this.nodeV = checkNotNull(nodeV); 050 } 051 052 /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */ 053 public static <N> EndpointPair<N> ordered(N source, N target) { 054 return new Ordered<>(source, target); 055 } 056 057 /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */ 058 public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) { 059 // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair. 060 return new Unordered<>(nodeV, nodeU); 061 } 062 063 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */ 064 static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) { 065 return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV); 066 } 067 068 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */ 069 static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) { 070 return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV); 071 } 072 073 /** 074 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source. 075 * 076 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered 077 */ 078 public abstract N source(); 079 080 /** 081 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target. 082 * 083 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered 084 */ 085 public abstract N target(); 086 087 /** 088 * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise, 089 * returns an arbitrary (but consistent) endpoint of the origin edge. 090 */ 091 public final N nodeU() { 092 return nodeU; 093 } 094 095 /** 096 * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin 097 * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}. 098 */ 099 public final N nodeV() { 100 return nodeV; 101 } 102 103 /** 104 * Returns the node that is adjacent to {@code node} along the origin edge. 105 * 106 * @throws IllegalArgumentException if this {@link EndpointPair} does not contain {@code node} 107 * @since 20.0 (but the argument type was changed from {@code Object} to {@code N} in 31.0) 108 */ 109 public final N adjacentNode(N node) { 110 if (node.equals(nodeU)) { 111 return nodeV; 112 } else if (node.equals(nodeV)) { 113 return nodeU; 114 } else { 115 throw new IllegalArgumentException("EndpointPair " + this + " does not contain node " + node); 116 } 117 } 118 119 /** 120 * Returns {@code true} if this {@link EndpointPair} is an ordered pair (i.e. represents the 121 * endpoints of a directed edge). 122 */ 123 public abstract boolean isOrdered(); 124 125 /** Iterates in the order {@link #nodeU()}, {@link #nodeV()}. */ 126 @Override 127 public final UnmodifiableIterator<N> iterator() { 128 return Iterators.forArray(nodeU, nodeV); 129 } 130 131 /** 132 * Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()} 133 * are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An 134 * ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}. 135 */ 136 @Override 137 public abstract boolean equals(@CheckForNull Object obj); 138 139 /** 140 * The hashcode of an ordered {@link EndpointPair} is equal to {@code Objects.hashCode(source(), 141 * target())}. The hashcode of an unordered {@link EndpointPair} is equal to {@code 142 * nodeU().hashCode() + nodeV().hashCode()}. 143 */ 144 @Override 145 public abstract int hashCode(); 146 147 private static final class Ordered<N> extends EndpointPair<N> { 148 private Ordered(N source, N target) { 149 super(source, target); 150 } 151 152 @Override 153 public N source() { 154 return nodeU(); 155 } 156 157 @Override 158 public N target() { 159 return nodeV(); 160 } 161 162 @Override 163 public boolean isOrdered() { 164 return true; 165 } 166 167 @Override 168 public boolean equals(@CheckForNull Object obj) { 169 if (obj == this) { 170 return true; 171 } 172 if (!(obj instanceof EndpointPair)) { 173 return false; 174 } 175 176 EndpointPair<?> other = (EndpointPair<?>) obj; 177 if (isOrdered() != other.isOrdered()) { 178 return false; 179 } 180 181 return source().equals(other.source()) && target().equals(other.target()); 182 } 183 184 @Override 185 public int hashCode() { 186 return Objects.hashCode(source(), target()); 187 } 188 189 @Override 190 public String toString() { 191 return "<" + source() + " -> " + target() + ">"; 192 } 193 } 194 195 private static final class Unordered<N> extends EndpointPair<N> { 196 private Unordered(N nodeU, N nodeV) { 197 super(nodeU, nodeV); 198 } 199 200 @Override 201 public N source() { 202 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED); 203 } 204 205 @Override 206 public N target() { 207 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED); 208 } 209 210 @Override 211 public boolean isOrdered() { 212 return false; 213 } 214 215 @Override 216 public boolean equals(@CheckForNull Object obj) { 217 if (obj == this) { 218 return true; 219 } 220 if (!(obj instanceof EndpointPair)) { 221 return false; 222 } 223 224 EndpointPair<?> other = (EndpointPair<?>) obj; 225 if (isOrdered() != other.isOrdered()) { 226 return false; 227 } 228 229 // Equivalent to the following simple implementation: 230 // boolean condition1 = nodeU().equals(other.nodeU()) && nodeV().equals(other.nodeV()); 231 // boolean condition2 = nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); 232 // return condition1 || condition2; 233 if (nodeU().equals(other.nodeU())) { // check condition1 234 // Here's the tricky bit. We don't have to explicitly check for condition2 in this case. 235 // Why? The second half of condition2 requires that nodeV equals other.nodeU. 236 // We already know that nodeU equals other.nodeU. Combined with the earlier statement, 237 // and the transitive property of equality, this implies that nodeU equals nodeV. 238 // If nodeU equals nodeV, condition1 == condition2, so checking condition1 is sufficient. 239 return nodeV().equals(other.nodeV()); 240 } 241 return nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); // check condition2 242 } 243 244 @Override 245 public int hashCode() { 246 return nodeU().hashCode() + nodeV().hashCode(); 247 } 248 249 @Override 250 public String toString() { 251 return "[" + nodeU() + ", " + nodeV() + "]"; 252 } 253 } 254}