RecRankJavaEmersion/src/GetPath.java at master · coderZMR/RecRankJavaEmersion · GitHub

History

executable file

155 lines (145 loc) · 5.68 KB

Raw

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;

}

RecRankJavaEmersion/src/GetPath.java at master · coderZMR/RecRankJavaEmersion · GitHub

Expand file tree

Breadcrumbs

GetPath.java

Latest commit

History

Breadcrumbs

GetPath.java

File metadata and controls