gayjannew.java

gayjannew.java

		private static final int TODO = -2;
		private static final int DONE = -3;
		
		public void visit(FlowBlock cur, List<FlowBlock> order, Stack<FlowBlock> stack, AtomicInteger curDfsNum, int[] index, int[] low, Set<FlowBlock> vertices_to_consider) {
			int curIndex = blocks.indexOf(cur);
			int cdn = curDfsNum.get();
			index[curIndex] = cdn;
			low[curIndex] = cdn;
			curDfsNum.incrementAndGet();
			
			stack.push(cur);
			
			for(FlowBlock child : cur.successors()) {
				if(vertices_to_consider.contains(child)) {
					int sIndex = blocks.indexOf(child);
					if(index[sIndex] == TODO) {
						visit(child, order, stack, curDfsNum, index, low, vertices_to_consider);
						low[curIndex] = Math.min(low[curIndex], low[sIndex]);
					} else if(index[sIndex] == DONE) {
						
					} else {
						low[curIndex] = Math.min(low[curIndex], index[sIndex]);
					}
				}
			}
			
			if(low[curIndex] == index[curIndex]) {
				SSC ssc = new SSC();
				FlowBlock pop = null;
				do {
					pop = stack.pop();
					ssc.blocks.add(pop);
					int pIndex = blocks.indexOf(pop);
					index[pIndex] = DONE;
				} while(pop != cur);
				
				
				System.out.println(ssc);
				
				if(ssc.blocks.size() == 1) {
					// order = cur_vertex + order
					order.add(0, cur);
				} else {
					// order = get_order(choose_first(scc), scc) + order
					// operation: calc get_order, then insert first
					order.addAll(0, deobfuscate(blocks.get(0), ssc.blocks));
				}
			}
		}
		
		public List<FlowBlock> deobfuscate(FlowBlock v, Set<FlowBlock> vertices_to_consider) {
			List<FlowBlock> order = new ArrayList<FlowBlock>();
			Stack<FlowBlock> stack = new Stack<FlowBlock>();
			AtomicInteger curDfsNum = new AtomicInteger();
			int count = blocks.size();
			int[] index = new int[count];
			int[] low = new int[count];
			
			for(FlowBlock b : vertices_to_consider) {
				int bIndex = blocks.indexOf(b);
				index[bIndex] = TODO;
			}
			
			int vIndex = blocks.indexOf(v);
			index[vIndex] = DONE;
			for(FlowBlock b : v.successors()) {
				if(vertices_to_consider.contains(b)) {
					int bIndex = blocks.indexOf(b);
					if(index[bIndex] == TODO) {
						visit(b, order, stack, curDfsNum, index, low, vertices_to_consider);
					}
				}
			}

			// System.out.printf("%s : %s.%n", Arrays.toString(index), Arrays.toString(low));
			
			// order = first_vertex + order
			order.add(0, v);
			return order;
		}