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

У информатици, тополошко сортирање (скраћено топсорт или топосорт) или тополошко уређење усмереног графа је линеарно уређење његових чворова тако да свака усмерена грана УВ од чвора У ка чвору 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

АлгоритмиУреди

Уобичајени алгоритми са тополошким сортирањем имају линеарну сложеност по броју грана плус броју чворова ( ).

Један од ових алгоритама, који је описао Кахн 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 у стампи.

СложеностУреди

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

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

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

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

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

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

Види јошУреди

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

РеференцеУреди

ЛитератураУреди

Спољашње везеУреди