package jnpf.elnService.formula;
|
|
import jnpf.elnEntity.formula.ElnTemplateFormulaBindingEntity;
|
|
import java.util.ArrayList;
|
import java.util.Collection;
|
import java.util.Collections;
|
import java.util.Comparator;
|
import java.util.HashMap;
|
import java.util.LinkedHashMap;
|
import java.util.LinkedHashSet;
|
import java.util.List;
|
import java.util.Map;
|
import java.util.PriorityQueue;
|
import java.util.Set;
|
|
public class FormulaDependencyGraph {
|
|
public Result validate(Collection<ElnTemplateFormulaBindingEntity> bindings) {
|
Map<String, ElnTemplateFormulaBindingEntity> nodes = new LinkedHashMap<>();
|
Map<String, String> resultOwners = new HashMap<>();
|
for (ElnTemplateFormulaBindingEntity item : bindings == null
|
? Collections.<ElnTemplateFormulaBindingEntity>emptyList() : bindings) {
|
if (item != null && "ACTIVE".equals(item.getBangdingZhuangtai())) {
|
nodes.put(item.getId(), item);
|
resultOwners.put(item.getJieguoBangdingId(), item.getId());
|
}
|
}
|
Map<String, Set<String>> edges = new LinkedHashMap<>();
|
Map<String, Integer> indegrees = new LinkedHashMap<>();
|
for (String id : nodes.keySet()) {
|
edges.put(id, new LinkedHashSet<>());
|
indegrees.put(id, 0);
|
}
|
for (ElnTemplateFormulaBindingEntity consumer : nodes.values()) {
|
for (String fieldBindingId : safeValues(consumer.getCanshuYingshe())) {
|
String producer = resultOwners.get(fieldBindingId);
|
if (producer != null && edges.get(producer).add(consumer.getId())) {
|
indegrees.put(consumer.getId(), indegrees.get(consumer.getId()) + 1);
|
}
|
}
|
}
|
PriorityQueue<String> ready = new PriorityQueue<>();
|
indegrees.forEach((id, degree) -> { if (degree == 0) ready.add(id); });
|
List<String> order = new ArrayList<>();
|
while (!ready.isEmpty()) {
|
String current = ready.poll();
|
order.add(current);
|
List<String> next = new ArrayList<>(edges.get(current));
|
next.sort(Comparator.naturalOrder());
|
for (String target : next) {
|
int degree = indegrees.get(target) - 1;
|
indegrees.put(target, degree);
|
if (degree == 0) ready.add(target);
|
}
|
}
|
if (order.size() == nodes.size()) return Result.valid(order);
|
return Result.cycle(findCycle(edges));
|
}
|
|
private static Collection<String> safeValues(Map<String, String> values) {
|
return values == null ? Collections.emptyList() : values.values();
|
}
|
|
private static List<String> findCycle(Map<String, Set<String>> edges) {
|
Map<String, Integer> colors = new HashMap<>();
|
List<String> stack = new ArrayList<>();
|
List<String> ids = new ArrayList<>(edges.keySet());
|
Collections.sort(ids);
|
for (String id : ids) {
|
List<String> cycle = dfs(id, edges, colors, stack);
|
if (!cycle.isEmpty()) return cycle;
|
}
|
return Collections.emptyList();
|
}
|
|
private static List<String> dfs(String id, Map<String, Set<String>> edges,
|
Map<String, Integer> colors, List<String> stack) {
|
int color = colors.getOrDefault(id, 0);
|
if (color == 2) return Collections.emptyList();
|
if (color == 1) {
|
int start = stack.indexOf(id);
|
List<String> cycle = new ArrayList<>(stack.subList(start, stack.size()));
|
cycle.add(id);
|
return cycle;
|
}
|
colors.put(id, 1);
|
stack.add(id);
|
List<String> targets = new ArrayList<>(edges.getOrDefault(id, Collections.emptySet()));
|
Collections.sort(targets);
|
for (String target : targets) {
|
List<String> cycle = dfs(target, edges, colors, stack);
|
if (!cycle.isEmpty()) return cycle;
|
}
|
stack.remove(stack.size() - 1);
|
colors.put(id, 2);
|
return Collections.emptyList();
|
}
|
|
public static final class Result {
|
private final List<String> topologicalOrder;
|
private final List<String> cyclePath;
|
private Result(List<String> order, List<String> cycle) {
|
this.topologicalOrder = Collections.unmodifiableList(new ArrayList<>(order));
|
this.cyclePath = Collections.unmodifiableList(new ArrayList<>(cycle));
|
}
|
static Result valid(List<String> order) { return new Result(order, Collections.emptyList()); }
|
static Result cycle(List<String> cycle) { return new Result(Collections.emptyList(), cycle); }
|
public boolean isValid() { return cyclePath.isEmpty(); }
|
public List<String> getTopologicalOrder() { return topologicalOrder; }
|
public List<String> getCyclePath() { return cyclePath; }
|
}
|
}
|
