Force-directed graph drawing

Ուժ-հիմք կամ ուժ-ղեկավարել ալգորիթմներ ենք, որոնք ալգորիթմի այն դասի համար են, որոնք նկերելու գրաֆիկ 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)$ ,որտեղ իդեալական երկրությունը $\delta _{ij}$ յուրաքնչյուր առաձգականությանը համամասնական է տեսաբանական հեռավորությունից մինչև հանգույցները 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(n³), , որտեղ հանգույցների n թիվն մուտքագրման գրաֆիկն է. Սա պայմանավորված է թիվի կրկնությամբ ` գնահատվում է O(n),և բոլոր զույգ հանգույցների ամեն կրկնություն, պետք է այցելել եւ նրանց փոխադարձ բանող ուժերը հաշվարկվում են. Սա կապված է ֆիզիկայի N-մարմնի խնդիրի հետ. Սակայն, քանի որ զզվելի ուժերը տեղական բնույթի են, գրաֆիկը կարող է բաժանվել այնպես, որ միայն հարեւան vertices hama8vwum. Ընդհանուր տեխնիկան օգտագործվում է ալգորիթմների դասավորությունը որոշելու համար, մեծ գրաֆիկներն ներառում են բարձր ծավալային ներկառուցում,^[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) բազմակրկնություն տեխնիկայով.Cite error: The <ref> tag has too many names (see the help page).

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

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); Unknown parameter |վերջին= ignored (help)
^ de Leeuw, J. (1988)
^ Harel, D., Koren Y. (2002)
^ Kamada, T., Kawai, S. (1989)
^ Fruchterman, T. M. J., & Reingold, E. M. (1991)

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

. ISBN 978-0133016154. {{cite book}}: Missing or empty |title= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |անվանումը= ignored (help); Unknown parameter |առաջինը= ignored (help); Unknown parameter |հրապարակիչ= ignored (help); Unknown parameter |վերջինը= ignored (help); Unknown parameter |տարի= ignored (help)
{{cite journal}}: Empty citation (help)
. doi:10.1002/spe.4380211102 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.8444. {{cite journal}}: Cite journal requires |journal= (help); Missing or empty |title= (help); Unknown parameter |= ignored (help); Unknown parameter |ամսագիր= ignored (help); Unknown parameter |առաջին1= ignored (help); Unknown parameter |առաջին2= ignored (help); Unknown parameter |էջեր= ignored (help); Unknown parameter |հեղինակ 2-link= ignored (help); Unknown parameter |հրապարակիչ= ignored (help); Unknown parameter |շավալներ= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |վերջին1= ignored (help); Unknown parameter |վերջին2= ignored (help); Unknown parameter |տարի= ignored (help)
. ISBN 3-540-00158-1 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5390. {{cite conference}}: Missing or empty |title= (help); Unknown parameter |առաջին1= ignored (help); Unknown parameter |առաջին2= ignored (help); Unknown parameter |գրքի հեղինակ= ignored (help); Unknown parameter |էջերը= ignored (help); Unknown parameter |հեղինակ1-link= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |վերջին1= ignored (help); Unknown parameter |վերջին2= ignored (help); Unknown parameter |տարի= ignored (help)
. doi:10.1016/0020-0190(89)90102-6. {{cite journal}}: Cite journal requires |journal= (help); Missing or empty |title= (help); Unknown parameter |= ignored (help); Unknown parameter |ամսագիր= ignored (help); Unknown parameter |առաջին1= ignored (help); Unknown parameter |առաջին2= ignored (help); Unknown parameter |էջեր= ignored (help); Unknown parameter |ծավալներ= ignored (help); Unknown parameter |հրապարակիչ= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |վերջին1= ignored (help); Unknown parameter |վերջին2= ignored (help); Unknown parameter |տարի= ignored (help)
. doi:10.1007/3-540-44969-8. ISBN 978-3540420620. {{cite book}}: Missing or empty |title= (help); Unknown parameter |խմբագիր1-առաջին= ignored (help); Unknown parameter |խմբագիր1-վերջին= ignored (help); Unknown parameter |խմբագիր2-առաջին= ignored (help); Unknown parameter |խմբագիր2-վերջին= ignored (help); Unknown parameter |հրապարակիչ= ignored (help); Unknown parameter |սկիզբ= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |տարի= ignored (help)
. doi:10.1007/BF01897162. {{cite journal}}: Cite journal requires |journal= (help); Missing or empty |title= (help); Unknown parameter |= ignored (help); Unknown parameter |ամսագր= ignored (help); Unknown parameter |առաջին= ignored (help); Unknown parameter |էջեր= ignored (help); Unknown parameter |ծավալներ= ignored (help); Unknown parameter |հրապարակիչ= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |վերջին= ignored (help); Unknown parameter |տարի= ignored (help)
. ISBN 3-540-41554-8 http://www.cs.ucd.ie/staff/aquigley/home/downloads/aq-gd2000.pdf. {{cite conference}}: Missing or empty |title= (help); Unknown parameter |առաջին1= ignored (help); Unknown parameter |առաջին2= ignored (help); Unknown parameter |գրքի վերնագիր= ignored (help); Unknown parameter |էջեր= ignored (help); Unknown parameter |հեղինակ2-link= ignored (help); Unknown parameter |վերնագիր= ignored (help); Unknown parameter |վերջին1= ignored (help); Unknown parameter |վերջին2= ignored (help); Unknown parameter |տարի= ignored (help)

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

[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); Unknown parameter |վերջին= ignored (help)

[2] Leeuw, J. (1988)

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

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

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

[1]

[2]

[3]

[4]

[5]