Մասնակից:AnnGabrieli/ավազարկղ
Սա AnnGabrieli մասնակցի սևագրության էջն է՝ «ավազարկղը», և մասնակցի էջի ենթաէջերից մեկն է։ Այն ծառայում է որպես սևագիր և փորձարկումների վայր։ Սա հանրագիտարանային հոդված չէ։ Ձեր անձնական ավազարկղը ստեղծելու համար սեղմեք այստեղ։ Այլ ավազարկղեր՝ Ընդհանուր ավազարկղ |
Ուժ-հիմք կամ ուժ-ղեկավարել ալգորիթմներ ենք, որոնք ալգորիթմի այն դասի համար են, որոնք նկերելու գրաֆիկ 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 parameter in
<ref>
tag կարող է բարելավել անընդմեջ ժամանակի n*log(n) յուրաքանչյուր բազմակրկնություն. Որպես ուղեցույց, մի քանի վայրկյանում կարելի է ակնկալել առավելագույնը 1,000 հանգույցների ստանդարտ n հետ2 տեխնիկայի բազմակրկնություն, և 100,000 n*log(n) բազմակրկնություն տեխնիկայով.Քաղվածելու սխալ՝ Invalid parameter in<ref>
tag
- Վատ տեղական 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=
(օգնություն); Unknown parameter|առաջին=
ignored (օգնություն); Unknown parameter|մուևքի անուն=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին=
ignored (օգնություն) - ↑ 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=
(օգնություն); Unknown parameter|coauthors=
ignored (|author=
suggested) (օգնություն); Unknown parameter|անվանումը=
ignored (օգնություն); Unknown parameter|առաջինը=
ignored (օգնություն); Unknown parameter|հրապարակիչ=
ignored (օգնություն); Unknown parameter|վերջինը=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) -
{{cite journal}}
: Empty citation (օգնություն) - . doi:10.1002/spe.4380211102 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.8444.
{{cite journal}}
: Cite journal requires|journal=
(օգնություն); Missing or empty|title=
(օգնություն); Unknown parameter|=
ignored (օգնություն); Unknown parameter|ամսագիր=
ignored (օգնություն); Unknown parameter|առաջին1=
ignored (օգնություն); Unknown parameter|առաջին2=
ignored (օգնություն); Unknown parameter|էջեր=
ignored (օգնություն); Unknown parameter|հեղինակ 2-link=
ignored (օգնություն); Unknown parameter|հրապարակիչ=
ignored (օգնություն); Unknown parameter|շավալներ=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին1=
ignored (օգնություն); Unknown parameter|վերջին2=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) - . ISBN 3-540-00158-1 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5390.
{{cite conference}}
: Missing or empty|title=
(օգնություն); Unknown parameter|առաջին1=
ignored (օգնություն); Unknown parameter|առաջին2=
ignored (օգնություն); Unknown parameter|գրքի հեղինակ=
ignored (օգնություն); Unknown parameter|էջերը=
ignored (օգնություն); Unknown parameter|հեղինակ1-link=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին1=
ignored (օգնություն); Unknown parameter|վերջին2=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) - . doi:10.1016/0020-0190(89)90102-6.
{{cite journal}}
: Cite journal requires|journal=
(օգնություն); Missing or empty|title=
(օգնություն); Unknown parameter|=
ignored (օգնություն); Unknown parameter|ամսագիր=
ignored (օգնություն); Unknown parameter|առաջին1=
ignored (օգնություն); Unknown parameter|առաջին2=
ignored (օգնություն); Unknown parameter|էջեր=
ignored (օգնություն); Unknown parameter|ծավալներ=
ignored (օգնություն); Unknown parameter|հրապարակիչ=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին1=
ignored (օգնություն); Unknown parameter|վերջին2=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) - . doi:10.1007/3-540-44969-8. ISBN 978-3540420620.
{{cite book}}
: Missing or empty|title=
(օգնություն); Unknown parameter|խմբագիր1-առաջին=
ignored (օգնություն); Unknown parameter|խմբագիր1-վերջին=
ignored (օգնություն); Unknown parameter|խմբագիր2-առաջին=
ignored (օգնություն); Unknown parameter|խմբագիր2-վերջին=
ignored (օգնություն); Unknown parameter|հրապարակիչ=
ignored (օգնություն); Unknown parameter|սկիզբ=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) - . doi:10.1007/BF01897162.
{{cite journal}}
: Cite journal requires|journal=
(օգնություն); Missing or empty|title=
(օգնություն); Unknown parameter|=
ignored (օգնություն); Unknown parameter|ամսագր=
ignored (օգնություն); Unknown parameter|առաջին=
ignored (օգնություն); Unknown parameter|էջեր=
ignored (օգնություն); Unknown parameter|ծավալներ=
ignored (օգնություն); Unknown parameter|հրապարակիչ=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն) - (PDF). ISBN 3-540-41554-8 http://www.cs.ucd.ie/staff/aquigley/home/downloads/aq-gd2000.pdf.
{{cite conference}}
: Missing or empty|title=
(օգնություն); Unknown parameter|առաջին1=
ignored (օգնություն); Unknown parameter|առաջին2=
ignored (օգնություն); Unknown parameter|գրքի վերնագիր=
ignored (օգնություն); Unknown parameter|էջեր=
ignored (օգնություն); Unknown parameter|հեղինակ2-link=
ignored (օգնություն); Unknown parameter|վերնագիր=
ignored (օգնություն); Unknown parameter|վերջին1=
ignored (օգնություն); Unknown parameter|վերջին2=
ignored (օգնություն); Unknown parameter|տարի=
ignored (օգնություն)
Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]
- aiSee's force-directed layout
- Video of Spring Algorithm
- Live visualisation in flash + source code and description
- Short explanation of the Kamada-Kawai spring-based graph layout algorithm featuring a picture
- Short explanation of Fruchterman-Reingold algorithm. The algorithm implements a variable step width (“temperature”) to guarantee that the system reaches equilibrium state
- Daniel Tunkelang's dissertation (with source code and demonstration applet) on force-directed graph layout
- Hyperassociative Map Algorithm
- Implementation of a Force Directed Graph with C# including video demonstration
- Interactive and real-time force directed graphing algorithms used in an online database modeling tool
Category:Graph algorithms
Category:Graph drawing
Category:Articles with example pseudocode