-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGetPath.java
More file actions
executable file
·155 lines (145 loc) · 5.68 KB
/
Copy pathGetPath.java
File metadata and controls
executable file
·155 lines (145 loc) · 5.68 KB
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
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
public class GetPath {
private static int threshold;
private static String curNode;
private static GroumNode groumNode;
private static Groum targetGraph;
private static List<List<String>> forPathList;
private static List<List<String>> backPathList;
private static List<List<String>> fuzzyPathList;
private static List<List<String>> forAndbackPathList;
private static List<List<String>> pathResult;
private static void getForPath(List<String> successors) {
if (successors.size() + 1 > threshold)
return;
curNode = successors.get(successors.size() - 1);
groumNode = targetGraph.getNodeMap().get(curNode);
for (GroumNode predecessor : groumNode.getParents()) {
List<String> successorsFor = new ArrayList<>();
Collections.addAll(successorsFor, new String[successors.size()]);
Collections.copy(successorsFor, successors);
successorsFor.add(predecessor.getId());
List<String> successorsCopy = new ArrayList<>();
Collections.addAll(successorsCopy, new String[successorsFor.size()]);
Collections.copy(successorsCopy, successorsFor);
Collections.reverse(successorsFor);
forPathList.add(successorsFor);
getForPath(successorsCopy);
}
}
private static void getBackPath(List<String> predecessors) {
if (predecessors.size() + 1 > threshold)
return;
curNode = predecessors.get(predecessors.size() - 1);
groumNode = targetGraph.getNodeMap().get(curNode);
for (GroumNode successor : groumNode.getChildren()) {
List<String> predecessorsFor = new ArrayList<>();
Collections.addAll(predecessorsFor, new String[predecessors.size()]);
Collections.copy(predecessorsFor, predecessors);
predecessorsFor.add(successor.getId());
backPathList.add(predecessorsFor);
getBackPath(predecessorsFor);
}
}
/**
* 产生指定范围的左闭右开区间List
* @param starter 起始
* @param ender 终止
* @return 区间List
*/
private static List<Integer> getRangeNums(int starter, int ender) {
List<Integer> result = new ArrayList<Integer>();
for (int i = starter; i < ender; ++i) {
result.add(i);
}
return result;
}
/**
* 构建一条fuzzy path
* @param target 需要修改的path
* @param start fuzzy的起始index
* @param end fuzzy的终止index + 1
*/
private static void makeOneFuzzyPath(List<String> target, int start, int end) {
for (int i = start; i < end; ++i) {
target.set(i, "*");
}
}
private static void getFuzzyPath(){
forAndbackPathList = new ArrayList<List<String>>();
forAndbackPathList.addAll(forPathList);
forAndbackPathList.addAll(backPathList);
for (List<String> path : forAndbackPathList) {
for (int starLen : getRangeNums(1, path.size() - 1)) {
List<String> pathCopyFor = new ArrayList<>();
Collections.addAll(pathCopyFor, new String[path.size()]);
Collections.copy(pathCopyFor, path);
makeOneFuzzyPath(pathCopyFor, 1, starLen + 1);
fuzzyPathList.add(pathCopyFor);
List<String> pathCopyBack = new ArrayList<>();
Collections.addAll(pathCopyBack, new String[path.size()]);
Collections.copy(pathCopyBack, path);
makeOneFuzzyPath(pathCopyBack, path.size() - 1 - starLen, path.size() - 1);
fuzzyPathList.add(pathCopyBack);
}
}
}
/**
* List 去重
* @param target
*/
private static void removeDuplicate(List<List<String>> target) {
LinkedHashSet<List<String>> set = new LinkedHashSet<List<String>>(target.size());
set.addAll(target);
target.clear();
target.addAll(set);
}
/**
* 将图上的id转为Map中的id
* @param pathResult
* @param source
*/
public static void convert(List<List<String>> pathResult, List<List<String>> source) {
Map<String, GroumNode> nodeMap = targetGraph.getNodeMap();
for (List<String> sourcePath : source) {
List<String> apiPath = new ArrayList<String>();
boolean canAdd = true;
for (String id : sourcePath) {
if (id.equals("*")) {
apiPath.add("*");
}
else {
String temp = nodeMap.get(id).getApi();
if (!temp.equals("-1")) apiPath.add(temp);
else {
canAdd = false;
break;
}
}
}
if (canAdd) pathResult.add(apiPath);
}
}
public static List<List<String>> getAllPath(Groum groum, List<String> startList, int d) {
threshold = d;
targetGraph = groum;
// get forward paths
forPathList = new ArrayList<List<String>>();
getForPath(startList);
// get backward paths
backPathList = new ArrayList<List<String>>();
getBackPath(startList);
// get fuzzy paths
fuzzyPathList = new ArrayList<List<String>>();
getFuzzyPath();
removeDuplicate(fuzzyPathList);
// 构建要返回的path list
pathResult = new ArrayList<List<String>>();
convert(pathResult, forPathList);
convert(pathResult, backPathList);
convert(pathResult, fuzzyPathList);
return pathResult;
}
}