-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
GraphDiameter.java
156 lines (124 loc) · 4.45 KB
/
GraphDiameter.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**
* Given a graph as a adjacency list this file shows you how to find the diameter/radius of the
* graph.
*
* <p>Time Complexity: O(V(V + E)) = O(V^2 + VE))= O(VE)
*
* <p>NOTE: This file could use some tests.
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.graphtheory;
import java.util.*;
public class GraphDiameter {
static class Edge {
int from, to;
public Edge(int from, int to) {
this.from = from;
this.to = to;
}
}
// Separate each breadth first search layer with a DEPTH_TOKEN
// to easily determine the distance to other nodes
static final int DEPTH_TOKEN = -1;
static Integer VISITED_TOKEN = 0;
static Map<Integer, Integer> visited = new HashMap<>();
static ArrayDeque<Integer> queue = new ArrayDeque<>();
// Compute the eccentricity from a given node. The eccentricity
// is the distance to the furthest node(s).
private static int eccentricity(int nodeID, Map<Integer, List<Edge>> graph) {
VISITED_TOKEN++;
queue.offer(nodeID);
queue.offer(DEPTH_TOKEN);
visited.put(nodeID, VISITED_TOKEN);
int depth = 0;
// Do BFS to count the
while (true) {
Integer id = queue.poll();
// If we encounter a depth token this means that we
// have finished the current frontier and are about
// to start the new layer (some of which may already
// be in the queue) or have reached the end.
if (id == DEPTH_TOKEN) {
// No more nodes to process
if (queue.isEmpty()) break;
// Add another DEPTH_TOKEN
queue.offer(DEPTH_TOKEN);
// Increase the max depth for each DEPTH_TOKEN seen
depth++;
} else {
List<Edge> edges = graph.get(id);
if (edges != null) {
for (Edge edge : edges) {
if (visited.get(edge.to) != VISITED_TOKEN) {
visited.put(edge.to, VISITED_TOKEN);
queue.offer(edge.to);
}
}
}
}
}
return depth;
}
// Compute the diameter of an arbitrary graph
// NOTE: The input graph should be undirected
public static int graphDiameter(Map<Integer, List<Edge>> graph) {
if (graph == null) return 0;
int diameter = 0;
int radius = Integer.MAX_VALUE;
// The diameter of a graph is the maximum of all the eccentricity values from all nodes.
// The radius on the other hand is the minimum of all the eccentricity values from all nodes.
for (Integer nodeID : graph.keySet()) {
int eccentricity = eccentricity(nodeID, graph);
diameter = Math.max(diameter, eccentricity);
radius = Math.min(radius, eccentricity);
}
// return radius;
return diameter;
}
// Example usage of how to compute the diameter of a graph
public static void main(String[] args) {
Map<Integer, List<Edge>> graph = createGraph(5);
addUndirectedEdge(graph, 4, 2);
addUndirectedEdge(graph, 2, 0);
addUndirectedEdge(graph, 0, 1);
addUndirectedEdge(graph, 1, 2);
addUndirectedEdge(graph, 1, 3);
int diameter = graphDiameter(graph);
if (diameter != 3) System.out.println("Wrong diameter!");
// No edges
graph = createGraph(5);
diameter = graphDiameter(graph);
if (diameter != 0) System.out.println("Wrong diameter!");
graph = createGraph(8);
addUndirectedEdge(graph, 0, 5);
addUndirectedEdge(graph, 1, 5);
addUndirectedEdge(graph, 2, 5);
addUndirectedEdge(graph, 3, 5);
addUndirectedEdge(graph, 4, 5);
addUndirectedEdge(graph, 6, 5);
addUndirectedEdge(graph, 7, 5);
diameter = graphDiameter(graph);
if (diameter != 2) System.out.println("Wrong diameter!");
graph = createGraph(9);
addUndirectedEdge(graph, 0, 5);
addUndirectedEdge(graph, 1, 5);
addUndirectedEdge(graph, 2, 5);
addUndirectedEdge(graph, 3, 5);
addUndirectedEdge(graph, 4, 5);
addUndirectedEdge(graph, 6, 5);
addUndirectedEdge(graph, 7, 5);
addUndirectedEdge(graph, 3, 8);
diameter = graphDiameter(graph);
if (diameter != 3) System.out.println("Wrong diameter!");
}
private static Map<Integer, List<Edge>> createGraph(int numNodes) {
Map<Integer, List<Edge>> graph = new HashMap<>();
for (int i = 0; i < numNodes; i++) graph.put(i, new ArrayList<Edge>());
return graph;
}
private static void addUndirectedEdge(Map<Integer, List<Edge>> graph, int from, int to) {
graph.get(from).add(new Edge(from, to));
graph.get(to).add(new Edge(to, from));
}
}