Обнаружение циклов в базе данных MySQL с использованием PHP - PullRequest
Новая
       14

Обнаружение циклов в базе данных MySQL с использованием PHP

2 голосов
/ 08 февраля 2011

У меня есть таблица в MySQL с двумя (важными) столбцами, A и B, со значением, относящимся к пакету.Строка находится в таблице, если и только если пакет A требует пакета B.

Я надеялся (1) сгенерировать граф в php, тогда (2) определить, является ли график ациклическим (DAG), и если нет, выведите (3) все циклы в графе.

Так что 3 достаточно просто, теоретически, (Алгоритм Джонсона: http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf).

(2) может быть выполнен с помощью (3) перечисления без циклов, но мне было интересно, есть ли более быстрые алгоритмы.

I 'm unsure of (1) - эффективно извлекает данные из таблицы и создает график в php, который пригоден для реализации (2) и (3).Как мне это сделать?

Кроме того, у меня также есть вторая таблица, также с двумя столбцами, имеющая строку, если и только если A конфликтует с B. Я также хотел (4) найти случаи (или проверить, что их нет), где: A требует B, B требует C, но A конфликтует с C

Ответы [ 2 ]

2 голосов
/ 18 февраля 2011

В интересах любого, кто найдет эту тему в поиске

(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)

В итоге я использовал алгоритм здесь .В основном, удаляя конечные узлы, вы либо оставляете (набор) циклов, либо пустой график. 

$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 (конфликт).обзор в комментариях к этому ответу

0 голосов
/ 08 февраля 2011

Звучит подозрительно, как «пожалуйста, помогите мне с домашним заданием».

С точки зрения рендеринга графа - взгляните на graphviz - он будет генерировать все виды графиков. Вот пример , который анализирует исходный код PHP для получения графа вызовов.

Извините, но я достаточно занят, не прочитав предоставленную вами ссылку (но хорошо сделанную для предоставления ссылки на ваш исходный материал) и не выработав алгоритм, который они использовали, затем подумав, является ли он оптимальным.

Возможно, вы захотите взглянуть на исходный код нового сборщика мусора PHP - который делает то же самое. (на самом деле вам просто нужно пройтись по дереву - если вы придете к узлу, который вы уже посетили, у вас будет цикл).

...