Код Гапта. 
Методика построения графов в программном комплексе Maple

В следующей программе решается задача составления кода Гапта. Граф задается обычным образом: сначала создается список вершин, затем в операторе connect указываются соединения. Для того чтобы не повторять список вершин-листьев, используется обозначение v:=$ 5.12. Некоторой особенностью ввода данных является обозначение части вершин буквами, а части — цифрами. Это вполне допустимо. Более того, буквы в Maple могут выполнять роль идентификаторов, им можно присваивать значения, в том числе даже слова. Например, если в начале программы, сразу после restart, задать A:=`корень`, то программа не воспримет это как ошибку; ответ будет тот же, а на рисунке вершина A будет подписана. Оператор shortpathtree алгоритма Дейкстры используется здесь не совсем по назначению. Он только превращает граф в корневое дерево с корнем в вершине A. Основой программы являются оператор daughter, определяющий список сыновей вершины дерева, и оператор nops, вычисляющий длину z списка. Эта длина и записывается слева в код Гапта: kod:=z, kod.

Рис. 12.

Рис. 13.

Топологическая сортировка сети

граф программный топологический алгоритм В алгоритме используется удобная функция delete, позволяющая удалять список вершин и соответствующие дуги. Каждый уровень организуется в виде списка для того, чтобы использовать результаты в операторе Linear топологически упорядоченной сети. После формирования списка вершин одного уровня эти вершины удаляются из графа. Работа цикла while NV0 do продолжается до тех пор, пока множество вершин не станет пустым. Счетчик числа вершин — NV. Копия графа H выводится на экран по полученным уровням. Если граф содержит цикл, то на очередном этапе поиска вершины с нулевой полустепенью захода список уровня окажется пустым и произойдет досрочный выход из цикла с помощью оператора break. К графу достаточно добавить, например, дугу [3,4], для того чтобы образовался контур и топологическая сортировка оказалась невозможной.

Рис. 14

Рис. 15.