User:AnnGabrieli

Force-based ' կամ force-directed-ը ալգորիթմներ են ալգորիթմներ -ի դասի համար նկարելու գրաֆիկներ գեղագիտական, հաճելի ձեւով. Նրանց նպատակը հանգույցների տեղն է մի գրաֆիկի երկու ծավալային կամ եռաչափ տարածության մեջ, այնպես որ բոլոր եզրերը ավելի կամ պակաս հավասար երկարությամբ լինեն, եւ կան նաեւ մի քանի հատող եզրեր, որոնք հնարավոր են .

Գաղափարը ծագել է 1980-ականների գարնանը- Eades և Kamada-Kawai անձանց մոդելով; force-directed տերմինը ծագել է Fruchterman & Reingold-ի 1990 Համալսարանում Illinois տեղնիկական հաշվետվությունից(UIUCDCS-R-90-1609).

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

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

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

Մինչ գրաֆիկը նկարելը բարդ խնդիր է, 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(n³), , որտեղ հանգույցների n թիվն մուտքագրման գրաֆիկն է. Սա պայմանավորված է թիվի կրկնությամբ ` գնահատվում է O(n),և բոլոր զույգ հանգույցների ամեն կրկնություն, պետք է այցելել եւ նրանց փոխադարձ բանող ուժերը հաշվարկվում են. Սա կապված է ֆիզիկայի N-մարմնի խնդիրի հետ. Սակայն, քանի որ զզվելի ուժերը տեղական բնույթի են, գրաֆիկը կարող է բաժանվել այնպես, որ միայն հարեւան vertices համարվում. Ընդհանուր տեխնիկան օգտագործվում է ալգորիթմների դասավորությունը որոշելու համար, մեծ գրաֆիկներն ներառում են բարձր ծավալային ներկառուցում,^[3] գծագրական տրոհված շերտի և այլ մեթոդների հետ կապված N- մարմին մոդելավորում. Օրինակ, Barnes–Hut simulation-հիմնված է FADE մեթոդի վրա Cite error: The <ref> tag has too many names (see the help page). կարող է բարելավել անընդմեջ ժամանակի n*log(n) յուրաքանչյուր բազմակրկնություն. Որպես ուղեցույց, մի քանի վայրկյանում կարելի է ակնկալել առավելագույնը 1,000 հանգույցների ստանդարտ n հետ ² տեխնիկայի բազմակրկնություն, և 100,000 n*log(n) բազմակրկնություն տեխնիկայով. ^[4]

Վատ տեղական minima: Շատ հեշտ է տեսնել, որ force-directed ալգորիթմները արտադրել են գրաֆիկ նվազագույն էներգետիկայով, մասնավորապես մեկում, որի ընդհանուր էներգիան միայն տեղական նվազագույնն է. Տեղական նվազագույն կարող է լինել, շատ դեպքերում, ավելի վատ, քան համաշխարհային նվազագույնը, որը թարգմանվել է ավելի ցածր որակի վիճակահանությամբ. Շատ ալգորիթմներ, հատկապես այն պայմանագրերը , որոնք թույլ են տալիս միայն down-hill vertices-ի շարժում, վերջնական արդյունքը կարող է մեծապես ազդել է մեկնարկային դիրքով, որ շատ դեպքերում պատահականորեն գեներացվել է. Վատ տեղական minima-յի խնդիրը դառնում է ավելի կարեւոր, քան vertices գրաֆիկը մեծանում է. Տարբեր ալգորիթմների համակցված կիրառումը օգտակար է լուծել այս խնդիրը. Օրինակ, օգտագործելով Kamada-Kawai ալգորիթ ը^[5] արագ առաջացնում է ողջամիտ նախնական դասավորություն, ապա Fruchterman-Reingold ալգորիթմը ^[6] բարելավելու տեղաբաշխում հարեւան հանգույցների.

Կեղծ կոդը

Յուրաքանչյուր առանցք ունի 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 է և հետախուզական հարթակ բոլոր տեսակի ցանցերի եւ բարդ համակարգերի, դինամիկ եւ հիերարխիկ գրաֆիկներ.

References

^ http://aphrodite.bio.utk.edu/phytree/. {{cite web}}: Missing or empty |title= (help); Unknown parameter |�� = ignored (help); Unknown parameter |��= ignored (help); Unknown parameter |��= ignored (help)
^ de Leeuw, J. (1988)
^ Harel, D., Koren Y. (2002)
^ Cite error: The named reference quigley+eades was invoked but never defined (see the help page).
^ Kamada, T., Kawai, S. (1989)
^ Fruchterman, T. M. J., & Reingold, E. M. (1991)

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

di Battista, Giuseppe (1999). Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall. ISBN 978-0133016154. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
Eades, Peter (1984). "A Heuristic for Graph Drawing". Congressus Numerantium. 42 (11): 149–160.
Fruchterman, Thomas M. J.; Reingold, Edward M. (1991). "Graph Drawing by Force-Directed Placement". Software – Practice & Experience. 21 (11). Wiley: 1129–1164. CiteSeerX 10.1.1.13.8444. doi:10.1002/spe.4380211102.
Harel, David; Koren, Yehuda (2002). "Graph Drawing by High-Dimensional Embedding". Proceedings of the 9th International Symposium on Graph Drawing. pp. 207–219. CiteSeerX 10.1.1.20.5390. ISBN 3-540-00158-1.
Kamada, Tomihisa; Kawai, Satoru (1989). "An algorithm for drawing general undirected graphs". Information Processing Letters. 31 (1). Elsevier: 7–15. doi:10.1016/0020-0190(89)90102-6.
Kaufmann, Michael; Wagner, Dorothea, eds. (2001). Drawing graphs: methods and models. Lecture Notes in Computer Science 2025. Vol. 2025. Springer. doi:10.1007/3-540-44969-8. ISBN 978-3540420620.
de Leeuw, Jan (1988). "Convergence of the majorization method for multidimensional scaling". Journal of Classification. 5 (2). Springer: 163–180. doi:10.1007/BF01897162.
Quigley, Aaron; Eades, Peter (2001). "FADE: Graph Drawing, Clustering, and Visual Abstraction" (PDF). Proceedings of the 8th International Symposium on Graph Drawing. pp. 197–210. ISBN 3-540-41554-8.

Արտաքին հղումներ

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

[1] ttp://aphrodite.bio.utk.edu/phytree/. {{cite web}}: Missing or empty |title= (help); Unknown parameter |�� = ignored (help); Unknown parameter |��= ignored (help); Unknown parameter |��= ignored (help)

[2] Leeuw, J. (1988)

[3] Harel, D., Koren Y. (2002)

[quigley+eades-4] Cite error: The named reference quigley+eades was invoked but never defined (see the help page).

[5] Kamada, T., Kawai, S. (1989)

[6] Fruchterman, T. M. J., & Reingold, E. M. (1991)

[1]

[2]

[3]

[4]

[5]

[6]