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
|
// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.yolean.chain;
import java.util.ArrayList;
import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* TODO: prioritize vertices in edge map.
*
* @author tonytv
*/
class DirectedGraph {
private IdentityHashMap<Vertex, List<Vertex>> incommingEdges = new IdentityHashMap<>();
private List<Vertex> vertices = new ArrayList<>();
private List<Vertex> beginningVertices = new ArrayList<>();
private List<Vertex> endingVertices = new ArrayList<>();
public void addVertex(Vertex vertex) {
vertices.add(vertex);
}
public void addBeginningVertex(Vertex vertex) {
beginningVertices.add(vertex);
}
public void addEndingVertex(Vertex vertex) {
endingVertices.add(vertex);
}
public void addEdge(Vertex start, Vertex end) {
get(incommingEdges, end).add(start);
}
private static List<Vertex> get(Map<Vertex, List<Vertex>> edgeMap, Vertex key) {
List<Vertex> value = edgeMap.get(key);
return value == null ?
addEmptyList(edgeMap, key) :
value;
}
private static List<Vertex> addEmptyList(Map<Vertex, List<Vertex>> edgeMap, Vertex key) {
List<Vertex> value = new ArrayList<>();
edgeMap.put(key, value);
return value;
}
public List<Vertex> topologicalSort() {
EnumeratedIdentitySet<Vertex> visitedVertices = new EnumeratedIdentitySet<>();
for (Vertex v : beginningVertices) {
topologicalSortVisit(v, visitedVertices);
}
warnIfVisitedEndVertices(visitedVertices);
for (Vertex v : vertices) {
topologicalSortVisit(v, visitedVertices);
}
// TODO: review this!
for (Vertex v : endingVertices) {
topologicalSortVisit(v, visitedVertices);
}
return visitedVertices.insertionOrderedList();
}
private void warnIfVisitedEndVertices(EnumeratedIdentitySet<Vertex> visitedVertices) {
//TVT:
}
private void topologicalSortVisit(Vertex vertex, Set<Vertex> visitedVertices) {
topologicalSortVisitImpl(vertex, visitedVertices, new EnumeratedIdentitySet<Vertex>());
}
private void topologicalSortVisitImpl(Vertex vertex, Set<Vertex> visitedVertices,
EnumeratedIdentitySet<Vertex> cycleDetector) {
if (cycleDetector.contains(vertex)) {
throw new ChainCycleException(cycleDetector.insertionOrderedList());
}
if (visitedVertices.contains(vertex)) {
return;
}
cycleDetector.add(vertex);
for (Vertex endVertex : emptyIfNull(incommingEdges.get(vertex))) {
topologicalSortVisitImpl(endVertex, visitedVertices, cycleDetector);
}
visitedVertices.add(vertex);
cycleDetector.remove(vertex);
}
private <T> List<T> emptyIfNull(List<T> list) {
return list == null ?
Collections.<T>emptyList() :
list;
}
}
|
