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 * <p>To choose the right interface, answer these questions: 039 * 040 * <ol> 041 * <li>Do you have data (objects) that you wish to associate with edges? 042 * <p>Yes: Go to question 2. No: Use {@link Graph}. 043 * <li>Are the objects you wish to associate with edges unique within the scope of a graph? That is, 044 * no two objects would be {@link Object#equals(Object) equal} to each other. A common example 045 * where this would <i>not</i> be the case is with weighted graphs. 046 * <p>Yes: Go to question 3. No: Use {@link ValueGraph}. 047 * <li>Do you need to be able to query the graph for an edge associated with a particular object? 048 * For example, do you need to query what nodes an edge associated with a particular object 049 * connects, or whether an edge associated with that object exists in the graph? 050 * <p>Yes: Use {@link Network}. No: Go to question 4. 051 * <li>Do you need explicit support for parallel edges? For example, do you need to remove one edge 052 * connecting a pair of nodes while leaving other edges connecting those same nodes intact? 053 * <p>Yes: Use {@link Network}. No: Use {@link ValueGraph}. 054 * </ol> 055 * 056 * <p>Although {@link MutableValueGraph} and {@link MutableNetwork} both require users to provide 057 * objects to associate with edges when adding them, the differentiating factor is that in {@link 058 * ValueGraph}s, these objects can be any arbitrary data. Like the values in a {@link Map}, they do 059 * not have to be unique, and can be mutated while in the graph. In a {@link Network}, these objects 060 * serve as keys into the data structure. Like the keys in a {@link Map}, they must be unique, and 061 * cannot be mutated in a way that affects their equals/hashcode or the data structure will become 062 * corrupted. 063 * 064 * <p>In all three interfaces, nodes have all the same requirements as keys in a {@link Map}. 065 * 066 * <p>The {@link Graph} interface does not support parallel {@link #edges()}, and forbids 067 * implementations or extensions with parallel edges. It is possible to encode a notion of edge 068 * multiplicity into the values of a {@link ValueGraph} (e.g. with an integer or a list of values), 069 * but this will not be reflected in methods such as {@link Graph#degree(Object)}. For that 070 * functionality, see {@link Network}. 071 * 072 * <p>All mutation methods live on the subinterface {@link MutableGraph}. If you do not need to 073 * mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph), you 074 * should prefer the non-mutating {@link Graph} interface. 075 * 076 * <p>We provide an efficient implementation of this interface via {@link GraphBuilder}. When using 077 * the implementation provided, all collection-returning methods provide live, unmodifiable views of 078 * the graph. In other words, you cannot add an element to the collection, but if an element is 079 * added to the {@link Graph} that would affect the collection, the collection will be updated 080 * automatically. This also means that you cannot mutate a {@link Graph} in a way that would affect 081 * a collection while iterating over that collection. For example, you cannot remove either {@code 082 * foo} or any successors of {@code foo} from the graph while iterating over {@code successors(foo)} 083 * (unless you first make a copy of the successors), just as you could not remove keys from a {@link 084 * Map} while iterating over its {@link Map#keySet()}. Behavior in such a case is undefined, and may 085 * result in {@link ConcurrentModificationException}. 086 * 087 * <p>Example of use: 088 * 089 * <pre><code> 090 * MutableGraph<String> managementGraph = GraphBuilder.directed().build(); 091 * managementGraph.putEdge("Big Boss", "Middle Manager Jack"); 092 * managementGraph.putEdge("Big Boss", "Middle Manager Jill"); 093 * managementGraph.putEdge("Middle Manager Jack", "Joe"); 094 * managementGraph.putEdge("Middle Manager Jack", "Schmoe"); 095 * managementGraph.putEdge("Middle Manager Jill", "Jane"); 096 * managementGraph.putEdge("Middle Manager Jill", "Doe"); 097 * for (String employee : managementGraph.nodes()) { 098 * Set<String> reports = managementGraph.successors(employee); 099 * if (!reports.isEmpty()) { 100 * System.out.format("%s has the following direct reports: %s%n", employee, reports); 101 * } 102 * } 103 * </code></pre> 104 * 105 * @author James Sexton 106 * @author Joshua O'Madadhain 107 * @param <N> Node parameter type 108 * @since 20.0 109 */ 110@Beta 111public interface Graph<N> { 112 // 113 // Graph-level accessors 114 // 115 116 /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */ 117 Set<N> nodes(); 118 119 /** Returns all edges in this graph. */ 120 Set<EndpointPair<N>> edges(); 121 122 // 123 // Graph properties 124 // 125 126 /** 127 * Returns true if the edges in this graph are directed. Directed edges connect a {@link 128 * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while 129 * undirected edges connect a pair of nodes to each other. 130 */ 131 boolean isDirected(); 132 133 /** 134 * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting 135 * to add a self-loop to a graph that does not allow them will throw an {@link 136 * UnsupportedOperationException}. 137 */ 138 boolean allowsSelfLoops(); 139 140 /** Returns the order of iteration for the elements of {@link #nodes()}. */ 141 ElementOrder<N> nodeOrder(); 142 143 // 144 // Element-level accessors 145 // 146 147 /** 148 * Returns the nodes which have an incident edge in common with {@code node} in this graph. 149 * 150 * @throws IllegalArgumentException if {@code node} is not an element of this graph 151 */ 152 Set<N> adjacentNodes(Object node); 153 154 /** 155 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 156 * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge. 157 * 158 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}. 159 * 160 * @throws IllegalArgumentException if {@code node} is not an element of this graph 161 */ 162 Set<N> predecessors(Object node); 163 164 /** 165 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 166 * {@code node}'s outgoing edges in the direction (if any) of the edge. 167 * 168 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}. 169 * 170 * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing 171 * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}. 172 * 173 * @throws IllegalArgumentException if {@code node} is not an element of this graph 174 */ 175 Set<N> successors(Object node); 176 177 /** 178 * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently, 179 * the number of times an edge touches {@code node}). 180 * 181 * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}. 182 * 183 * <p>For undirected graphs, this is equal to {@code adjacentNodes(node).size()} + (1 if {@code 184 * node} has an incident self-loop, 0 otherwise). 185 * 186 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 187 * 188 * @throws IllegalArgumentException if {@code node} is not an element of this graph 189 */ 190 int degree(Object node); 191 192 /** 193 * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()}) 194 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}. 195 * 196 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 197 * 198 * @throws IllegalArgumentException if {@code node} is not an element of this graph 199 */ 200 int inDegree(Object node); 201 202 /** 203 * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()}) 204 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}. 205 * 206 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 207 * 208 * @throws IllegalArgumentException if {@code node} is not an element of this graph 209 */ 210 int outDegree(Object node); 211 212 // 213 // Graph identity 214 // 215 216 /** 217 * For the default {@link Graph} implementations, returns true iff {@code this == object} 218 * (reference equality). External implementations are free to define this method as they see fit, 219 * as long as they satisfy the {@link Object#equals(Object)} contract. 220 * 221 * <p>To compare two {@link Graph}s based on their contents rather than their references, see 222 * {@link Graphs#equivalent(Graph, Graph)}. 223 */ 224 @Override 225 boolean equals(@Nullable Object object); 226 227 /** 228 * For the default {@link Graph} implementations, returns {@code System.identityHashCode(this)}. 229 * External implementations are free to define this method as they see fit, as long as they 230 * satisfy the {@link Object#hashCode()} contract. 231 */ 232 @Override 233 int hashCode(); 234}