001/* 002 * Copyright (C) 2014 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 com.google.common.annotations.Beta; 020import java.util.ConcurrentModificationException; 021import java.util.Map; 022import java.util.Set; 023import javax.annotation.Nullable; 024 025/** 026 * An interface for <a href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a> 027 * data structures. A graph is composed of a set of nodes (sometimes called vertices) and a set of 028 * edges connecting pairs of nodes. Graphs are useful for modeling many kinds of relations. If the 029 * relation to be modeled is symmetric (such as "distance between cities"), that can be represented 030 * with an undirected graph, where an edge that connects node U to node V also connects node V to 031 * node U. If the relation to be modeled is asymmetric (such as "employees managed"), that can be 032 * represented with a directed graph, where edges are strictly one-way. 033 * 034 * <p>There are three main interfaces provided to represent graphs. In order of increasing 035 * complexity they are: {@link Graph}, {@link ValueGraph}, and {@link Network}. You should generally 036 * prefer the simplest interface that satisfies your use case. 037 * 038 * <ol> 039 * <li>Do you have data (objects) that you wish to associate with edges? 040 * <p>Yes: Go to question 2. No: Use {@link Graph}. 041 * <li>Are the objects you wish to associate with edges unique within the scope of a graph? That is, 042 * no two objects would be {@link Object#equals(Object) equal} to each other. A common example 043 * where this would <i>not</i> be the case is with weighted graphs. 044 * <p>Yes: Go to question 3. No: Use {@link ValueGraph}. 045 * <li>Do you need to be able to query the graph for an edge associated with a particular object? 046 * For example, do you need to query what nodes an edge associated with a particular object 047 * connects, or whether an edge associated with that object exists in the graph? 048 * <p>Yes: Use {@link Network}. No: Go to question 4. 049 * <li>Do you need explicit support for parallel edges? For example, do you need to remove one edge 050 * connecting a pair of nodes while leaving other edges connecting those same nodes intact? 051 * <p>Yes: Use {@link Network}. No: Use {@link ValueGraph}. 052 * </ol> 053 * 054 * <p>Although {@link MutableValueGraph} and {@link MutableNetwork} both require users to provide 055 * objects to associate with edges when adding them, the differentiating factor is that in {@link 056 * ValueGraph}s, these objects can be any arbitrary data. Like the values in a {@link Map}, they do 057 * not have to be unique, and can be mutated while in the graph. In a {@link Network}, these objects 058 * serve as keys into the data structure. Like the keys in a {@link Map}, they must be unique, and 059 * cannot be mutated in a way that affects their equals/hashcode or the data structure will become 060 * corrupted. 061 * 062 * <p>In all three interfaces, nodes have all the same requirements as keys in a {@link Map}. 063 * 064 * <p>All mutation methods live on the subinterface {@link MutableNetwork}. If you do not need to 065 * mutate a network (e.g. if you write a method than runs a read-only algorithm on the network), you 066 * should prefer the non-mutating {@link Network} interface. 067 * 068 * <p>We provide an efficient implementation of this interface via {@link NetworkBuilder}. When 069 * using the implementation provided, all collection-returning methods provide live, unmodifiable 070 * views of the network. In other words, you cannot add an element to the collection, but if an 071 * element is added to the {@link Network} that would affect the collection, the collection will be 072 * updated automatically. This also means that you cannot mutate a {@link Network} in a way that 073 * would affect a collection while iterating over that collection. For example, you cannot remove 074 * either {@code foo} or any successors of {@code foo} from the network while iterating over {@code 075 * successors(foo)} (unless you first make a copy of the successors), just as you could not remove 076 * keys from a {@link Map} while iterating over its {@link Map#keySet()}. Behavior in such a case is 077 * undefined, and may result in {@link ConcurrentModificationException}. 078 * 079 * <p>Example of use: 080 * 081 * <pre><code> 082 * MutableNetwork<String, String> roadNetwork = NetworkBuilder.undirected().build(); 083 * roadNetwork.addEdge("Springfield", "Shelbyville", "Monorail"); 084 * roadNetwork.addEdge("New York", "New New York", "Applied Cryogenics"); 085 * roadNetwork.addEdge("Springfield", "New New York", "Secret Wormhole"); 086 * String roadToQuery = "Secret Wormhole"; 087 * if (roadNetwork.edges().contains(roadToQuery)) { 088 * EndpointPair<String> cities = roadNetwork.incidentNodes(roadToQuery); 089 * System.out.format("%s and %s connected via %s", cities.nodeU(), cities.nodeV(), roadToQuery); 090 * } 091 * </code></pre> 092 * 093 * @author James Sexton 094 * @author Joshua O'Madadhain 095 * @param <N> Node parameter type 096 * @param <E> Edge parameter type 097 * @since 20.0 098 */ 099@Beta 100public interface Network<N, E> { 101 // 102 // Network-level accessors 103 // 104 105 /** Returns all nodes in this network, in the order specified by {@link #nodeOrder()}. */ 106 Set<N> nodes(); 107 108 /** Returns all edges in this network, in the order specified by {@link #edgeOrder()}. */ 109 Set<E> edges(); 110 111 /** 112 * Returns a live view of this network as a {@link Graph}. The resulting {@link Graph} will have 113 * an edge connecting node A to node B iff this {@link Network} has an edge connecting A to B. 114 * 115 * <p>If this network {@link #allowsParallelEdges() allows parallel edges}, parallel edges will be 116 * treated as if collapsed into a single edge. For example, the {@link #degree(Object)} of a node 117 * in the {@link Graph} view may be less than the degree of the same node in this {@link Network}. 118 */ 119 Graph<N> asGraph(); 120 121 // 122 // Network properties 123 // 124 125 /** 126 * Returns true if the edges in this network are directed. Directed edges connect a {@link 127 * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while 128 * undirected edges connect a pair of nodes to each other. 129 */ 130 boolean isDirected(); 131 132 /** 133 * Returns true if this network allows parallel edges. Attempting to add a parallel edge to a 134 * network that does not allow them will throw an {@link UnsupportedOperationException}. 135 */ 136 boolean allowsParallelEdges(); 137 138 /** 139 * Returns true if this network allows self-loops (edges that connect a node to itself). 140 * Attempting to add a self-loop to a network that does not allow them will throw an {@link 141 * UnsupportedOperationException}. 142 */ 143 boolean allowsSelfLoops(); 144 145 /** Returns the order of iteration for the elements of {@link #nodes()}. */ 146 ElementOrder<N> nodeOrder(); 147 148 /** Returns the order of iteration for the elements of {@link #edges()}. */ 149 ElementOrder<E> edgeOrder(); 150 151 // 152 // Element-level accessors 153 // 154 155 /** 156 * Returns the nodes which have an incident edge in common with {@code node} in this network. 157 * 158 * @throws IllegalArgumentException if {@code node} is not an element of this network 159 */ 160 Set<N> adjacentNodes(Object node); 161 162 /** 163 * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing 164 * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge. 165 * 166 * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}. 167 * 168 * @throws IllegalArgumentException if {@code node} is not an element of this network 169 */ 170 Set<N> predecessors(Object node); 171 172 /** 173 * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing 174 * {@code node}'s outgoing edges in the direction (if any) of the edge. 175 * 176 * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}. 177 * 178 * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing 179 * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}. 180 * 181 * @throws IllegalArgumentException if {@code node} is not an element of this network 182 */ 183 Set<N> successors(Object node); 184 185 /** 186 * Returns the edges whose {@link #incidentNodes(Object) incident nodes} in this network include 187 * {@code node}. 188 * 189 * @throws IllegalArgumentException if {@code node} is not an element of this network 190 */ 191 Set<E> incidentEdges(Object node); 192 193 /** 194 * Returns all edges in this network which can be traversed in the direction (if any) of the edge 195 * to end at {@code node}. 196 * 197 * <p>In a directed network, an incoming edge's {@link EndpointPair#target()} equals {@code node}. 198 * 199 * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}. 200 * 201 * @throws IllegalArgumentException if {@code node} is not an element of this network 202 */ 203 Set<E> inEdges(Object node); 204 205 /** 206 * Returns all edges in this network which can be traversed in the direction (if any) of the edge 207 * starting from {@code node}. 208 * 209 * <p>In a directed network, an outgoing edge's {@link EndpointPair#source()} equals {@code node}. 210 * 211 * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}. 212 * 213 * @throws IllegalArgumentException if {@code node} is not an element of this network 214 */ 215 Set<E> outEdges(Object node); 216 217 /** 218 * Returns the count of {@code node}'s {@link #incidentEdges(Object) incident edges}, counting 219 * self-loops twice (equivalently, the number of times an edge touches {@code node}). 220 * 221 * <p>For directed networks, this is equal to {@code inDegree(node) + outDegree(node)}. 222 * 223 * <p>For undirected networks, this is equal to {@code incidentEdges(node).size()} + (number of 224 * self-loops incident to {@code node}). 225 * 226 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 227 * 228 * @throws IllegalArgumentException if {@code node} is not an element of this network 229 */ 230 int degree(Object node); 231 232 /** 233 * Returns the count of {@code node}'s {@link #inEdges(Object) incoming edges} in a directed 234 * network. In an undirected network, returns the {@link #degree(Object)}. 235 * 236 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 237 * 238 * @throws IllegalArgumentException if {@code node} is not an element of this network 239 */ 240 int inDegree(Object node); 241 242 /** 243 * Returns the count of {@code node}'s {@link #outEdges(Object) outgoing edges} in a directed 244 * network. In an undirected network, returns the {@link #degree(Object)}. 245 * 246 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 247 * 248 * @throws IllegalArgumentException if {@code node} is not an element of this network 249 */ 250 int outDegree(Object node); 251 252 /** 253 * Returns the nodes which are the endpoints of {@code edge} in this network. 254 * 255 * @throws IllegalArgumentException if {@code edge} is not an element of this network 256 */ 257 EndpointPair<N> incidentNodes(Object edge); 258 259 /** 260 * Returns the edges which have an {@link #incidentNodes(Object) incident node} in common with 261 * {@code edge}. An edge is not considered adjacent to itself. 262 * 263 * @throws IllegalArgumentException if {@code edge} is not an element of this network 264 */ 265 Set<E> adjacentEdges(Object edge); 266 267 /** 268 * Returns the set of edges directly connecting {@code nodeU} to {@code nodeV}. 269 * 270 * <p>In an undirected network, this is equal to {@code edgesConnecting(nodeV, nodeU)}. 271 * 272 * <p>The resulting set of edges will be parallel (i.e. have equal {@link #incidentNodes(Object)}. 273 * If this network does not {@link #allowsParallelEdges() allow parallel edges}, the resulting set 274 * will contain at most one edge. 275 * 276 * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this 277 * network 278 */ 279 Set<E> edgesConnecting(Object nodeU, Object nodeV); 280 281 // 282 // Network identity 283 // 284 285 /** 286 * For the default {@link Network} implementations, returns true iff {@code this == object} 287 * (reference equality). External implementations are free to define this method as they see fit, 288 * as long as they satisfy the {@link Object#equals(Object)} contract. 289 * 290 * <p>To compare two {@link Network}s based on their contents rather than their references, see 291 * {@link Graphs#equivalent(Network, Network)}. 292 */ 293 @Override 294 boolean equals(@Nullable Object object); 295 296 /** 297 * For the default {@link Network} implementations, returns {@code System.identityHashCode(this)}. 298 * External implementations are free to define this method as they see fit, as long as they 299 * satisfy the {@link Object#hashCode()} contract. 300 */ 301 @Override 302 int hashCode(); 303}