diff --git a/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java b/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java index f596acd..ef5b8cb 100644 --- a/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java +++ b/AlgebraicDataflowArchitectureModel/src/algorithm/UpdateConflictCheck.java @@ -2,6 +2,7 @@ import java.util.HashMap; import java.util.Map; +import java.util.Set; import models.*; import models.dataFlowModel.DataFlowModel; @@ -9,7 +10,9 @@ public class UpdateConflictCheck { DataFlowModel graph = new DataFlowModel(); Map comp = new HashMap<>(); + Map root = new HashMap<>(); int i = 0; + int index = 0; public void setup(DataFlowModel graph) { this.graph = graph; @@ -17,7 +20,6 @@ public boolean check() { boolean result = true; - Map root = new HashMap<>(); for (Node node : graph.getResourceDependencyGraph().getNodes()) { if (node.getIndegree() > 1) result = false; @@ -39,13 +41,13 @@ comp.put(node, true); if (!reverse) { for (Node out : node.getSuccessors()) { - if (comp.containsKey(out)) { + if (comp.containsKey(out)&&root.containsValue(out)) { return search(out, reverse); } } } else { for (Node out : node.getPredecessors()) { - if (comp.containsKey(out)) { + if (comp.containsKey(out)&&root.containsValue(out)) { return search(out, reverse); } } @@ -54,4 +56,63 @@ 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(){ + + } }