diff --git a/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java b/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java index ef5b8cb..b6689a2 100644 --- a/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java +++ b/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java @@ -1,16 +1,14 @@ package algorithm; -import java.util.HashMap; -import java.util.Map; -import java.util.Set; +import java.util.*; import models.*; import models.dataFlowModel.DataFlowModel; public class UpdateConflictCheck { DataFlowModel graph = new DataFlowModel(); - Map comp = new HashMap<>(); - Map root = new HashMap<>(); + List order = new ArrayList<>(); + Map comp = new HashMap<>(); int i = 0; int index = 0; @@ -21,98 +19,30 @@ public boolean check() { boolean result = true; for (Node node : graph.getResourceDependencyGraph().getNodes()) { - if (node.getIndegree() > 1) + if (node.getIndegree() > 1) { result = false; - } - for (Node node : graph.getResourceDependencyGraph().getNodes()) { - if (node.getIndegree() == 0) { - root.put(i, search(node, false)); break; } } - comp.clear(); - for (int j = root.size(); j < 0; j--) { - search(root.get(j), true); - } return result; } - private Node search(Node node, boolean reverse) { - comp.put(node, true); + private Node dfs(Node n, boolean reverse) { + order.add(index); + comp.put(index, n); if (!reverse) { - for (Node out : node.getSuccessors()) { - if (comp.containsKey(out)&&root.containsValue(out)) { - return search(out, reverse); + for (Node in : n.getSuccessors()) { + if (comp.containsValue(in)) { + return dfs(in, reverse); } } } else { - for (Node out : node.getPredecessors()) { - if (comp.containsKey(out)&&root.containsValue(out)) { - return search(out, reverse); + for (Node in : n.getPredecessors()) { + if (comp.containsValue(in)) { + return dfs(in, reverse); } } } - if (!reverse) - i++; - return node; - } - /* - public Set kosaraju(){ - int n = graph.size(), sz = 0; - Graph rg(n); - std::vector stk, cmp(n, -1), added(n), visited(n), ord(n); - for (auto &es : g) { - for (auto e : es) { - std::swap(e.src, e.dst); - rg[e.src].emplace_back(e); - } - sz += es.size(); - } - stk.resize(n + sz); - sz = 0; - for (int i = 0; i < n; i++) { - if (visited[i]) continue; - int s = 0; - stk[s++] = i; - while (s != 0) { - int v = stk[s - 1]; - visited[v] = true; - bool pushed = false; - for (auto &e : g[v]) { - int dst = e.dst; - if (!visited[dst]) { - stk[s++] = dst; - pushed = true; - } - } - if (pushed) continue; - int t = stk[s - 1]; - if (!added[t]) { - added[t] = true; - ord[n - ++sz] = t; - } - --s; - } - } - int k = 0; - for (int &u : ord) { - if (cmp[u] != -1) continue; - int s = 0; - stk[s++] = u; - while (s != 0) { - int v = stk[--s]; - cmp[v] = k; - for (auto &e : rg[v]) { - int d = e.dst; - if (cmp[d] == -1) stk[s++] = d; - } - } - ++k; - } - return cmp; - }*/ - - public Set tarjan(){ - + return n; } }