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
|
package com.yahoo.graph;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
/**
* Provides graph traversal algorithms in an ad-hoc manner.
*
* @author jvenstad / jonmv
*/
public class Traversals {
private Traversals() { }
/**
* Returns an {@link Iterable} over the given nodes with a topological iteration order, per the given child mapper.
*
* @param nodes An iterable containing all nodes in the graph.
* @param children A function mapping a node to its children.
* @param <T> The node type.
* @return A topologically ordered iterable over the given nodes.
*/
public static <T> Iterable<T> topologically(Iterable<T> nodes, Function<T, Iterable<T>> children) {
return () -> new Iterator<T>() {
Iterator<T> delegate = topological(nodes, children);
@Override
public boolean hasNext() {
return delegate.hasNext();
}
@Override
public T next() {
T next = delegate.next();
delegate.remove();
return next;
}
};
}
/**
* Returns an {@link Iterable} over the given nodes with a topological iteration order, per the given child mapper.
*
* The {@link Iterator#remove()} method must be called for each returned element in order to proceed to its children.
*
* @param nodes An iterable containing all nodes in the graph.
* @param children A function mapping a node to its children.
* @param <T> The node type.
* @return A topologically ordered iterable over the given nodes.
*/
public static <T> Iterator<T> topological(Iterable<T> nodes, Function<T, Iterable<T>> children) {
Map<T, Long> indegrees = new HashMap<>();
for (T node : nodes)
for (T child : children.apply(node))
indegrees.merge(child, 1L, Long::sum);
Deque<T> ready = new ArrayDeque<>();
for (T node : nodes)
if ( ! indegrees.containsKey(node))
ready.add(node);
return new Iterator<T>() {
T last = null;
@Override
public boolean hasNext() {
return ! ready.isEmpty();
}
@Override
public T next() {
return last = ready.remove();
}
@Override
public void remove() {
if (last == null)
throw new IllegalStateException();
for (T child : children.apply(last))
indegrees.compute(child, (__, count) -> {
if (--count == 0)
ready.add(child);
return count;
});
}
};
}
/**
* Returns an edge set which is the reverse of the given one, restricted to the given node set.
*
* @param nodes The node set of the input and output graphs.
* @param edges The directed edge set for which to find a reverse.
* @param <T> The node type.
* @return The given edge set, but with all edges reversed.
*/
public static <T> Function<T, Iterable<T>> reversed(Iterable<T> nodes, Function<T, Iterable<T>> edges) {
Map<T, List<T>> reverse = new HashMap<>();
for (T node : nodes)
reverse.put(node, new ArrayList<>());
for (T node : nodes)
for (T neighbour : edges.apply(node))
if (reverse.containsKey(neighbour))
reverse.get(neighbour).add(node);
return reverse::get;
}
}
|
