使用 PHP 检测 MySQL 数据库中的循环

Question

我在 MySQL 中有一个表，其中有两个（重要的）列 A 和 B，其值引用了一个包。当且仅当包 A 需要包 B 时，表中才会有一行。

我希望 (1) 在 php 中生成一个图表，然后 (2) 确定是否该图是非循环的（DAG），如果不是，则打印(3)图中的所有循环。

因此，从理论上讲，3 很简单（约翰逊算法：http://dutta. csc.ncsu.edu/csc791_spring07/wrap/ Circuits_johnson.pdf）。

（2）可以通过（3）不列出循环来完成，但我想知道是否有更快的算法。

我不确定 (1) - 有效地从表中提取数据并在 php 中制作图表，这有助于实现 (2) 和 (3)。我应该怎样做呢？

---

顺便说一句，我还有第二个表，也有两列，当且仅当 A 与 B 冲突时才有一行。我还想 (4) 查找案例（或验证是否存在无）其中： A需要B，B需要C，但A与C冲突

Answer 1

为了在搜索

(1)

$pkgList = array();
$result = mysqli_query($conn, 'SELECT * FROM `Packages`');
while (($row = mysqli_fetch_array($result, MYSQLI_ASSOC)) != NULL) {
    $pkgList[] = $row['idPackages'];
}

$reqEdgeList = array();
$conEdgeList = array();

$result = mysqli_query($conn, "SELECT * FROM `Dependancies` WHERE `Relationship` = 'Requires'");
while (($row = mysqli_fetch_array($result, MYSQLI_ASSOC)) != NULL) {
    switch ($row['Relationship']) {
        case 'Requires':
            $reqEdgeList[] = array($row["DependerPackage"], $row["DependeePackage"]);
            break;
        case 'Conflicts':
            $conEdgeList[] = array($row["DependerPackage"], $row["DependeePackage"]);
            break;
    }
}

(2)和(3)

中找到此主题的任何人的利益，我最终使用了算法< a href="http://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acirclic/" rel="nofollow">此处。基本上，通过删除叶节点，您要么留下一个（一组）循环，要么留下一个空图。

$allReqs = $reqEdgeList;

$noDependanciesCycle = true;

$searching = true;
while ($searching) {
    if (empty($pkgList)) {
        $searching = false;
        echo "Req is a DAG\n<br />";
    } else {
        $foundleaf = false;
        $leaf = null;
        foreach ($pkgList as $key => $l) {
            $isLeaf = true;
            foreach ($reqEdgeList as $k => $edge) {
                if ($edge[0] == $l) {
                    $isLeaf = false;
                }
            }

            if ($isLeaf) {
                $foundleaf = true;
                $leaf = $l;
            }
        }
        if ($foundleaf) {
            $pkgList = array_diff($pkgList, array($leaf));
            foreach ($reqEdgeList as $key => $value) {
                if ($value[1] == $leaf) {
                    unset($reqEdgeList[$key]);
                }
            }
            $reqEdgeList = array_values($reqEdgeList);
        } else {
            $searching = false;
            echo "Req cycle detected\n<br />";
            $noDependanciesCycle = false;
            print_r($reqEdgeList);
            echo "<br />\n";
        }
    }
}

(4)

为了找到A需要B需要C，但是A与C冲突，我对每个冲突都使用了深度优先搜索，从A开始，寻找C（冲突）。

$reqEdgeList = $allReqs;
echo "<br />\n";

$anyReqConfError = false;
foreach ($conEdgeList as $endpoints) {
    for ($i = 0; $i < 2; $i++) {
        if ($i == 0) {
            $startPkg = $endpoints[0];
            $endPkg = $endpoints[1];
        } else {
            $startPkg = $endpoints[1];
            $endPkg = $endpoints[0];
        }

        $marked = array();
        foreach ($allPkgs as $pkg) {
            $marked[$pkg] = false;
        }

        $queue = array();
        $queue[] = $startPkg; // enque
        $marked[$startPkg] = true;

        $searching = true;
        $found = false;
        while ($searching) {
            $v = array_shift($queue); // deque (use array_pop for stack (dfs))
            if ($v == $endPkg) {
                $searching = false;
                $found = true;
            } else {
                foreach ($reqEdgeList as $edge) {
                    if ($edge[0] == $v) {
                        $w = $edge[1];
                        if (!$marked[$w]) {
                            $marked[$w] = true;
                            $queue[] = $w;
                        }
                    }
                }
            }

            if($searching) {
                $searching = !empty($queue);
            }
        }

        if($found) {
            echo "$startPkg requires $endPkg, but are conflicting [$endpoints[0] $endpoints[1]]\n<br />";
            $anyReqConfError = true;
            $noDependanciesCycle = false;
        }
    }
}

我很感激评论中对此答案的任何代码审查

Answer 2

听起来很可疑，就像“请帮我做作业”。

在渲染图表方面 - 看看 graphviz - 这将生成各种图表。 这是一个示例 解析 PHP 源代码以获取调用图。

抱歉，但我很忙，没有阅读您提供的参考资料（但提供了源材料的链接做得很好），也没有计算出他们使用的算法，然后考虑它是否是最佳的。

您可能想看看新的 PHP 垃圾收集器的源代码 - 它做同样的事情。 （实际上，您只需要遍历树 - 如果您到达已经访问过的节点，那么您就得到了一个循环）。