这份代码的作用是找图中所有长度3-7的环并按照字典序输出到文件中。
package huawei;import java.io.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.stream.IntStream;@SuppressWarnings("unchecked")
final class DiGraph {private final int V;private int E;private LinkedList<Integer>[] adj;private int[] inDegree;private int[] outDegree;private List<Map<Integer,Set<Integer>>> p;// List<int[]> data
// List<Integer> inputs,Map<Integer,Integer> reverse_dictpublic DiGraph(int V, int E,List<Integer> inputs,Map<Integer,Integer> reverse_dict ){this.V = V;this.E = E;adj = (LinkedList<Integer>[])new LinkedList[V];inDegree = new int[V];outDegree = new int[V];p = new ArrayList<>(V);for(int i = 0;i < V;i++){adj[i] = new LinkedList<>();p.add(new HashMap<>());}// for(int i=0;i<data.size();i++){
// int v = data.get(i)[0];
// int w = data.get(i)[1];
// addEdge(v,w);
// }int s;for(s = 0;s < inputs.size();s+=2){int v = reverse_dict.get(inputs.get(s));int w = reverse_dict.get(inputs.get(s+1));addEdge(v,w);}for(int i = 0; i < this.V;i++){adj[i].sort((o1, o2) -> {if(o1 > o2){return 1;}else if(o1 < o2){return -1;}else {return 0;}});}construct();}public void construct(){
// IntStream.range(0,this.V()).parallel().forEach(i -> {
// for(int k:this.adj(i)){
// for(int j:this.adj(k)){
// if(i>j && k > j){
// Set<Integer> set = p.get(j).get(i);
// if(set != null){
// set.add(k);
// }
// else {
// set = new TreeSet<>();
// set.add(k);
// }
// p.get(j).put(i,set);
// }
// }
// }
// });for(int i=0;i < this.V();i++){for(int k:this.adj(i)){for(int j:this.adj(k)){if(i>j && k > j){Set<Integer> set = p.get(j).get(i);if(set != null){set.add(k);}else {set = new TreeSet<>();set.add(k);}p.get(j).put(i,set);}}}}}public List<Map<Integer,Set<Integer>>> getP(){return p;}public int indegree(int v){return inDegree[v];}public void subIndegree(int v){inDegree[v]--;}public int outdegree(int v){return outDegree[v];}public void removeAllEdge(int v){E -= adj[v].size();adj[v] = new LinkedList<>();}public void addEdge(int v,int w){inDegree[v] += 1 ;outDegree[w] += 1;adj[v].add(w);E++;}public final Iterable<Integer> adj(int v){return adj[v];}public int V(){return V;}public int E(){return E;}
}@SuppressWarnings("unchecked")
public final class Main {private List<Map<Integer,Set<Integer>>> pInv;public Main(){}public List<LinkedList<Integer>> train(DiGraph g, List<List<Integer>> data){List<LinkedList<Integer>> allCylce = new ArrayList<>();pInv = g.getP();ThreadPoolExecutor executor = new ThreadPoolExecutor(1000, 2000, 100L,TimeUnit.MILLISECONDS, new LinkedBlockingQueue<>(2048),new ThreadPoolExecutor.AbortPolicy());boolean[] marked ;boolean[] onStack ;LinkedList<Integer> path;for(int i = 0;i < data.size();i++){List<Integer> subList = data.get(i);List<Future<List<LinkedList<Integer>>>> futureList = new ArrayList<>();for(int j = 0,length=subList.size();j < length;j++){marked = new boolean[g.V()];onStack = new boolean[g.V()];path = new LinkedList<>();SubThread subThread = new SubThread(g, subList.get(j), subList.get(j), 1,marked,onStack,path);futureList.add(executor.submit(subThread));}futureList.stream().forEach(future -> {try {List<LinkedList<Integer>> list = future.get();allCylce.addAll(list);} catch (Exception e) {e.printStackTrace();}});}executor.shutdown();return allCylce;}final class SubThread implements Callable<List<LinkedList<Integer>>> {private DiGraph g;private int v;private int source;private int currentLength;private boolean[] marked;private boolean[] onStack;private LinkedList<Integer> path;public SubThread(DiGraph g, int v, int source, int currentLength,boolean[] marked,boolean[] onStack,LinkedList<Integer> path) {this.g = g;this.v = v;this.source = source;this.currentLength = currentLength;this.marked = marked;this.onStack = onStack;this.path = path;}@Overridepublic final List<LinkedList<Integer>> call(){List<LinkedList<Integer>> stackList = dfs(g,v, source, currentLength,marked,onStack,path);return stackList;}}final public List<LinkedList<Integer>> dfs(DiGraph g, int v, int source, int currentLength,boolean[] marked,boolean[] onStack,LinkedList<Integer> path) {List<LinkedList<Integer>> subList = new ArrayList<>();onStack[v] = true;marked[v] = true;path.add(v);for (Iterator<Integer> it = g.adj(v).iterator();it.hasNext();) {int w = it.next();if (!marked[w] && w > source) {if(currentLength < 6){List<LinkedList<Integer>> stackList = dfs(g,w, source, currentLength + 1,marked,onStack,path);subList.addAll(stackList);}} else if (onStack[w] && currentLength >= 3 && w == source) {LinkedList<Integer> temp = (LinkedList<Integer>) path.clone();subList.add(temp);}}if(currentLength == 6) {Set<Integer> ks = pInv.get(source).get(v);if(ks != null){for(int k:ks){if(marked[k]) continue;LinkedList<Integer> temp = (LinkedList<Integer>) path.clone();temp.add(k);subList.add(temp);}}}onStack[v] = false;marked[v] = false;if(!path.isEmpty()){path.remove(path.size()-1);}return subList;}public final Map<String, Object> getDiGraphData(String filename) throws IOException {Map<String, Object> map = load_data(filename);return map;}public final Map<String,Object> load_data(String filename) throws IOException {File file = new File(filename);file.setReadOnly();BufferedReader reader = new BufferedReader(new FileReader(file));String line;TreeSet<Integer> set = new TreeSet<>();List<int[]> array_list = new ArrayList<>();List<String> idsComma = new ArrayList<>();List<String> idsLF = new ArrayList<>();List<Integer> inputs = new ArrayList<>();while ((line = reader.readLine()) != null){int[] array = new int[2];String[] strings = line.split(",");int source = Integer.parseInt(strings[0]);int dest = Integer.parseInt(strings[1]);set.add(source);set.add(dest);inputs.add(source);inputs.add(dest);array[0] = source;array[1] = dest;array_list.add(array);}reader.close();// Collections.sort(array_list, (o1, o2) -> {
// if(o1[0] > o2[0]){
// return 1;
// }
// else if(o1[0] < o2[0]){
// return -1;
// }
// else {
// if(o1[1] > o2[1]){
// return 1;
// }
// else if(o1[1] < o2[1]){
// return -1;
// }
// else {
// return 0;
// }
// }
// });List<Integer> listSet = new ArrayList<>(set);Map<Integer,Integer> reverse_dict = new HashMap<>();TreeSet<Integer> sorted_data = new TreeSet<>();for(int i = 0,length=listSet.size();i < length;i++){Integer source = listSet.get(i);reverse_dict.put(source,i);idsComma.add(source.toString()+",");idsLF.add(source.toString()+"\n");sorted_data.add(i);}array_list.parallelStream().forEach(data -> {data[0] = reverse_dict.get(data[0]);data[1] = reverse_dict.get(data[1]);});int V = sorted_data.last();int E = array_list.size();Map<String,Object> result = new HashMap<>();result.put("V",V);result.put("E",E);result.put("data",array_list);result.put("sorted_data",sorted_data);result.put("reverse_dict",reverse_dict);result.put("comma",idsComma);result.put("lf",idsLF);result.put("inputs",inputs);return result;}public final void save_file(String path,List<LinkedList<Integer>> results,List<String> comma,List<String> lf) throws IOException {File file = new File(path);if(!file.exists()){file.createNewFile();}BufferedWriter bw = new BufferedWriter(new FileWriter(file));bw.write(results.size()+"\n");StringBuilder largeSb = new StringBuilder();StringBuilder sb;int count = 0;for(LinkedList<Integer> r : results){sb = new StringBuilder();for(int i=0;i < r.size()-1;i++){sb.append(comma.get(r.get(i)));}sb.append(lf.get(r.get(r.size()-1)));largeSb.append(sb.toString());if(count % 10000 == 0){bw.write(largeSb.toString());largeSb = new StringBuilder();}count += 1;}bw.write(largeSb.toString());bw.close();}public final List<List<Integer>> splitData(TreeSet<Integer> data){List<Integer> dataList = new ArrayList<>(data);List<List<Integer>> result = new ArrayList<>();List<Integer> subList = new ArrayList<>();for(int i = 0,length=dataList.size();i < length;i++){if((i+1) % 2000 == 0){subList.add(dataList.get(i));result.add(subList);subList = new ArrayList<>();}else {if(data.size() > 0){subList.add(dataList.get(i));}}}result.add(subList);return result;}public static void main(String[] args) throws IOException {long start = System.currentTimeMillis();String filename = "D:\\huaweichussai/test_data1.txt";Main diGraphCycle = new Main();Map<String, Object> map = diGraphCycle.getDiGraphData(filename);int E = (int) map.get("E");int V = (int) map.get("V")+1;List<int[]> data = (List<int[]>) map.get("data");TreeSet<Integer> sorted_data = (TreeSet<Integer>) map.get("sorted_data");List<String> comma = (List<String>) map.get("comma");List<String> lf = (List<String>) map.get("lf");List<Integer> inputs = (List<Integer>) map.get("inputs");Map<Integer,Integer> reverse_dict = (Map<Integer, Integer>) map.get("reverse_dict");System.out.println("load:"+(System.currentTimeMillis()-start));DiGraph diGraph = new DiGraph(V, E, inputs,reverse_dict);System.out.println("create graph:"+(System.currentTimeMillis()-start));long start2 = System.currentTimeMillis();List<List<Integer>> splitData = diGraphCycle.splitData(sorted_data);System.out.println("split:"+(System.currentTimeMillis()-start2));List<LinkedList<Integer>> result_list = diGraphCycle.train(diGraph, splitData);System.out.println("findCycle:"+(System.currentTimeMillis()-start2));long start3 = System.currentTimeMillis();result_list.sort(Comparator.comparingInt(List::size));System.out.println("sort:"+(System.currentTimeMillis()-start3));long start4 = System.currentTimeMillis();String save_path = "D:\\huaweichussai/m1.txt";diGraphCycle.save_file(save_path,result_list,comma,lf);System.out.println("save:"+(System.currentTimeMillis()-start4));System.out.println(System.currentTimeMillis()-start);}
}