Тополошко уређење

У информатици, тополошко сортирање (скраћено топсорт или топосорт) или тополошко уређење усмереног графа је линеарно уређење његових чворова тако да свака усмерена грана УВ од чвора У ка чвору V, У долази пре V у уређењу. На пример, чворови графа представљају задатке које треба извршити, а гране представљају ограничења да неки задатака мора бити извршен пре неког другог; у овој апликацији, тополошко уређење је само валидан распоред извршавања задатака. Тополошко уређење је могуће, ако и само ако граф нема усмерене циклусе, односно да је усмерени ацикличан граф (УАГ). Сваки УАГ има најмање једно тополошко уређење, и познат је алгоритам за конструисање тополошког уређења било ког УАГ у линеарном времену.

Примери

Канонска апликација тополошког сортирања (тополошког уређења) је у планирању распореда послова или задата на основу њихове зависности; алгоритми тополошког сортирања су први пут проучавани раних 1960-их година у контексту ПЕРТ технике планирања управљања пројектима (^[1]). Послови су представљени чворовима и постоји грана од А ка Б, ако посао А мора бити извршен пре него што се посао Б може запоцети (пример: код прања веш машине, машина мора да заврши са прањем веша да би га ми сатвили на сушење). Дакле, тополошко сортирање нам даје редослед којим треба да извршавамо послове.

У информатици, апликације овог типа прерастају у инструкције организације, уређењу формула ћелија евалуације при реизрачунавању формула валуације у табелама, логичке синтезе, одређивање распореда задатака компилације који се извршавају у мејкфајловима, серијализацији података и одређивању зависности симбола у линкерима.

Граф приказан са леве стране се може на много начина тополошки сортирати, укључујући:

7, 5, 3, 11, 8, 2, 9, 10 (вузуелно са лева на десно, са врха ка дну)
3, 5, 7, 8, 11, 2, 9, 10 (прво чворови са најмањом вредношћу)
3, 7, 8, 5, 11, 10, 2, 9
5, 7, 3, 8, 11, 10, 9, 2 (најкраце гране прво)
7, 5, 11, 3, 10, 8, 9, 2 (прво чворови са највечом вредношћу)
7, 5, 11, 2, 3, 8, 9, 10

Алгоритми

Уобичајени алгоритми са тополошким сортирањем имају линеарну сложеност по броју грана плус броју чворова ( $O(\left|{V}\right|+\left|{E}\right|)$ ).

Један од ових алгоритама, који је описао Кахн 1962, ради тако што одабира чворове у истом редоследу као и евентуално тополошко сортирање.Прво наде листу „почетних чворова“ који немају улазне гране и убацује их у С; барем један такав чвор мора постојати у ацикличном графу. Затим:

L ← Prazna lista koja će sadržati sortirane elemente
S ← Skup svih čvorova bez ulaznih grana
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (Graf ima bar jedan ciklus)
else 
    return L (Topološki sortirani)

Ако је граф УАГ, решење це се налазити у листи L(решења не морају бити јединствена). У супротном, граф има бар један циклус и тополошко сортирање се не може урадити.

Напоменимо да, због не-јединствености резултата сортирања, структура С може бити једноставно скуп, ред или стек.У зависности од редоследа којим се чворови н избацују из скупа С, добијамо различита решења.Варијације Кахн-овог алгоритма који разбије везе лексикографских облика, кључна је компонента Кафман-Грахамовог алгоритма за паралелно планирање и слојевито цртање графа.

Алтернативни алгоритам за тополошко сортирање је заснован на претраживању у дубину.Код овог алгоритма, гране су усмерене у супротном смеру од претхног алгоритма(а у супротном смеру него сто су приказане на дијаграму узнад). Постоји грана од А ка Б ако посао А зависи од посла Б(ако посао Б мора бири извршен пре него сто посао А може да се започне). Алгоритам се креће кроз сваки чвор графа, у произвољном редоследу, започињући претрагу у дубину која се зауставља када се дође до чвора који је већ посећен.

L ← Prazna lista koja će sadržati sortirane čvorove
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(čvor n)
    if n has a temporary mark then stop (nije UAG)
    if n is not marked (nije posećen) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        add n to head of L

Приметимо да се сваки чвор н додаје у излазну листу L тек након што се размотре сви чворови од којих н зависи(сви потомци чвора н у графу).Посебно, када алгоритам дода чвор н, загарантовано је да су сви чворови од којих зависи н већ додати у излазну листу L:дадати су у L или претходним рекурзивним позивом висит() или ранијим позицом висит(). Како су сви чворови и свака грана посећени једном, алгоритам се извршава у линеарном времену. Овај алгоритам, заснован је на претрази у ширину, описао га је Цормен ет ал. 2001, али га је пре њега описао Тарјан 1976 у стампи.

Сложеност

Рачунарска комплексност израчунавања у усмереном графу је НЦ²; што значи да се може израчунати за О(лог² н) времена на паралелном рачунару помоћу полиномијалног броја од О(н^к)процесора, за исту константу к^[2].

Јединственост

Када би тополошко сортирање имало особину да све парове узастопних чворова у сортираном поретку повеже гранама, добили бисмо усмерен Хамилтонов пут у УАГ. Ако Хамилтонов пут постоји, тополошки поредак је јединствен; ниједан други поредак не задовољава ивице пута.Обрнуто, ако тополошко сортирање не формира Хамилтонов пут, УАГ ће имати два или више валидна тополошка поретка, јер је у овом случају увек могуће формирати други исправан поредак заменом два узастопна чвора који нису повезани граном. Дакле, могуће је проверити у линеарном времену да ли постоји јединствени поредак, и да ли постоји Хамилтонов пут, упркос НП-тежини проблема Хамилтоновог пута за неке општије усмерене графове^[3].

Однос према релацији поретка

Тополошка сортирања су уско повезана са концептом линеаног истезања релације поретка у математици.

Парцијално уредјен скуп је скуп објеката са дефиницијом релације мање или једнако "≤", задовољавајући аксиоме рефлексивности(x ≤ x), антисиметричности(ако је x ≤ y и y ≤x онда је x = y), и транзитивности (ако је x ≤ y и y ≤ з, онда је x ≤ з).Релација тоталног поретка је релација поретка у којој су свака два објекта x и y из скупа упоредиви, или је x ≤ y или је y ≤ x.Тотална уређења се користе у информатици како би оператори поређења могли да изеду упоређивање код алгоритама за сортирање.За коначне скупове, тотална уређења се могу идентификовати као линеаран низ објеката где је "≤" релација тачна кад год први објекат претходи другом у реду;алгоритми за сортирање упоређивањем се могу искористити за претварање тоталног уређења у низ на овај начин. Линеарно истезање релације поретка је тотални поредак који је усаглашен са њим, у смислу ако је x ≤ y у релацији поретка онда је и x ≤ y у тоталном поретку такође.

Може се дефинисати релација поретка из било ког ДАЛ-а тако што ћемо поставити да скуп објеката буду чворови ДАЛ-а и дефинишемо да је x ≤ y тачно за било која два чвора x и y', кад год постоји усмерен пут од x ка y,тј. кад год из x можемо да стигнемо до y. Овако дефинисано, тополошко уређење ДАЛ-а је исто што и линеарно истезање ове релације поретка. Обрнуто, свака релација поретка може бити дефинисана као релација домашаја у ДАЛ-у. Један начин да се ово изведе је да се дефинише ДАЛ које има чвор за сваки објекат из скупа релације поретка и грану xy за сваки пар објеката за које важи x ≤ y. Алтернативан начин да се уради ово је да се користи транзитивно затворење релације поретка;у целини, овако добијамо ДАЛ-ове са мање грана али је релација домашаја и даље иста релација поретка. Овако се алгоритми за тополошко сортирање могу користити за налажење линеарних истезања релације поретка.

Види још

тсорт, Јуникс програм за тополошко сортирање

Литература

Цоок, Степхен А. (1985). А Таxономy оф Проблемс wитх Фаст Параллел Алгоритхмс. Информатион анд Цонтрол. 64. стр. 2—22. дои:10.1016/С0019-9958(85)80041-3. .
Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (2001). „Сецтион 22.4: Топологицал сорт”. Интродуцтион то Алгоритхмс (2нд изд.). МИТ Пресс анд МцГраw-Хилл. стр. 549-552. ИСБН 978-0-262-03293-3. .
Јарнагин, M. П. (1960). Аутоматиц мацхине метходс оф тестинг ПЕРТ нетwоркс фор цонсистенцy. Тецхницал Меморандум Но. К-24/60. Дахлгрен, Виргиниа: У. С. Навал Wеапонс Лабораторy. .
Кахн, Артхур Б. (1962). Топологицал сортинг оф ларге нетwоркс. Цоммуницатионс оф тхе АЦМ. 5. стр. 558—562. дои:10.1145/368996.369025. .
Тарјан, Роберт Е. (1976). Едге-дисјоинт спаннинг треес анд дептх-фирст сеарцх. Ацта Информатица. 6. стр. 171—185. дои:10.1007/БФ00268499. .
Вернет, Осwалдо; Маркензон, Лилиан (1997). „Хамилтониан проблемс фор редуцибле флоwграпхс”. Проц. 17тх Интернатионал Цонференце оф тхе Цхилеан Цомпутер Сциенце Социетy (СЦЦЦ '97). стр. 264—267. дои:10.1109/СЦЦЦ.1997.637099. .

Спољашње везе

NIST Dictionary of Algorithms and Data Structures: topological sort
dep-trace Orders basic dependencies and unfolds nested ones. (basic: without 2D graphical presumption)

[1] Јарнагин 1960

[2] Цоок 1985

[3] Вернет & Маркензон 1997

[1]

[2]

[3]