Топологическая сортировка
Учитывая сопоставление между элементами и элементами, на которых они зависят, топологические позиции сортировки сортируются, так что ни один элемент не предшествует элементу, от которого он зависит.
Компиляция библиотеки на языке VHDL имеет ограничение на то, что библиотека должна быть скомпилирована после любой библиотеки, от которой она зависит.
Задача:
Напишите функцию, которая вернет действительный порядок компиляции библиотек VHDL из их зависимостей.
Предположим, что имена библиотек - это одиночные слова. Пункты, упомянутые как только иждивенцы, не имеют собственных иждивенцев, но их порядок компиляции должен быть дан. Любые собственные зависимости следует игнорировать. Любые неустановимые зависимости следует игнорировать.
В качестве примера используйте следующие данные:
БИБЛИОТЕЧНЫЕ БИОГРАФИЧЕСКИЕ ЗАВИСИМОСТИ ======= ============================= des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib Synopsys
Примечание: вышеуказанные данные были бы неустановимыми, если, например, dw04 добавляется в список зависимостей dw01 .
Cf:
<a href="http://rosettacode.org/wiki/Topological sort/Extracted top item" title="Topological sort/Extracted top item">Topological sort/Extracted top item</a>. Существует два популярных алгоритма топологической сортировки:
Канский топологический сорт 1962 года и поиск по глубине: топологическая сортировка
Джейсон Сакс: «Десять небольших алгоритмов, часть 4: топологическая сортировка» .
Write a function that will return a valid compile order of VHDL libraries from their dependencies.
- Assume library names are single words.
- Items mentioned as only dependents have no dependents of their own, but their order of compiling must be given.
- Any self dependencies should be ignored.
- Any un-orderable dependencies should be ignored.
Use the following data as an example:
LIBRARY LIBRARY DEPENDENCIES ======= ==================== des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys
Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.
C.f.:
There are two popular algorithms for topological sorting: