Մասնակից:AnnGabrieli/Force-based algorithms (graph drawing)

Visualization of links between pages on a wiki using a force directed layout.

Ուժ-հիմք կամ ուժ-ղեկավարել ալգորիթմներ ենք, որոնք ալգորիթմի այն դասի համար են, որոնք նկերելու գրաֆիկ aesthetically հաճելի ճանապարհով. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible. Գաղափարը ծագել է 1980-ականների գարնանը- ներդրվել է Eades և Kamada-Kawai-ի մոդելը; force-directed տերմինը ծագել է Fruchterman & Reingold-ի 1990 Համալսարանում Illinois տեղնիկական հաշվետվությունից(UIUCDCS-R-90-1609).

Ուժով ուղղված ալգորթմները հասել են նրան, որ նշանակվում են ուժերի շրջանում փաթեթի եզրերին և փաթեթի հանգույցներին ;առավել պարզ եղանակ է ուժերը հատկացնելը , քանի որ եթե եզրերի աղբյուրներ է (տեսHooke- օրենքը) և հանգույցները էլեկտրական լիցքավերման մասնիկներով (տեսCoulomb-ի օրենքը).Ամբողջ ծրագիրը կեղծվել է, քանի որ եղել է ֆիզիկական համակրգ. Այն ուժերը, որոնք կիրառվում են հանգույցներում, մոտենում են միմյանց կամ հետագայում հրում իրար. Սա անընդհատ կրկնվում է, մինչև համակարգը գալիս հավասարակշռության վիճակի; այսինքն ., դրանց համեմատական դիրքրորշումները չեն փովելմի կրկնությունից հաջորդը. Այդ պահին գրաֆիկը ձևավորվում է. Հավասարակշռության վիճակի ֆիզիկական մեկնաբանությունները բերում են նրան, որ բոլոր ուժերը մեխանիկական հավասարակշռության են.

Այլընտրանքնաին մոդելը համարում է առաձգական ուժ յուրաքնչյուր զույգ հանույցների համար ,որտեղ իդեալական երկրությունը յուրաքնչյուր առաձգականությանը համամասնական է տեսաբանական հեռավորությունից մինչև հանգույցները i և j. Այս մոդելում,առանձին բանող ուժի անհրաժեշտություն չկա. Նշենք, որ նվազագույնի հասցնելով տարբերությունը (սովորաբար քառակուսու տարբերությունը) միչևeuclidean և հանգույցների միջև իդեալական հեռավորությունը համարժեք ե մի մետրի multidimensional scaling խնդրի. Stress majorization տալիս է շատ լավ վարք (այսինքն, monotonically համեմատ) և mathematically էլեգանտ ճանապարհն է նվազեցնելու այս տարբերությունները եւ, հետեւաբար, գտնել լավ դասավորություն գրաֆիկի համար.

force-directed գրաֆիկը կարող է ներգրավել ուժեր, որոնք մեխանիկական եւ էլեկտրական աղբյուրների արդյունք են; օրինակները ներառում են logarithmic-ի աղբյուրներ (ի տարբերություն գծային աղբյուրների),ինչպես gravitational ուժերի (որը համախառն կապված բաղադրիչներ, որոնք մենակ կապված գրաֆիկներ չեն), մագնիսական ոլորտները (այսպես, ստանալու համար լավ դասավորություն ուղղված գրաֆիկների համար), և էլեկտրական լիցքավորված զսպանակներ (խուսափելու համար համընկնումը կամ մոտ համընկնումը վերջնական խաղարկությանը). Այդ դեպքում,աղբյուր և լիցքավորված մասնիկների գրաֆիկները, եզրեր են հակված են միատեսակ երկարության (քանի որ առաձգական ուժեր են), եւ հանգույցները, որոնք կապված չեն եզրից հակված են հետագայում տարվելու (էլեկտրական արդյունքի պատճառով).

Մինչ գրաֆիկը նկարելը բարդ խնդիր է, force-directed ալգորթմները, լինելով ֆիզիկական սիմուլացիա, սովորաբար պահանջվում է հատուկ գիտելիքներ ոչ միայն գրաֆիկի տեսության , ինչպիսին է planarity.

Նաեւ հնարավոր է կիրառել մեխանիզմներ , որոնք որոնման համար ուղղակիորեն ավելի էներգետիկ minima, կամ փոխարենը համատեղ ֆիզիկական մոդելավորում. Նման մեխանիզմները, որոնք օրինակ, ընդհանուր գլոբալ օպտիմալացման մեթոդները, ներառում է կռվելու սիմուլյացիա և գենետիկ ալգորիթմը.

ԱռավելություններըԽմբագրել

Հետևյալ են force-directed ալգորիթմների կարեւորագույն առավելություններից:

  • Լավ որակի արդյունքներ: Գրաֆիկների միջին մեծության նվազագույնը (մինչեւ 50-100 vertices), իսկ ստացված արդյունքները սովորաբար շատ լավ արդյունքներ են հիմնված հետեւյալ պայմանների վրա: միասնական եզրի երկարությունը, միասնական vertex բաշխումը և ցուցադրման համաչափությունը. Այս վերջին չափանիշը մեկն է առավել կարեւորներից և դժվար է հասնել ցանկացած այլ տեսակի ալգորիթմի.
  • Ճկունություն: Force-directed ալգորիթմները կարող են հեշտությամբ հարմարվել եւ տարածված է կատարելու լրացուցիչ գեղագիտական չափանիշներ. Սա ստիպում է նրանց առավել բազմակողմանի գրաֆիկ նկարելու ալգորթմների դաս. Գոյության ընդարձակման օրինակները ներառում է նոր գրաֆիկներ, 3D գրաֆիկ նկարել[1], կլաստերի գրաֆիկինկարելը, լարված գրաֆիկի նկարելը, և դինամիկ գրաֆիկի նկարելը.
  • Ինտուիտիվ: Քանի որ դրանք հիմնված են ընդհանուր օբյեկտների ֆիզիկական անալոգների վրա, ինչպիսիք են աղբյուրները, ալգորիթմների պահվածքը համեմատաբար հեշտ է կանխատեսել եւ հասկանալ. Սա այն դեպքն չէ, այլ տեսակի գրաֆիկի ալգորիթմների հետ.
  • Պարզություն: Տիպիկ force-directed ալգորիթմները պարզ են և կարող է իրականացնել մի քանի տող կոդը. Այլ դասընթացների գրաֆիկ-նկարելու ալգորիթմները, ինչպես orthogonal դասավորություն, սովորաբար շատ ավելի զբաղված են.
  • Interactivity: Այս դասի ալգորիթմի մի այլ առավելությունը ինտերակտիվ առումով է. Կազմելով միջանկյալ փուլերի գրաֆիկը, օգտվողը կարող է հետեւել, թե ինչպես է զարգանում գրաֆիկը , տեսնել այն tangled քաոսի մի գեղեցիկ կազմաձեւումը. Որոշ ինտերակտիվ գրաֆիկի գործիքներից, օգտվողը կարող մեկ կամ մի քանի հանգույցներ դուրս քաշել իրենց հավասարակշռության վիճակից և հետեւելու նրանց հետ վերաբնակելու դիրքորոշումը. Սա ստիպում է նրանց նախընտրելի դինամիկ ընտրությունը և online գրաֆիկի համակարգերը.
  • Ուժեղ տեսական հիմքերի քանակը: Մինչ պարզ ad-hoc force-directed ալգորիթմները (օրինակ, կեղծ սույն հոդվածով) հաճախ հայտնվում են գրականությում եւ գործնականում (քանի որ դրանք համեմատաբար հեշտ է հասկանալ), եւ առավել հիմնավորված մոտեցումներ են սկսում ձեռք բերել. Վիճակագիրները լուծել են նմանատիպ խնդիրներ multidimensional scaling (MDS) սկսած 1930-ից, եւ ֆիզիկոսներ նույնպես ունեն նմանատիպ խնդիրների հետ աշխատելու երկար պատմություն n-body -Ֆորումում խնդիրները շատ հասուն մոտեցումներ կան. Որպես օրինակ, stress majorization մոտեցումը MDS կարող է կիրառվել գրաֆիկի խաղարկությանը ինչպես նկարագրված է վերը. Սա ապացուցվել է զուգամիտելով monotonically.[2] Monotonic կոնվերգենցիան, գույքը, որը ալգորիթմ կլինի յուրաքանչյուր բազմակրկնություն նվազեցնելով կամ արժեքն դիրքով, կարևոր է, քանի որ այն երաշխավորում է, որ այն դիրքով, ի վերջո հասնելու տեղական minimum-ի և դադարի. Խլացում ծրագրերը, ինչպիսիք են մեկ օգտագործվող pseudo-code գրանշանները `առաջացնում է ալգորիթմի դադարեցշում, բայց չի կարող երաշխավորել իսկական տեղական նվազագույնին հասելը.

ԹերություններըԽմբագրել

force-directed ալգորիթմների գլխավոր թերություններըներառում են հետևյալը:

  • High անընդմեջ ժամանակը: force-directed ալգորիթմներին բնորոշ է համարել ընդհանուր անընդմեջ ժամանակին համարժեք հաղորդագրություններ O(n3), , որտեղ հանգույցների n թիվն մուտքագրման գրաֆիկն է. Սա պայմանավորված է թիվի կրկնությամբ ` գնահատվում է O(n),և բոլոր զույգ հանգույցների ամեն կրկնություն, պետք է այցելել եւ նրանց փոխադարձ բանող ուժերը հաշվարկվում են. Սա կապված է ֆիզիկայի N-մարմնի խնդիրի հետ. Սակայն, քանի որ զզվելի ուժերը տեղական բնույթի են, գրաֆիկը կարող է բաժանվել այնպես, որ միայն հարեւան vertices hama8vwum. Ընդհանուր տեխնիկան օգտագործվում է ալգորիթմների դասավորությունը որոշելու համար, մեծ գրաֆիկներն ներառում են բարձր ծավալային ներկառուցում,[3] գծագրական տրոհված շերտի և այլ մեթոդների հետ կապված N- մարմին մոդելավորում. Օրինակ, Barnes–Hut simulation-հիմնված է FADE մեթոդի վրա Քաղվածելու սխալ՝ Invalid <ref> tag; invalid names, e.g. too many կարող է բարելավել անընդմեջ ժամանակի n*log(n) յուրաքանչյուր բազմակրկնություն. Որպես ուղեցույց, մի քանի վայրկյանում կարելի է ակնկալել առավելագույնը 1,000 հանգույցների ստանդարտ n հետ2 տեխնիկայի բազմակրկնություն, և 100,000 n*log(n) բազմակրկնություն տեխնիկայով.Քաղվածելու սխալ՝ Invalid <ref> tag; invalid names, e.g. too many
  • Վատ տեղական minima: Շատ հեշտ է տեսնել, որ force-directed ալգորիթմները արտադրել են գրաֆիկ նվազագույն էներգետիկայով, մասնավորապես մեկում, որի ընդհանուր էներգիան միայն տեղական նվազագույնն է. Տեղական նվազագույն կարող է լինել, շատ դեպքերում, ավելի վատ, քան համաշխարհային նվազագույնը, որը թարգմանվել է ավելի ցածր որակի վիճակահանությամբ. Շատ ալգորիթմներ, հատկապես այն պայմանագրերը , որոնք թույլ են տալիս միայն down-hill vertices-ի շարժում, վերջնական արդյունքը կարող է մեծապես ազդել է մեկնարկային դիրքով, որ շատ դեպքերում պատահականորեն գեներացվել է. Վատ տեղական minima-յի խնդիրը դառնում է ավելի կարեւոր, քան vertices գրաֆիկը մեծանում է. Տարբեր ալգորիթմների համակցված կիրառումը օգտակար է լուծել այս խնդիրը. Օրինակ, օգտագործելով Kamada-Kawai ալգորիթ ը[4] արագ առաջացնում է ողջամիտ նախնական դասավորություն, ապա Fruchterman-Reingold ալգորիթմը [5] բարելավելու տեղաբաշխում հարեւան հանգույցների.

Կեղծ կոդըԽմբագրել

Յուրաքանչյուր առանցք ունի x,y պաշտոնը և dx,dy արագություն և m զանգվածը. Սովորաբար կա անընդհատ առաձգականություն, և խլացում: 0 < damping < 1. Ուժը դեպի ու հեռու հանգույցների հաշվարկվում է ըստ Hooke-ի օրենքի և Coulomb-ի օրենքը կամ նման քննարկումը վերեւից. Օրինակ կարող է ընդլայնվել trivially ներառելով a z պաշտոնը 3D ներկայացուցչության համար.

 set up initial node velocities to (0,0)
 set up initial node positions randomly // make sure no 2 nodes are in exactly the same position
 loop
     total_kinetic_energy := 0 // running sum of total kinetic energy over all particles
     for each node
         net-force := (0, 0) // running sum of total force on this particular node
         
         for each other node
             net-force := net-force + Coulomb_repulsion( this_node, other_node )
         next node
         
         for each spring connected to this node
             net-force := net-force + Hooke_attraction( this_node, spring )
         next spring
         
         // without damping, it moves forever
         this_node.velocity := (this_node.velocity + timestep * net-force) * damping
         this_node.position := this_node.position + timestep * this_node.velocity
         total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2
     next node
 until total_kinetic_energy is less than some small number  // the simulation has stopped moving

Տես նաևԽմբագրել

  • Թուլիփ, ծրագիր, որը իրականցնում է force directed կառուցվածքի մասին (GEM, LGL, GRIP, FM³)
  • Cytoscape, ծրագրային ապահովման համար visualizing կենսաբանական ցանցեր. Բազային փաթեթը ներառում է force-directed դասավորություն որպես ներկառուցված մեթոդներ.
  • Gephi, որը ինտերակտիվ visualization է և հետախուզական հարթակ բոլոր տեսակի ցանցերի եւ բարդ համակարգերի, դինամիկ եւ հիերարխիկ գրաֆիկներ.

ԾանոթագրություններԽմբագրել

  1. http://aphrodite.bio.utk.edu/phytree/ 
  2. de Leeuw, J. (1988)
  3. Harel, D., Koren Y. (2002)
  4. Kamada, T., Kawai, S. (1989)
  5. Fruchterman, T. M. J., & Reingold, E. M. (1991)

Հետագա ընթերցումԽմբագրել

Արտաքին հղումներԽմբագրել


Category:Graph algorithms Category:Graph drawing Category:Articles with example pseudocode