Топологическая сортировка "Best-Effort"

Question

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

Обычно это можно сделать с помощью топологическая сортировка, но у моего графа есть циклы. Есть ли что-то вроде топологической сортировки с «максимальными усилиями», которая может пытаться определить «наиболее важных» родителей по таким вещам, как количество соединений или что-то аналогичное?

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

Answer 1

Один из способов добиться чего-то подобного - вычислить для каждого узла, сколько других узлов доступно из него, а затем отсортировать узлы на основе этого числа.

В качестве альтернативы, вы можете отменить эту логику c. Для каждого узла вычислите, сколько узлов имеет к нему доступ, затем отсортируйте узлы в порядке возрастания.

Answer 2

Google pagerank-Algorithm оценивает веб-сайты, гиперссылки которых представлены в виде направленных ребер. Сайты со многими важными входящими ссылками высоко оцениваются.
В вашем случае все выглядит наоборот. Вам нужно немного / нет входящего фронта.
Поэтому вы можете попробовать алгоритм pagerank, но обратить его результаты таким образом, чтобы узлы с самым высоким рейтингом страницы получили наименьший рейтинг наследования, и наоборот.