Блог

Главная - Вопросы по программированию - Как удалить избыточные смежности в DAG?

Как удалить избыточные смежности в DAG?

#algorithm #graph #graph-algorithm

#алгоритм #График #граф-алгоритм

Вопрос:

Я ищу алгоритм для уменьшения избыточных смежностей в ориентированном ациклическом графе. Я провел небольшое исследование и нашел несколько тем, которые ссылаются на транзитивное сокращение.

После некоторых тестов я пришел к выводу, что для меня этого недостаточно. Кажется, что транзитивное сокращение удаляет только избыточные зависимости на первом уровне:

Например:

Если есть ребро a -> b и ребро b -> c , то оно удаляет ребро a -> c .Но если есть ребро a -> b , b -> c , и c -> d , то оно не удаляет ребро a -> d .

Поэтому я думаю, что мне нужно что-то вроде транзитивного сокращения, но для всех уровней.

Есть ли какой-либо алгоритм для очистки моих графиков таким образом?

Большое спасибо!

Комментарии:

1. Если есть ребро a -> b и другой путь a -> x -> y -> ... -> z -> b , то ребро a -> b должно быть удалено. Это то, что вы хотите?

2. На самом деле это то, что делает транзитивное сокращение — оно удаляет избыточные ребра для всех уровней.

3. Да, имя — топологическая сортировка

4. Я думаю, что @WhatsUp прав! Однако я видел много псевдокода, связанного с транзитивным сокращением, которое уменьшает только первый уровень зависимостей. Наконец, я использую networkx, что довольно хорошо!

Ответ №1:

Я реализовал транзитивное сокращение для всех уровней. Если кто-нибудь найдет для этого. Это здесь

 void process() {

    // Build a side-graph edge2 ( init by clone mainGraph edge ). if a > b > c and a > c  = false. make a > c true
    // the side-graph make the multi level problem same as the first level problem
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < n; j  ) {
                for (int k = 0; k < n; k  ) {
                    if (edge2[i][k] amp;amp; edge2[k][j] amp;amp; !edge2[i][j]) {
                        edge2[i][j] = true;
                    }
                }
        }
    }

    // Check transitive at edge2 ( subGraph )
    // update transitive at edge ( mainGraph )
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < n; j  ) {

            if (edge[i][j]) {

                for (int k = 0; k < n; k  ) {
                    if (edge2[i][k] amp;amp; edge2[k][j]) {
                        if (edge[i][j]) {
                            reduceNumber  ;
                        }

                        edge[i][j] = false;

                    }
                }

            }

        }
    }

}