Տոպոլոգիական դասավորում/Ավազարկղ

“Dependency resolution” վերահղված է այստեղ։ other uses տես Dependency (disambiguation).

Համակարգչային գիտության մեջ, տոպոլոգիական դասավորումը (երբեմն կրճատ տոպսորտ կամ տոպոսորտ) կամ տոպոլոգիական կապերի ուղղորդված դիագրամմայի գծային մասի ուղղահայաց ձախ մասը ինչպիսին է ցանկացաց uv գագատի համար, u-ն գալիս է նախքան v կարգը : Օրինակ, դիագրամմայի վերևի հատվածը կարող է ներկայացնել առաջադրանքներ կատարելու համար, և գագաթները կարող են ներկայացնել հարկադրանքներ, որը պետք է ներկայացնի մեկ առաջադրանքը նախքան մեկ ուրիշը; այս կիրառությունով տոպոլոգիական դասավորումը ընդունելի արդյունք է առաջադրանքների համար: Տոպոլոգիական դասավորումը հնարավոր է եթե դիագրամման չունի ուղղորդված ցիկլ , այսինքն եթե ունի ուղղորդված ացիկլիկ դիագրամմա (ՈՒԱԴ).Որևէ ՈՒԱԴ նվազագույնը ունի մեկ տոպոլոգիական դասավորում, և ալգորիթմները հայտնի են որպես որևէ ՈՒԱԴ ի տոպոլոգիական դասավորման կառույց կախված գծային ժամանակահատվածից.

Օրինակներ

Տոպոլոգիական դասավորման կանոնակարգված կիրառությունը (տոպոլոգիական կարգ) աշխատանքների ցուցակագրված հաջորդականությունն է կամ առաջադրանքները հիմնվաց են իրենց կախյալներից,տոպոլոգիական դասավորման ալգորիթմները ուսումնասիրվել է վաղ 1960-ական թվականներին` ծրագրերի վերանայման և գնահատման տեխնիկա կոնտեքստում մենեջմենթի նախագծման համար ԾՎԳՏ (Jarnagin 1960):Աշխատանքները որոնք նկարագրվում են վերևում, և x ից մինչև y կա մեկ գագաթ x աշխատանքը պետք է կատարվի նախքան y աշխատանքը կարող է կատարվել (օրինակ, երբ շոր ենք լվանում, նախքան մեր շորերը չորացնելը լվացքի մեքենան պետք է ավարտի լվացքը): Այնուհետև, տոպոլոգիական դասավորումը տալիս է մի ուղղություն,որը ներկայացնում է աշխատանքները:

Համակարգչային գիտության մեջ այս տեսակ կիրառությունները առաջացնում են գրաֆիկական հրահանգավորում, կարգավորելով բանաձևի էլեմենտար գնահատականը,երբ վերահաշվարկում ենք բանաձևի արժեքները աղյուսակներում, տրամաբանական վերլուծություններում, սահմանելով մեքենայական լեզվի վերահաղորդումը հատուկ ծրագրի օգնությամբ ստեղծելով ֆայլերը, վերլուծելով կախյալ մնացորդի նշանը:

Գրաֆիկը որը ներկայացված է ստորև ունի շատ ճիշտ տոպոլոգիական դասավորում,ընդգրկելով. 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|)$).

Այս ալգորիթմներից առաջինը նկարագրվում է Կաղապար:Harvtxt-ի կողմից, այդ նույն ձևով ընտրվում են աշխատանքները ուղղահայացների կողմից որպես վերջնական տոպոլոգիական դասավորում: Առաջինը, գտնել "հանգույցների սկզբնական ցուցակը" որը չունի մուտքային գագաթներ և տեղադրել դրանք S-ի մեջ,նվազագույնը մեկ այսպիսի դիագրամմա պետք է գոյություն ունենա ացիկլիկ դիագրամմայում:Այնուհետև.

L ← դատարկ ցանկ,որը կպարունակի տեսակավորված էլեմենտներ 
S ← գործի դնել բոլոր հանգույցները,որոնք ,ուտք չունեն դեպի գագաթ,
մինչ S-ը կարող է կատարել ոչ դատարկ ցանկով
    տեղաշարժել հանգույցը n ից S
    տեղադրել n-ը դեպի L
    յուրաքանչյուր  m հանգույց  e գագաթի հետ  կատարելով n ից m
        remove edge e from the graph
        եթե m-ը չունի մեկ այլ մոտքային գագաթներ,ապա տեղադրենք  
         m-ը դեպի S
եթե դիագրամման ունի գագաթներ ապա 
    վերադարձնում է սխալ
     (դիագրամման ունի նվազագույնը մեկ ցիկլ)
հակառակ դեպքում 
    վերադարձնում է L (տոպոլոգիական դասավորման կարգ)

Եթե դիագրամման ունի ՈՒԱԴ, ապա լուծումը կնդգրկվի L ցուցակում (առանձնահատուկ լուծում անհրաչեշտ չէ): Այլ կերպ ասած, դիագրամման նվազագույնը պետք է ունենա մեկ ցիկլ,հետևաբար տոպոլոգիական դասավորումը հնարավաոր է:

Նկատենք, որ այն անդրադառնում է արդյունք ոչ յուրահատուկ տեսակի վրա, S կառույցը կարող է պարզապես կիրառվել կամ հերթի կանգնել կամ կուտակվել:Կախված լինելով հանգույցների հրահանգից n-ը տեղափոխվում է S մուտք, ստեղծվում է մեկ այլ լուծում: Կան-ի ալգորիթմի տարբերակը հանգւցալուծում է լեքսիկոգրաֆիան որը հանդիսանում է Քոֆֆման-Գրեհեմի ալգորիթմի բաղադրիչի բանալին զուգահեռ ցանկի և եռաշերտ դիագրամմայի գծագրման համար:

Տոպոլոգիական դասավորման համար երկընտրանքային ալգորիթմը հիմնված է առաջին-խորը ուսումնասիրման վրա: Այս ալգորթիմի համար գագաթները ստուգվում են հակառակ ուղղությամբ ինչպես նախորդ մեկը (այն փնտրում է հանգույցները գագաթների հետ մատնանշելով տրված հանգույցը դրա փոխարեն,որը հնարավոր է տեղակայել տարբեր պահանջներում տվյալների կառույցի համար,այն օգտագործելով դիագրամման օգտագործելու համար, և դա սկսվում է ոչ ելքի գագաթներից): Ընգծելով ալգորիթմը դիագրամմայի յուրաքանչյուր հանգույցի միջոցով անկանոն ձևով , նախաձեռնելով առաջին-խորը ուսումնասիրությունը որն ավարտվում է երբ դիպչում է որևէ հանգույցի որը մուտէ էր գործել տոպոլոգիական դասավորման հենց սկսզբից.

L ← դատարկ ցանկ որն ընդգրկում է տեսակավորված հանգույցները
S ← գործի դնել բոլոր հանգույցները ոչ մուտքի  գագաթների հետ 

յուրաքանչյուր n հանգույց կատարվում է s-ում

    մուտք (n) 
ֆունկցիայի մուտք(հանգույց n)
    եթե n դեռ չի մուտքագրվել ապա
        նշում ենք n-ը որպես մւտքագրված
        յուրաքանչյուր m հանգույց մեկ գագաթի հետ կատարվելով m-ից n 
            մուտք(m)
        ավելացնել n-ը  L-ով

նկատենք որ յուրաքանչյուր n հանգույց ավելացվում է ստեղծված L ,իայն այն բանից հետո ենթադրելով որ բոլոր հնգույցները կախված են n-ից (n-ի բոլոր սկզբնական հանգույցները դիագրամմայում): Մասնավորապես, երբ ալգորիթմը ավելացնում ենքn հանգույցին, մենք համոզված ենք ,որ բոլոր հանգույցները որից կախված է n-ը արդեն դուրս է մղվել L ցանկից. նրանք կամ ավելացվել էին L-ին նախորդ կրկնվող մուտքի կանչի ժամանակ(), կամ ավելի վաղ մուտքի կանչի ժամանակ(): նախքան ամեն մի գագաթ և հագույց մուտքագրվում են մեկ անգամ, ալգորիթմը անցնում է գծային ժամանակահատվածով: Նկատենք որ ստորև տրված հասարակ կեղծ կոդը չի կարող հայտնաբերել սխալը երբ մուտքի դիագրամման պարունակում է ցիկլեր:Հետևելով հանգույցներին, որոնք մուտքագրվում են ավելի քան մեկ անգամ հերթական մւտքի կանչի այցելության ընտացքում,ալգորիթմը կարող է զտել հայտնաբերելով ցիկլեր, (օրինակ,անցնելով ներքևի ցանկը որպես այցելության արգումենտ(), նշելով թե որ հանգույցներն են արդեն այցելել ընթացիկ կանչի կուտակումներում): Այս խորը-առաջին-ուսումնասիրման-վրա հիմնված ալգորիթմը առջինն ուսումնասիրվում է Կաղապար:Harvtxt:

Եզակիություն

Եթե տոպոլոգիական դասավորումը ունի հատկություն,որը բոլոր գագաթներով միացված հաջորդական ուղղահայացները զույգավորում է Համիլտոնյան ուղուց դեպի ՈՒԱԴ:Եթե Համիլտոնյան ուղին գոյություն ունի,ապա տոպոլոգիական դասավորումը ունիկալ է,ոչ մի առնչություն չունի գագաթների ուղու հետ: Ընդհակառակը, եթե տոպոլոգիական դասավորումը չի ձևավորում համիլտոնյան ողին,ՈՒԱԴ-ն կունենա 2 և ավելի ճիշտ տոպոլոգիական հրահանգ, և այդ ձևով միշտ հնարավոր է ձևավորել` 2րդ ճիշտ հրահանգը փոխանակելով միմյանց գագաթով չմիացված 2 հաջորդական ուղղահայացներով:Հետևաբար,հնարավոր է ստուգել թե արդյոք գոյություն ունի յուրահատուկ հրահանգավորում ամբողջական ժամանակաշրջանում և թե արդյոք գոյություն ունի համիլտոնյան ուղի, հակառակ NP-կարծրության Համիլտոնյան ուղղու խնդիրը ավելի ընդհանուր է ուղղորդված դիագրամմաների համար (Vernet & Markenzon 1997).

Կապը մասնակի հրահանգների միջև

Տոպոլոգիական հրահանգները նաև սերտորեն կապված են մասնակի հրահանգի գծային երկարության հետ մաթեմատիկայում:

Մասնակի հրահանգը տեղադրված է օբյեկտների հետ միասին "≤" անհավասարություն հասկացությանը բավարարելով ռեֆլեքսիվության աքսիոմաները (x = x), հակասիմետրիկ (եթե x ≤ y և y ≤x ապա x = y) և անցողիկ (եթե x ≤ y և y ≤ z, ապա x ≤ z): Ամողջական գրահանգը մասնակի հրահանգ է , որում տեղակայված է 2 x և y օբյեկտներ, կամ x ≤ y կամ y ≤ x: Ամբողջական հրահանգները սովորական են համակարգչային գիտության մեջ որպես համեմատական օպերատորներ, որոնք պետք ներկայացնեն համեմատման տեսակավթրմանալգորիթմները: Սահմանափակ արժեքի համար, ամբողջական հրահանգները կարող են նույնացվել գծային օբյեկտների հերթականության հետ, որտեղ "≤" կապը ճիշտ է երբ էլ որ հրահանգում առաջին օբյեկտը նախորդում է երկրորդ օբյեկտին,համեմատության տեսակավորման ալգորիթմը կարելի է օգտագործել` փոխակերպելով ամբողջական հրահանգը հերթականության հետ ձևով: Մասնակի հրահանգի գծային երկարացումը ամբողջական հրահանգ է,որա հարմար է դրա հետ պատկերում եթե մասնակի հրահանգում x ≤ y,ապա x ≤ y ամբողջական հրահանգում:

Կարող ենք մասնակի հրահանգավորումը սահմանել ՈՒԱԴ-ից թույլ տալով, որպեսզի ՈՒԱԴ-ի տեղայնացումը լինի ուղղահայաց, և սահմանելով x ≤ yլինի ճիշտ, ցանկացած 2 x և y համար,երբ էլ որ գոյություն ունի x ից y ուղղորդված ուղի,այն է երբ էլ որ y-ը հասանելի է xից:Այս սահմանումներով ՈՒԱԴ-ի տոպոլոգիական դասավորումը նույնն է ինչ որ մասնակի հրահանգի գծային երկարացումը: Ընդհակառակը,մասնակի հրահանգավորումը կարող է սահմանվել որպես ՈւԱԴ-ի հասանելի կապ:Դա կատարելու մեկ ձևը ՈՒԱԴ-ի սահմանումն է, որն ունի ՈՒԱԴ-ը արտադրող ՈՒղղահայցներ յուրաքանչյուր օբյեկտի համար քիչ գագաթով,բայց հասանելիության կապը այս ՈՒԱԴ-ներում դեռևս մույն մասնակի հրահանգն է: Օգտագործելով այս ցուցումները տոպոլոգիական հրահանգի ալգորիթմները կարող ենք օգտագործել գտնելու մասնակի հրահանգբերի երկարացւմները:

See also

• tsort, a Unix program for topological sorting
• Feedback arc set, a (possibly empty) set of arcs which, if removed from the graph, make it possible to topologically sort it. Useful for dealing with graphs with cycles.

References

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), «Section 22.4: Topological sort», Introduction to Algorithms (2nd տպ.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7 .
• Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Dahlgren, Virginia: U. S. Naval Weapons Laboratory .
• Kahn, A. B. (1962), «Topological sorting of large networks», Communications of the ACM 5 (11), doi:10.1145/368996.369025 .
• Tarjan, Robert E. (1976), «Edge-disjoint spanning trees and depth-first search», Algorithmica 6 (2), doi:10.1007/BF00268499 .
• Vernet, Oswaldo; Markenzon, Lilian (1997), «Hamiltonian problems for reducible flowgraphs», Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97), doi:10.1109/SCCC.1997.637099 .

External links

• NIST Dictionary of Algorithms and Data Structures: topological sort
• Կաղապար:MathWorld