0
# Graph API
1
2
Powerful graph data structures and algorithms for modeling complex relationships, networks, and hierarchical data. Guava provides flexible graph implementations supporting directed/undirected graphs, with or without edge values.
3
4
## Package: com.google.common.graph
5
6
### Basic Graph
7
8
Simple graph with nodes and edges, where edges are implicit connections between nodes.
9
10
```java { .api }
11
import com.google.common.graph.Graph;
12
import com.google.common.graph.GraphBuilder;
13
import com.google.common.graph.MutableGraph;
14
15
// Create undirected graph
16
MutableGraph<String> undirectedGraph = GraphBuilder.undirected().build();
17
18
// Add nodes
19
undirectedGraph.addNode("A");
20
undirectedGraph.addNode("B");
21
undirectedGraph.addNode("C");
22
23
// Add edges (automatically adds nodes if they don't exist)
24
undirectedGraph.putEdge("A", "B");
25
undirectedGraph.putEdge("B", "C");
26
undirectedGraph.putEdge("A", "C");
27
28
// Query graph structure
29
Set<String> nodes = undirectedGraph.nodes(); // {A, B, C}
30
Set<EndpointPair<String>> edges = undirectedGraph.edges(); // {{A,B}, {B,C}, {A,C}}
31
boolean hasEdge = undirectedGraph.hasEdgeConnecting("A", "B"); // true
32
33
// Node relationships
34
Set<String> neighbors = undirectedGraph.adjacentNodes("A"); // {B, C}
35
Set<String> predecessors = undirectedGraph.predecessors("B"); // {A, C} (same as successors in undirected)
36
Set<String> successors = undirectedGraph.successors("B"); // {A, C}
37
38
// Degree information
39
int degree = undirectedGraph.degree("B"); // 2
40
int inDegree = undirectedGraph.inDegree("B"); // 2 (same as degree in undirected)
41
int outDegree = undirectedGraph.outDegree("B"); // 2 (same as degree in undirected)
42
43
// Create directed graph
44
MutableGraph<String> directedGraph = GraphBuilder.directed().build();
45
directedGraph.putEdge("A", "B"); // A -> B
46
directedGraph.putEdge("B", "C"); // B -> C
47
directedGraph.putEdge("C", "A"); // C -> A (creates cycle)
48
49
// Directed graph queries
50
Set<String> aSuccessors = directedGraph.successors("A"); // {B}
51
Set<String> aPredecessors = directedGraph.predecessors("A"); // {C}
52
int aOutDegree = directedGraph.outDegree("A"); // 1
53
int aInDegree = directedGraph.inDegree("A"); // 1
54
```
55
56
### Graph Configuration
57
58
Comprehensive configuration options for graph behavior and constraints.
59
60
```java { .api }
61
// Self-loops configuration
62
MutableGraph<String> withSelfLoops = GraphBuilder.undirected()
63
.allowsSelfLoops(true)
64
.build();
65
withSelfLoops.putEdge("A", "A"); // Self-loop allowed
66
67
MutableGraph<String> noSelfLoops = GraphBuilder.undirected()
68
.allowsSelfLoops(false) // Default
69
.build();
70
// withSelfLoops.putEdge("A", "A"); // Would throw IllegalArgumentException
71
72
// Node ordering
73
MutableGraph<String> ordered = GraphBuilder.directed()
74
.nodeOrder(ElementOrder.<String>natural()) // Natural ordering for nodes
75
.build();
76
77
MutableGraph<Integer> insertionOrder = GraphBuilder.undirected()
78
.nodeOrder(ElementOrder.<Integer>insertion()) // Insertion order
79
.build();
80
81
// Expected node count (for performance optimization)
82
MutableGraph<String> withCapacity = GraphBuilder.undirected()
83
.expectedNodeCount(1000) // Optimize for ~1000 nodes
84
.build();
85
86
// Incidence order (order of edges for each node)
87
MutableGraph<String> stableIncidence = GraphBuilder.directed()
88
.incidenceOrder(ElementOrder.<String>stable()) // Stable order
89
.build();
90
91
// Complete configuration example
92
MutableGraph<Integer> configuredGraph = GraphBuilder.directed()
93
.allowsSelfLoops(true)
94
.nodeOrder(ElementOrder.<Integer>natural())
95
.incidenceOrder(ElementOrder.<Integer>stable())
96
.expectedNodeCount(100)
97
.build();
98
```
99
100
### ValueGraph
101
102
Graph where edges have associated values, useful for weighted graphs or storing edge metadata.
103
104
```java { .api }
105
import com.google.common.graph.ValueGraph;
106
import com.google.common.graph.MutableValueGraph;
107
import com.google.common.graph.ValueGraphBuilder;
108
109
// Create weighted graph (edges have numeric weights)
110
MutableValueGraph<String, Double> weightedGraph = ValueGraphBuilder.directed().<String, Double>build();
111
112
// Add edges with values (weights)
113
weightedGraph.putEdgeValue("A", "B", 5.0);
114
weightedGraph.putEdgeValue("B", "C", 3.2);
115
weightedGraph.putEdgeValue("A", "C", 7.8);
116
weightedGraph.putEdgeValue("C", "D", 2.1);
117
118
// Query edge values
119
Optional<Double> weight = weightedGraph.edgeValue("A", "B"); // Optional[5.0]
120
Double weightOrDefault = weightedGraph.edgeValueOrDefault("A", "B", 0.0); // 5.0
121
Double missingWeight = weightedGraph.edgeValueOrDefault("A", "D", 0.0); // 0.0
122
123
// Graph with string metadata on edges
124
MutableValueGraph<String, String> metadataGraph = ValueGraphBuilder.undirected()
125
.<String, String>build();
126
127
metadataGraph.putEdgeValue("Server1", "Server2", "ethernet-100mbps");
128
metadataGraph.putEdgeValue("Server2", "Server3", "fiber-1gbps");
129
metadataGraph.putEdgeValue("Server1", "Server3", "wifi-54mbps");
130
131
String connectionType = metadataGraph.edgeValueOrDefault("Server1", "Server2", "unknown");
132
133
// Remove edges
134
Double removedWeight = weightedGraph.removeEdge("A", "C"); // Returns 7.8 and removes edge
135
136
// Iterate over edges with values
137
for (EndpointPair<String> edge : weightedGraph.edges()) {
138
String nodeU = edge.nodeU();
139
String nodeV = edge.nodeV();
140
Double value = weightedGraph.edgeValueOrDefault(nodeU, nodeV, 0.0);
141
System.out.println(nodeU + " -> " + nodeV + " (weight: " + value + ")");
142
}
143
```
144
145
### Network
146
147
Graph where edges are first-class objects with their own identity, allowing multiple edges between the same pair of nodes.
148
149
```java { .api }
150
import com.google.common.graph.Network;
151
import com.google.common.graph.MutableNetwork;
152
import com.google.common.graph.NetworkBuilder;
153
154
// Create network with edge objects
155
MutableNetwork<String, String> network = NetworkBuilder.directed().<String, String>build();
156
157
// Add nodes
158
network.addNode("A");
159
network.addNode("B");
160
network.addNode("C");
161
162
// Add edges with explicit edge objects (allows multiple edges between same nodes)
163
network.addEdge("A", "B", "edge1");
164
network.addEdge("A", "B", "edge2"); // Second edge between A and B
165
network.addEdge("B", "C", "edge3");
166
167
// Query network structure
168
Set<String> nodes = network.nodes(); // {A, B, C}
169
Set<String> edges = network.edges(); // {edge1, edge2, edge3}
170
171
// Edge relationships
172
Set<String> edgesFromA = network.outEdges("A"); // {edge1, edge2}
173
Set<String> edgesToB = network.inEdges("B"); // {edge1, edge2}
174
Set<String> incidentToB = network.incidentEdges("B"); // {edge1, edge2, edge3}
175
176
// Edge endpoints
177
EndpointPair<String> endpoints = network.incidentNodes("edge1"); // {A, B}
178
String source = network.incidentNodes("edge1").source(); // A (in directed network)
179
String target = network.incidentNodes("edge1").target(); // B (in directed network)
180
181
// Adjacent edges
182
Set<String> adjacentEdges = network.adjacentEdges("edge1"); // Edges sharing a node with edge1
183
184
// Nodes connected by edges
185
Set<String> connectedByEdge = network.adjacentNodes("A"); // Nodes connected to A
186
Set<String> edgesBetween = network.edgesConnecting("A", "B"); // {edge1, edge2}
187
188
// Parallel edges (multiple edges between same nodes)
189
boolean hasParallelEdges = network.edgesConnecting("A", "B").size() > 1; // true
190
191
// Remove edges
192
boolean removed = network.removeEdge("edge2"); // true if edge existed
193
```
194
195
### Graph Utilities
196
197
Static utility methods for common graph operations and transformations.
198
199
```java { .api }
200
import com.google.common.graph.Graphs;
201
202
// Copy graphs
203
MutableGraph<String> original = GraphBuilder.undirected().build();
204
original.putEdge("A", "B");
205
original.putEdge("B", "C");
206
207
Graph<String> copy = ImmutableGraph.copyOf(original);
208
MutableGraph<String> mutableCopy = Graphs.copyOf(original);
209
210
// Transpose (reverse all edges in directed graph)
211
MutableGraph<String> directed = GraphBuilder.directed().build();
212
directed.putEdge("A", "B");
213
directed.putEdge("B", "C");
214
215
Graph<String> transposed = Graphs.transpose(directed);
216
// Original: A -> B -> C
217
// Transposed: A <- B <- C
218
219
// Reachability
220
Set<String> reachableFromA = Graphs.reachableNodes(directed, "A"); // All nodes reachable from A
221
boolean hasPath = Graphs.hasPathConnecting(directed, "A", "C"); // true
222
223
// Induced subgraph (subgraph containing only specified nodes)
224
Set<String> nodeSubset = ImmutableSet.of("A", "B");
225
MutableGraph<String> subgraph = Graphs.inducedSubgraph(original, nodeSubset);
226
227
// Graph properties
228
boolean isTree = Graphs.hasCycle(original); // Check for cycles (false means it's a tree if connected)
229
```
230
231
### Graph Algorithms
232
233
Implementation of common graph algorithms using Guava graphs.
234
235
```java { .api }
236
// Breadth-First Search (BFS)
237
public static <N> List<N> bfs(Graph<N> graph, N startNode) {
238
List<N> visited = new ArrayList<>();
239
Set<N> seen = new HashSet<>();
240
Queue<N> queue = new ArrayDeque<>();
241
242
queue.offer(startNode);
243
seen.add(startNode);
244
245
while (!queue.isEmpty()) {
246
N current = queue.poll();
247
visited.add(current);
248
249
for (N neighbor : graph.adjacentNodes(current)) {
250
if (!seen.contains(neighbor)) {
251
seen.add(neighbor);
252
queue.offer(neighbor);
253
}
254
}
255
}
256
257
return visited;
258
}
259
260
// Depth-First Search (DFS)
261
public static <N> List<N> dfs(Graph<N> graph, N startNode) {
262
List<N> visited = new ArrayList<>();
263
Set<N> seen = new HashSet<>();
264
dfsRecursive(graph, startNode, visited, seen);
265
return visited;
266
}
267
268
private static <N> void dfsRecursive(Graph<N> graph, N node, List<N> visited, Set<N> seen) {
269
if (seen.contains(node)) {
270
return;
271
}
272
273
seen.add(node);
274
visited.add(node);
275
276
for (N neighbor : graph.adjacentNodes(node)) {
277
dfsRecursive(graph, neighbor, visited, seen);
278
}
279
}
280
281
// Dijkstra's shortest path (for ValueGraph with numeric edge weights)
282
public static <N> Map<N, Double> dijkstra(ValueGraph<N, Double> graph, N startNode) {
283
Map<N, Double> distances = new HashMap<>();
284
PriorityQueue<N> queue = new PriorityQueue<>(
285
Comparator.comparing(node -> distances.getOrDefault(node, Double.MAX_VALUE)));
286
287
distances.put(startNode, 0.0);
288
queue.offer(startNode);
289
290
while (!queue.isEmpty()) {
291
N current = queue.poll();
292
double currentDistance = distances.get(current);
293
294
for (N neighbor : graph.adjacentNodes(current)) {
295
double edgeWeight = graph.edgeValueOrDefault(current, neighbor, Double.MAX_VALUE);
296
double newDistance = currentDistance + edgeWeight;
297
298
if (newDistance < distances.getOrDefault(neighbor, Double.MAX_VALUE)) {
299
distances.put(neighbor, newDistance);
300
queue.offer(neighbor);
301
}
302
}
303
}
304
305
return distances;
306
}
307
308
// Topological sort (for directed acyclic graphs)
309
public static <N> List<N> topologicalSort(Graph<N> graph) {
310
if (!graph.isDirected()) {
311
throw new IllegalArgumentException("Topological sort requires directed graph");
312
}
313
314
List<N> result = new ArrayList<>();
315
Set<N> visited = new HashSet<>();
316
Set<N> visiting = new HashSet<>();
317
318
for (N node : graph.nodes()) {
319
if (!visited.contains(node)) {
320
topologicalSortVisit(graph, node, visited, visiting, result);
321
}
322
}
323
324
Collections.reverse(result);
325
return result;
326
}
327
328
private static <N> void topologicalSortVisit(Graph<N> graph, N node,
329
Set<N> visited, Set<N> visiting, List<N> result) {
330
if (visiting.contains(node)) {
331
throw new IllegalArgumentException("Graph contains cycle");
332
}
333
if (visited.contains(node)) {
334
return;
335
}
336
337
visiting.add(node);
338
for (N successor : graph.successors(node)) {
339
topologicalSortVisit(graph, successor, visited, visiting, result);
340
}
341
visiting.remove(node);
342
visited.add(node);
343
result.add(node);
344
}
345
```
346
347
### Practical Applications
348
349
Real-world examples of using Guava graphs for common modeling scenarios.
350
351
```java { .api }
352
// Social network modeling
353
public class SocialNetwork {
354
private final MutableGraph<Person> friendshipGraph;
355
356
public SocialNetwork() {
357
this.friendshipGraph = GraphBuilder.undirected()
358
.allowsSelfLoops(false)
359
.expectedNodeCount(10000)
360
.build();
361
}
362
363
public void addPerson(Person person) {
364
friendshipGraph.addNode(person);
365
}
366
367
public void addFriendship(Person person1, Person person2) {
368
friendshipGraph.putEdge(person1, person2);
369
}
370
371
public Set<Person> getFriends(Person person) {
372
return friendshipGraph.adjacentNodes(person);
373
}
374
375
public Set<Person> getMutualFriends(Person person1, Person person2) {
376
Set<Person> friends1 = friendshipGraph.adjacentNodes(person1);
377
Set<Person> friends2 = friendshipGraph.adjacentNodes(person2);
378
return Sets.intersection(friends1, friends2);
379
}
380
381
public List<Person> findShortestPath(Person from, Person to) {
382
// BFS to find shortest path
383
Map<Person, Person> parent = new HashMap<>();
384
Queue<Person> queue = new ArrayDeque<>();
385
Set<Person> visited = new HashSet<>();
386
387
queue.offer(from);
388
visited.add(from);
389
parent.put(from, null);
390
391
while (!queue.isEmpty()) {
392
Person current = queue.poll();
393
if (current.equals(to)) {
394
break; // Found target
395
}
396
397
for (Person friend : friendshipGraph.adjacentNodes(current)) {
398
if (!visited.contains(friend)) {
399
visited.add(friend);
400
parent.put(friend, current);
401
queue.offer(friend);
402
}
403
}
404
}
405
406
// Reconstruct path
407
List<Person> path = new ArrayList<>();
408
Person current = to;
409
while (current != null) {
410
path.add(current);
411
current = parent.get(current);
412
}
413
Collections.reverse(path);
414
415
return path.get(0).equals(from) ? path : Collections.emptyList();
416
}
417
}
418
419
// Dependency graph for build system
420
public class DependencyManager {
421
private final MutableGraph<String> dependencyGraph;
422
423
public DependencyManager() {
424
this.dependencyGraph = GraphBuilder.directed()
425
.allowsSelfLoops(false)
426
.build();
427
}
428
429
public void addModule(String module) {
430
dependencyGraph.addNode(module);
431
}
432
433
public void addDependency(String module, String dependency) {
434
// module depends on dependency
435
dependencyGraph.putEdge(dependency, module);
436
}
437
438
public List<String> getBuildOrder() {
439
try {
440
return topologicalSort(dependencyGraph);
441
} catch (IllegalArgumentException e) {
442
throw new RuntimeException("Circular dependency detected", e);
443
}
444
}
445
446
public Set<String> getDirectDependencies(String module) {
447
return dependencyGraph.predecessors(module);
448
}
449
450
public Set<String> getAllDependencies(String module) {
451
return Graphs.reachableNodes(
452
Graphs.transpose(dependencyGraph), module);
453
}
454
455
public boolean hasCyclicDependencies() {
456
try {
457
topologicalSort(dependencyGraph);
458
return false;
459
} catch (IllegalArgumentException e) {
460
return true;
461
}
462
}
463
}
464
465
// Network routing with weighted edges
466
public class NetworkTopology {
467
private final MutableValueGraph<String, Integer> network;
468
469
public NetworkTopology() {
470
this.network = ValueGraphBuilder.undirected()
471
.<String, Integer>build();
472
}
473
474
public void addRouter(String routerId) {
475
network.addNode(routerId);
476
}
477
478
public void addLink(String router1, String router2, int latency) {
479
network.putEdgeValue(router1, router2, latency);
480
}
481
482
public Map<String, Integer> findShortestPaths(String sourceRouter) {
483
return dijkstra(network, sourceRouter);
484
}
485
486
public List<String> findShortestPath(String from, String to) {
487
Map<String, Integer> distances = dijkstra(network, from);
488
if (!distances.containsKey(to)) {
489
return Collections.emptyList(); // No path exists
490
}
491
492
// Reconstruct path (simplified - would need parent tracking in real dijkstra)
493
// This is a placeholder for demonstration
494
return Arrays.asList(from, to);
495
}
496
497
public Set<String> findAlternativeRoutes(String from, String to, String excludeRouter) {
498
// Create subgraph excluding the router
499
Set<String> nodesWithoutExcluded = new HashSet<>(network.nodes());
500
nodesWithoutExcluded.remove(excludeRouter);
501
502
ValueGraph<String, Integer> subgraph = Graphs.inducedSubgraph(network, nodesWithoutExcluded);
503
504
// Find reachable nodes from source in subgraph
505
return Graphs.reachableNodes(subgraph, from);
506
}
507
}
508
```
509
510
### Immutable Graphs
511
512
Creating immutable graph instances for thread safety and caching.
513
514
```java { .api }
515
import com.google.common.graph.ImmutableGraph;
516
import com.google.common.graph.ImmutableValueGraph;
517
import com.google.common.graph.ImmutableNetwork;
518
519
// Create immutable graph from mutable graph
520
MutableGraph<String> mutable = GraphBuilder.undirected().build();
521
mutable.putEdge("A", "B");
522
mutable.putEdge("B", "C");
523
524
ImmutableGraph<String> immutable = ImmutableGraph.copyOf(mutable);
525
526
// Build immutable graph directly
527
ImmutableGraph<Integer> numbers = ImmutableGraph.<Integer>builder()
528
.addNode(1)
529
.addNode(2)
530
.addNode(3)
531
.putEdge(1, 2)
532
.putEdge(2, 3)
533
.build();
534
535
// Immutable value graph
536
ImmutableValueGraph<String, Double> weights = ImmutableValueGraph.<String, Double>builder()
537
.putEdgeValue("A", "B", 1.5)
538
.putEdgeValue("B", "C", 2.3)
539
.build();
540
541
// Benefits: thread-safe, can be cached, shared safely between components
542
public class GraphCache {
543
private static final Map<String, ImmutableGraph<String>> cache = new ConcurrentHashMap<>();
544
545
public static ImmutableGraph<String> getOrBuildGraph(String graphId) {
546
return cache.computeIfAbsent(graphId, id -> {
547
MutableGraph<String> graph = buildGraphFromConfig(id);
548
return ImmutableGraph.copyOf(graph);
549
});
550
}
551
}
552
```
553
554
Guava's graph API provides a flexible, type-safe way to model complex relationships and networks with support for various graph types, comprehensive query operations, and integration with common graph algorithms.