This is an implementation of two Spring-embedder algorithms used for graph layout: Force-directed (Fruchterman - Reingold) and Local minimum energy (Kamada- Kawaii) in C language.
Generate matrix vertexes and edges:
make
.\MyForce
Draw graph:
cd drawgraph
qmake
make
.\release\drawgraph
ΠΠΎΠ½ΡΡΠΈΠ΅ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΡΠ½ΠΎΠ²Π½ΡΠΌ Π² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ², Π² ΡΠ°ΡΡΠ½ΠΎΡΡΠΈ Π² ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ². Π‘ΡΡΠ΅ΡΡΠ²ΡΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΉ Π³ΡΠ°ΡΠ°, Π² ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π³ΡΠ°ΡΠΎΠΌ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΠΏΠ°ΡΠ° β (V, E), Π³Π΄Π΅ V β ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°, Π° E β ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ. ΠΠ²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ v ΠΈ u ΠΎΠ±ΡΠ°Π·ΡΡΡ ΡΠ΅Π±ΡΠΎ Π³ΡΠ°ΡΠ°, Π΅ΡΠ»ΠΈ {v, u} β E. ΠΡΠ»ΠΈ {v, u} β E ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ {u, v} β E, ΡΠΎ Π³ΡΠ°Ρ ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΡΠΎ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ.
ΠΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π³ΡΠ°ΡΠ° ΠΈΠ»ΠΈ ΡΠ΅ΡΠ΅Π²ΠΎΠΉ Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΡ β ΡΡΠΎ Π³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ°. ΠΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π½Π΅ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΡΡΠ°ΡΡ Ρ ΡΠ°ΠΌΠΈΠΌ Π³ΡΠ°ΡΠΎΠΌ: ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈ ΡΠΎΠΌΡ ΠΆΠ΅ Π³ΡΠ°ΡΡ ΠΌΠΎΠ³ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ ΠΎΡΠ΅Π½Ρ ΡΠ°Π·Π½ΡΠ΅ ΡΠ°ΡΠΊΠ»Π°Π΄ΠΊΠΈ.
ΠΠ»Ρ Π²ΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π±ΡΠ»ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Π΅ΠΉ ΠΊΠ°ΡΠ΅ΡΡΠ²Π° Π² ΠΏΠΎΠΏΡΡΠΊΠ΅ Π½Π°ΠΉΡΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠ΅ ΡΡΠ΅Π΄ΡΡΠ²Π° ΠΎΡΠ΅Π½ΠΊΠΈ ΠΈΡ ΡΡΡΠ΅ΡΠΈΠΊΠΈ ΠΈ ΡΠ΄ΠΎΠ±ΡΡΠ²Π° ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ. Π Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΊ ΡΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²Ρ Π²ΡΠ±ΠΎΡΠΎΠΌ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠ°ΡΠΊΠ»Π°Π΄ΠΊΠΈ Π΄Π»Ρ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΡΠΎΠ³ΠΎ ΠΆΠ΅ Π³ΡΠ°ΡΠ°, Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ°ΡΠΊΠ»Π°Π΄ΠΊΠΈ ΠΏΡΡΠ°ΡΡΡΡ Π½Π°ΠΏΡΡΠΌΡΡ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΈ ΠΌΠ΅ΡΡ.
- ΠΠ΅Π½ΡΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΡΠ΅Π±Π΅Ρ: Π²ΡΡΠ°Π²Π½ΠΈΠ²Π°Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΠ΅Π±Π΅Ρ Π΄Π»Ρ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π³ΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΡΠ΅Π±Π΅Ρ Π΄Π΅Π»Π°Π΅Ρ Π³ΡΠ°ΡΠΈΠΊ Π±ΠΎΠ»Π΅Π΅ Π°ΠΊΠΊΡΡΠ°ΡΠ½ΡΠΌ ΠΈ ΠΌΠ΅Π½Π΅Π΅ Π·Π°ΠΏΡΡΠ°Π½Π½ΡΠΌ.
- ΠΠΈΠ½ΠΈΠΌΡΠΌ Π½Π°Π»ΠΎΠΆΠ΅Π½ΠΈΠΉ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΡΠ±Π΅Ρ.
- Π Π°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠ½ ΠΈ/ΠΈΠ»ΠΈ ΡΡΠ±Π΅Ρ ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎ.
- Π‘ΠΌΠ΅ΠΆΠ½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π±Π»ΠΈΠ·ΠΊΠΈ Π΄ΡΡΠ³ ΠΊ Π΄ΡΡΠ³Ρ, Π½Π΅ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Π΄Π°Π»Π΅ΠΊΠΈ.
- Π‘ΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° Π³ΡΡΠΏΠΏΠΈΡΡΡΡΡΡ Π² ΠΊΠ»Π°ΡΡΠ΅ΡΡ.
Π‘ΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° ΡΠ²Π»ΡΡΡΡΡ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎΠΌ ΠΌΠ½ΠΎΠ³ΠΈΡ ΡΠ΅ΡΠ΅ΠΉ, Π² ΠΊΠΎΡΠΎΡΡΡ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½Π°Ρ ΡΠ΅ΡΡ ΠΌΠΎΠΆΠ΅Ρ ΠΈΠΌΠ΅ΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ², ΡΠ°ΠΊ ΡΡΠΎ ΡΠ·Π»Ρ Π²Π½ΡΡΡΠΈ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° ΡΠ΅ΡΠ½ΠΎ ΡΠ²ΡΠ·Π°Π½Ρ. Π£Π·Π»Ρ Π² Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π°Ρ ΠΌΠΎΠ³ΡΡ ΠΏΠ΅ΡΠ΅ΠΊΡΡΠ²Π°ΡΡΡΡ.
Π’Π°ΠΊΠΆΠ΅ Π½Π°ΠΌ ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΡΠΈΡΠ»ΠΎΠ²Π°Ρ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊΠ°, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΎΠΏΠΈΡΡΠ²Π°Π΅Ρ Π²ΡΡΠ°ΠΆΠ΅Π½Π½ΠΎΡΡΡ ΡΡΡΡΠΊΡΡΡΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ² Π² Π΄Π°Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠ°Ρ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡΡ:
Π³Π΄Π΅ Ξ΄(Ci, Cj) β Π΄Π΅Π»ΡΡΠ°-ΡΡΠ½ΠΊΡΠΈΡ, ΡΠ°Π²Π½Π°Ρ Π΅Π΄ΠΈΠ½ΠΈΡΠ΅, Π΅ΡΠ»ΠΈ Ci = Cj ΠΈ Π½ΡΠ»Ρ ΠΈΠ½Π°ΡΠ΅.
ΠΠΎΠΏΡΡΠ°Π΅ΠΌΡΡ ΠΏΠΎΠ½ΡΡΡ, ΡΡΠΎ ΠΎΠ½Π° ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ. ΠΠΎΠ·ΡΠΌΡΠΌ Π΄Π²Π΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ»ΡΠ½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ i ΠΈ j ΠΠ΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΠΏΠΎΡΠ²Π»Π΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° ΠΌΠ΅ΠΆΠ΄Ρ Π½ΠΈΠΌΠΈ ΠΏΡΠΈ Π³Π΅Π½Π΅ΡΠ°ΡΠΈΠΈ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Ρ ΡΠ°ΠΊΠΈΠΌ ΠΆΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΡΠ±Π΅Ρ, ΠΊΠ°ΠΊ Ρ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°, ΡΠ°Π²Π½Π° didj/2m. Π Π΅Π°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΡΠ±Π΅Ρ Π² ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π΅ C Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½ΡΡΡΡΡ Ξ£i,j β C Ai,j.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ ΡΠ°Π²Π½Π° ΡΠ°Π·Π½ΠΎΡΡΠΈ ΠΌΠ΅ΠΆΠ΄Ρ Π΄ΠΎΠ»Π΅ΠΉ ΡΡΠ±Π΅Ρ Π²Π½ΡΡΡΠΈ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° ΠΏΡΠΈ Π΄Π°Π½Π½ΠΎΠΌ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ ΠΈ Π΄ΠΎΠ»Π΅ΠΉ ΡΡΠ±Π΅Ρ, Π΅ΡΠ»ΠΈ Π±Ρ ΠΎΠ½ΠΈ Π±ΡΠ»ΠΈ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎ ΡΠ³Π΅Π½Π΅ΡΠΈΡΠΎΠ²Π°Π½Ρ. ΠΠΎΡΡΠΎΠΌΡ ΠΎΠ½Π° ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°Π΅Ρ Π²ΡΡΠ°ΠΆΠ΅Π½Π½ΠΎΡΡΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ² (ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΉ Π³ΡΠ°Ρ ΡΡΡΡΠΊΡΡΡΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ² Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ). Π’Π°ΠΊΠΆΠ΅ ΡΡΠΎΠΈΡ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ ΡΠ°Π²Π½Π° 1 Π΄Π»Ρ ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΠΌΠ΅ΡΠ΅Π½Ρ Π² ΠΎΠ΄Π½ΠΎ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²ΠΎ ΠΈ ΡΠ°Π²Π½Π° Π½ΡΠ»Ρ Π΄Π»Ρ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΡ Π½Π° ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π°, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ ΡΠΎΠΏΠΎΡΡΠ°Π²Π»Π΅Π½ΠΎ ΠΏΠΎ ΠΎΡΠ΄Π΅Π»ΡΠ½ΠΎΠΌΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Ρ. ΠΠ»Ρ ΠΎΡΠΎΠ±ΠΎ Π½Π΅ΡΠ΄Π°ΡΠ½ΡΡ ΡΠ°Π·Π±ΠΈΠ΅Π½ΠΈΠΉ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΠΎΠΉ.
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠ°ΡΡ Π²Π΅ΡΡΠΈΠ½ ΡΠ²ΡΠ·Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΡΠΈΡΠ»ΠΈΡΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ, ΠΈΡ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠΉ. ΠΡΠ΄Π΅ΠΌ ΡΡΠΈΡΠ°ΡΡ, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°ΠΊΠΎΠΉ ΠΏΡΡΡ ΠΈΠΌΠ΅Π΅Ρ Π²Π΅Ρ, ΡΠ°Π²Π½ΡΠΉ 1/N, Π³Π΄Π΅ N β ΡΠΈΡΠ»ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΡ ΠΏΡΡΠ΅ΠΉ ΠΌΠ΅ΠΆΠ΄Ρ Π²ΡΠ±ΡΠ°Π½Π½ΠΎΠΉ ΠΏΠ°ΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½. ΠΡΠ»ΠΈ ΡΠ°ΠΊΠΈΠ΅ Π²Π΅ΡΠ° ΠΏΠΎΡΡΠΈΡΠ°ΡΡ Π΄Π»Ρ Π²ΡΠ΅Ρ ΠΏΠ°Ρ Π²Π΅ΡΡΠΈΠ½, ΡΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ΅Π±ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΠ°Π²ΠΈΡΡ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Edge betweenness β ΡΡΠΌΠΌΡ Π²Π΅ΡΠΎΠ² ΠΏΡΡΠ΅ΠΉ, ΠΏΡΠΎΡΠ΅Π΄ΡΠΈΡ ΡΠ΅ΡΠ΅Π· ΡΡΠΎ ΡΠ΅Π±ΡΠΎ.
ΠΠ»Ρ ΡΡΠ½ΠΎΡΡΠΈ ΠΏΡΠΈΠ²Π΅Π΄ΡΠΌ ΡΠ»Π΅Π΄ΡΡΡΡΡ ΠΈΠ»Π»ΡΡΡΡΠ°ΡΠΈΡ:
ΠΡΠ°Ρ, Π΄Π»Ρ ΡΠ΅Π±ΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΠΎΡΡΠΈΡΠ°Π½Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Edge betweenness Π Π΄Π°Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ Ρ ΠΎΡΠ΅ΡΡΡ Π²ΡΠ΄Π΅Π»ΠΈΡΡ Π΄Π²Π° ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π°: Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ 1-5 ΠΈ 6-10. ΠΡΠ°Π½ΠΈΡΠ° ΠΆΠ΅ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΡ ΠΎΠ΄ΠΈΡΡ ΡΠ΅ΡΠ΅Π· ΡΠ΅Π±ΡΠΎ, ΠΈΠΌΠ΅ΡΡΠ΅Π΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ Π²Π΅Ρ, 25. ΠΠ° ΡΡΠΎΠΉ ΠΈΠ΄Π΅Π΅ ΠΈ ΠΎΡΠ½ΠΎΠ²ΡΠ²Π°Π΅ΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ: ΠΏΠΎΡΡΠ°ΠΏΠ½ΠΎ ΡΠ΄Π°Π»ΡΠ΅ΠΌ ΡΠ΅Π±ΡΠ° Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ Π²Π΅ΡΠΎΠΌ, Π° ΠΎΡΡΠ°Π²ΡΠΈΠ΅ΡΡ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ ΠΎΠ±ΡΡΠ²Π»ΡΠ΅ΠΌ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π°ΠΌΠΈ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΡΠΎΠΈΡ ΠΈΠ· 6 ΡΡΠ°ΠΏΠΎΠ²:
- ΠΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ Π²Π΅ΡΠ°
- Π£Π΄Π°Π»ΠΈΡΡ ΡΠ΅Π±ΡΠΎ Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ Π²Π΅ΡΠΎΠΌ
- ΠΠ΅ΡΠ΅ΡΡΠΈΡΠ°ΡΡ Π²Π΅ΡΠ° Π΄Π»Ρ ΡΠ΅Π±ΡΡ
- Π‘ΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π°ΠΌΠΈ ΡΡΠΈΡΠ°ΡΡΡΡ Π²ΡΠ΅ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ
- ΠΠΎΡΡΠΈΡΠ°ΡΡ ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π» ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΠΈ
- ΠΠΎΠ²ΡΠΎΡΡΡΡ Ρ ΡΠ°Π³ΠΈ 2-6, ΠΏΠΎΠΊΠ° Π΅ΡΡΡ ΡΡΠ±ΡΠ°
ΠΠ»ΡΡΡΡΠ°ΡΠΈΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Multilevel: Π΄Π²Π° ΠΏΡΠΎΡ ΠΎΠ΄Π°, Π΄Π»Ρ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ ΠΎΠ±Π° ΡΡΠ°ΠΏΠ°
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΎΡΠ½ΠΎΠ²Π°Π½ Π½Π° ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΠΈ. ΠΠ°ΠΊ ΠΈ Π² ΠΌΠ½ΠΎΠ³ΠΈΡ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠΈΡ ΠΌΠ΅ΡΠΎΠ΄Π°Ρ , ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ ΡΠ½Π°ΡΠ°Π»Π° ΡΡΠ°Π²ΠΈΡΡΡ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΏΠΎ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Ρ. ΠΠ°Π»Π΅Π΅ ΡΠ΅ΡΠ΅Π΄ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΡΠ°ΠΏΡ:
- ΠΠ΅ΡΠ²ΡΠΉ ΡΡΠ°ΠΏ
- ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠ΅ΡΠ΅Π±ΠΈΡΠ°Π΅ΠΌ Π΅Ρ ΡΠΎΡΠ΅Π΄Π΅ΠΉ
- ΠΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅ΠΌ Π² ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²ΠΎ ΡΠΎΡΠ΅Π΄Π°, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ ΡΠ²Π΅Π»ΠΈΡΠΈΠ²Π°Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ
- ΠΡΠ»ΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ Π² Π»ΡΠ±ΠΎΠ΅ Π΄ΡΡΠ³ΠΎΠ΅ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²ΠΎ ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΌΠ΅Π½ΡΡΠΈΡΡ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ, ΡΠΎ Π²Π΅ΡΡΠΈΠ½Π° ΠΎΡΡΠ°ΡΡΡΡ Π² ΡΠ²ΠΎΡΠΌ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π΅
- ΠΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΠΏΠΎΠ²ΡΠΎΡΡΠ΅ΠΌ, ΠΏΠΎΠΊΠ° ΠΊΠ°ΠΊΠΎΠ΅-Π»ΠΈΠ±ΠΎ ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ
- ΠΡΠΎΡΠΎΠΉ ΡΡΠ°ΠΏ
- Π‘ΠΎΠ·Π΄Π°ΡΡ ΠΌΠ΅ΡΠ°Π³ΡΠ°Ρ ΠΈΠ· ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²-Π²Π΅ΡΡΠΈΠ½. ΠΡΠΈ ΡΡΠΎΠΌ ΡΡΠ±ΡΠ° Π±ΡΠ΄ΡΡ ΠΈΠΌΠ΅ΡΡ Π²Π΅ΡΠ°, ΡΠ°Π²Π½ΡΠ΅ ΡΡΠΌΠΌΠ΅ Π²Π΅ΡΠΎΠ² Π²ΡΠ΅Ρ ΡΡΠ±Π΅Ρ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° Π² Π΄ΡΡΠ³ΠΎΠ΅ ΠΈΠ»ΠΈ Π²Π½ΡΡΡΠΈ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Π° (Ρ.Π΅. Π±ΡΠ΄Π΅Ρ Π²Π·Π²Π΅ΡΠ΅Π½Π½Π°Ρ ΠΏΠ΅ΡΠ»Ρ)
- ΠΠ΅ΡΠ΅ΠΉΡΠΈ Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ ΡΡΠ°ΠΏ Π΄Π»Ρ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΡΠ΅ΠΊΡΠ°ΡΠ°Π΅Ρ ΡΠ°Π±ΠΎΡΡ, ΠΊΠΎΠ³Π΄Π° Π½Π° ΠΎΠ±ΠΎΠΈΡ ΡΡΠ°ΠΏΠ°Ρ ΠΌΠΎΠ΄ΡΠ»ΡΡΠ½ΠΎΡΡΡ Π½Π΅ ΠΏΠΎΠ΄Π΄Π°ΡΡΡΡ ΡΠ»ΡΡΡΠ΅Π½ΠΈΡ. ΠΡΠ΅ ΠΈΡΡ ΠΎΠ΄Π½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΊΠΎΡΠΎΡΡΠ΅ Π²Ρ ΠΎΠ΄ΡΡ Π² ΡΠΈΠ½Π°Π»ΡΠ½ΡΡ ΠΌΠ΅ΡΠ°Π²Π΅ΡΡΠΈΠ½Ρ, ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°Ρ ΠΎΠ΄Π½ΠΎΠΌΡ ΡΠΎΠΎΠ±ΡΠ΅ΡΡΠ²Ρ. ΠΠ΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π·Π°ΠΌΠ΅ΡΠ°Π½ΠΈΠΉ:
- ΠΠ° ΠΏΠ΅ΡΠ²ΠΎΠΌ ΡΡΠ°ΠΏΠ΅ Π²Π΅ΡΡΠΈΠ½Π° ΠΌΠΎΠΆΠ΅Ρ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠ°Π·
- ΠΠΎΡΡΠ΄ΠΎΠΊ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ° Π½Π΅ ΡΠΈΠ»ΡΠ½ΠΎ Π²Π»ΠΈΡΠ΅Ρ Π½Π° ΡΠΎΡΠ½ΠΎΡΡΡ, ΠΎΠ΄Π½Π°ΠΊΠΎ ΠΌΠΎΠΆΠ΅Ρ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ Π²Π»ΠΈΡΡΡ Π½Π° Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°
- ΠΠ° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ 3-4 ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ
Π ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΎΠ±ΡΠΈΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ² ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΡΡ ΠΎΠ±Π»Π°ΡΡΡ Π΄Π»Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠΎΠ². ΠΠ½ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈΠ»ΠΈ ΠΎΠ±ΠΎΠΈΠΌ ΠΈΠ· Π΄Π²ΡΡ Π²Π°ΠΆΠ½ΡΡ ΡΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΠΉ: (1) Ρ ΠΎΡΠΎΡΠΎ ΡΠΈΡΠΎΠ²Π°ΡΡ Π³ΡΠ°ΡΠΈΠΊ ΠΈ (2) ΡΠΈΡΠΎΠ²Π°ΡΡ Π΅Π³ΠΎ Π±ΡΡΡΡΠΎ. Π§ΡΠΎΠ±Ρ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΠΏΠ΅ΡΠ²ΠΎΠ΅ ΡΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΠ΅, Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΌΠΎΠ³ΡΡ ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΠΌ ΡΠΈΡΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΠΌ ΡΠ²ΡΠΈΡΡΠΈΠΊΠ°ΠΌ. Π§ΡΠΎΠ±Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ Π²ΡΠΎΡΠΎΠΌΡ, Π°Π»Π³ΠΎΡΠΈΡΠΌΡ, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, Π΄ΠΎΠ»ΠΆΠ½Ρ ΠΌΠ°ΡΡΡΠ°Π±ΠΈΡΠΎΠ²Π°ΡΡΡΡ, ΡΡΠΎΠ±Ρ ΠΈΠΌΠ΅ΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΠΎΠ±ΡΠ°Π±Π°ΡΡΠ²Π°ΡΡ Π±ΠΎΠ»ΡΡΠΎΠΉ Π³ΡΠ°Ρ.
Π ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΡΠ»Π΅Π΄ΠΈΡΡ Π΄ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π‘ΠΠΠ‘, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ³ΠΎ ΡΠΈΠ»ΠΎΠ²ΡΠΌ ΡΠ°Π·ΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ, ΡΠ΅Π»ΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΡ ΡΡ Π΅ΠΌΡ ΡΡ Π΅ΠΌΡ Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠΉ Π»ΠΈΠ½ΠΈΠΉ. Eades (1984) Π²Π²Π΅Π» ΠΌΠΎΠ΄Π΅Π»Ρ Spring-Embedder, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π² Π³ΡΠ°ΡΠ΅ Π·Π°ΠΌΠ΅Π½ΡΡΡΡΡ ΡΡΠ°Π»ΡΠ½ΡΠΌΠΈ ΠΊΠΎΠ»ΡΡΠ°ΠΌΠΈ, Π° ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π·Π°ΠΌΠ΅Π½ΡΠ΅ΡΡΡ ΠΏΡΡΠΆΠΈΠ½ΠΎΠΉ. ΠΡΡΠΆΠΈΠ½Π½Π°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° Π·Π°ΠΏΡΡΠΊΠ°Π΅ΡΡΡ ΡΠΎ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌ Π½Π°ΡΠ°Π»ΡΠ½ΡΠΌ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ, ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°ΡΡΡΡ ΠΏΠΎΠ΄ Π΄Π΅ΠΉΡΡΠ²ΠΈΠ΅ΠΌ ΠΏΡΡΠΆΠΈΠ½Π½ΡΡ ΡΠΈΠ». ΠΠΏΡΠΈΠΌΠ°Π»ΡΠ½Π°Ρ ΠΊΠΎΠΌΠΏΠΎΠ½ΠΎΠ²ΠΊΠ° Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ Π·Π° ΡΡΠ΅Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎ ΡΠ½Π΅ΡΠ³ΠΈΡ ΡΠΈΡΡΠ΅ΠΌΡ ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ.
ΠΡΠ° ΠΈΠ½ΡΡΠΈΡΠΈΠ²Π½Π°Ρ ΠΈΠ΄Π΅Ρ Π²Π΄ΠΎΡ Π½ΠΎΠ²ΠΈΠ»Π° ΠΌΠ½ΠΎΠ³ΠΈΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΠ°Π±ΠΎΡΡ ΠΏΠΎ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ², ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ ΠΠ°ΠΌΠ°Π΄Π° ΠΈ ΠΠ°Π²Π°ΠΈ (1989), Π€ΡΡΡ ΡΠ΅ΡΠΌΠ°Π½ ΠΈ Π Π΅ΠΉΠ½Π³ΠΎΠ»ΡΠ΄ (1991). ΠΠ΄Π΅ΡΡ ΠΈΡ ΡΠ°Π±ΠΎΡΡ ΠΎΠ±ΠΎΠ±ΡΠ°ΡΡΡΡ ΠΈ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΠΈΠ»Π»ΡΡΡΡΠΈΡΠΎΠ²Π°ΡΡ Π²Π»ΠΈΡΠ½ΠΈΠ΅ ΠΌΠΎΠ΄Π΅Π»ΠΈ Spring-Embedder Π½Π° ΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π³ΡΠ°ΡΠΈΠΊΠΎΠ² ΠΈ Π²ΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. ΠΠ΄Π΅ΠΈ, Π²Π΄ΠΎΡ Π½ΠΎΠ²Π»Π΅Π½Π½ΡΠ΅ ΡΡΠΈΠΌΠΈ ΡΠ°Π±ΠΎΡΠ°ΠΌΠΈ, Π±Π΅ΡΡΠ΅Π½Π½Ρ Π΄Π»Ρ Π²ΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ Π² ΡΠ΅Π»ΠΎΠΌ.
ΠΠΎΠ΄Π΅Π»Ρ spring-embedder Π±ΡΠ»Π° ΠΏΠ΅ΡΠ²ΠΎΠ½Π°ΡΠ°Π»ΡΠ½ΠΎ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½Π° Eades (1984) ΠΈ Π² Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· ΡΠ°ΠΌΡΡ ΠΏΠΎΠΏΡΠ»ΡΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π΄Π»Ρ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ² Ρ ΠΏΡΡΠΌΠΎΠ»ΠΈΠ½Π΅ΠΉΠ½ΡΠΌΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ, ΡΠΈΡΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠ³ΠΎ Π² ΡΠΈΡΡΠ΅ΠΌΠ°Ρ Π²ΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ Π·Π° Π΅Π³ΠΎ ΠΏΡΠΎΡΡΠΎΡΡ ΠΈ ΠΈΠ½ΡΡΠΈΡΠΈΠ²Π½ΠΎ ΠΏΠΎΠ½ΡΡΠ½ΡΡ ΠΏΡΠΈΠ²Π»Π΅ΠΊΠ°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΄Π΅ΡΠ° ΡΠ»Π΅Π΄ΡΠ΅Ρ Π΄Π²ΡΠΌ ΡΡΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ ΠΊΡΠΈΡΠ΅ΡΠΈΡΠΌ: ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½Π°Ρ Π΄Π»ΠΈΠ½Π° ΡΠ΅Π±Π΅Ρ ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Π°Ρ ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΡ. Π ΠΌΠΎΠ΄Π΅Π»ΠΈ Spring-Embedder Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡΡΡ Π½Π°Π±ΠΎΡΠΎΠΌ ΠΊΠΎΠ»Π΅Ρ, ΠΈ ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΏΠ°ΡΠ° ΠΊΠΎΠ»Π΅Ρ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π° ΠΏΡΡΠΆΠΈΠ½ΠΎΠΉ. ΠΡΡΠΆΠΈΠ½Π° ΡΠ²ΡΠ·Π°Π½Π° Ρ Π΄Π²ΡΠΌΡ Π²ΠΈΠ΄Π°ΠΌΠΈ ΡΠΈΠ»: ΡΠΈΠ»Π°ΠΌΠΈ ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ ΠΈ ΡΠΈΠ»Π°ΠΌΠΈ ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ, Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΈ ΡΠ²ΠΎΠΉΡΡΠ² ΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π°.
Π ΠΈΡΡΠ½ΠΎΠΊ Π³ΡΠ°ΡΠΈΠΊΠ° ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ°Π΅ΡΡΡ ΠΊ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ ΠΏΠΎ ΠΌΠ΅ΡΠ΅ ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΡ ΡΠ½Π΅ΡΠ³ΠΈΠΈ ΠΏΡΡΠΆΠΈΠ½Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ. Π ΡΠ·Π»Π°ΠΌ, ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΠΌ ΠΏΡΡΠΆΠΈΠ½ΠΎΠΉ, ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½Π° ΡΠΈΠ»Π° ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ (fa), Π° ΠΊ ΡΠ°Π·ΡΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΠΌ ΡΠ·Π»Π°ΠΌ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½Π° ΡΠΈΠ»Π° ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ (fr). ΠΡΠΈ ΡΠΈΠ»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
ka ΠΈ kr β ΠΊΠΎΠ½ΡΡΠ°Π½ΡΡ, Π° d β ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ·Π»Π°ΠΌΠΈ. ΠΠ»Ρ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΡ ΡΠ·Π»ΠΎΠ² ΡΡΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ d ΡΠ²Π»ΡΠ΅ΡΡΡ Π΄Π»ΠΈΠ½ΠΎΠΉ ΠΏΡΡΠΆΠΈΠ½Ρ. ΠΠ°ΡΠ°Π»ΡΠ½Π°Ρ ΠΊΠΎΠΌΠΏΠΎΠ½ΠΎΠ²ΠΊΠ° Π³ΡΠ°ΡΠ° Π½Π°ΡΡΡΠ°ΠΈΠ²Π°Π΅ΡΡΡ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. Π ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΡΠΈΠ»Ρ ΡΠ°ΡΡΡΠΈΡΡΠ²Π°ΡΡΡΡ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ·Π»Π°, ΠΈ ΡΠ·Π»Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°ΡΡΡΡ, ΡΡΠΎΠ±Ρ ΡΠΌΠ΅Π½ΡΡΠΈΡΡ Π½Π°ΠΏΡΡΠΆΠ΅Π½ΠΈΠ΅. Π‘ΠΎΠ³Π»Π°ΡΠ½ΠΎ Eades (1984), ΠΌΠΎΠ΄Π΅Π»Ρ Spring Embedder ΡΠ°Π±ΠΎΡΠ°Π»Π° ΠΎΡΠ΅Π½Ρ Π±ΡΡΡΡΠΎ Π½Π° VAX 11/780 Π½Π° Π³ΡΠ°ΡΠ°Ρ Ρ ΡΠΈΡΠ»ΠΎΠΌ ΡΠ·Π»ΠΎΠ² Π΄ΠΎ 30. ΠΠ΄Π½Π°ΠΊΠΎ ΠΌΠΎΠ΄Π΅Π»Ρ Spring-Embedder ΠΌΠΎΠΆΠ΅Ρ Π½Π΅ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π½Π° ΠΎΡΠ΅Π½Ρ Π±ΠΎΠ»ΡΡΠΈΡ Π³ΡΠ°ΡΠ°Ρ .
ΠΠΎΠ΄Π΅Π»Ρ spring-embedder Π²Π΄ΠΎΡ Π½ΠΎΠ²ΠΈΠ»Π° Π½Π° ΡΠΎΠ·Π΄Π°Π½ΠΈΠ΅ ΡΡΠ΄Π° ΠΌΠΎΠ΄ΠΈΡΠΈΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΠΈ ΡΠ°ΡΡΠΈΡΠ΅Π½Π½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ². ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠΈΠ»Ρ ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ ΠΎΠ±ΡΡΠ½ΠΎ Π²ΡΡΠΈΡΠ»ΡΡΡΡΡ ΠΌΠ΅ΠΆΠ΄Ρ Π²ΡΠ΅ΠΌΠΈ ΠΏΠ°ΡΠ°ΠΌΠΈ Π²Π΅ΡΡΠΈΠ½, Π° ΡΠΈΠ»Ρ ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΡΠ°ΡΡΡΠΈΡΠ°Π½Ρ ΡΠΎΠ»ΡΠΊΠΎ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΡΠ΅Π΄Π½ΠΈΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. Π£ΠΏΡΠΎΡΠ΅Π½Π½Π°Ρ ΠΌΠΎΠ΄Π΅Π»Ρ ΡΠΌΠ΅Π½ΡΡΠ°Π΅Ρ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ: Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠΈΠ» ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ O(|E|), Ρ ΠΎΡΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠΈΠ»Ρ ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π΄ΠΎ O(|V|Β²), ΡΡΠΎ Π² ΡΠ΅Π»ΠΎΠΌ ΡΠ²Π»ΡΠ΅ΡΡΡ Π±ΠΎΠ»ΡΡΠΈΠΌ ΡΠ·ΠΊΠΈΠΌ ΠΌΠ΅ΡΡΠΎΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Ρ n ΡΠ΅Π»Π°ΠΌΠΈ. ΠΠ°ΠΌΠ°Π΄Π° ΠΈ ΠΠ°Π²Π°ΠΈ (1989) ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠ»ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΠΉ Π½Π° ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΏΡΡΠΆΠΈΠ½Π½ΠΎΠ³ΠΎ Π²Π½Π΅Π΄ΡΠ΅Π½ΠΈΡ ΠΠ΄ΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΡΡΠ°Π΅ΡΡΡ Π΄ΠΎΡΡΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΡ Π΄Π²ΡΡ ΠΊΡΠΈΡΠ΅ΡΠΈΠ΅Π² ΠΈΠ»ΠΈ ΡΠ²ΡΠΈΡΡΠΈΠΊ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ°:
- ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΡΠ΅Π±Π΅Ρ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ.
- ΠΠ΅ΡΡΠΈΠ½Ρ ΠΈ ΡΠ΅Π±ΡΠ° ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Ρ ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎ.
Π¦Π΅Π»Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ Π»ΠΎΠΊΠ°Π»ΡΠ½ΡΠΉ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ ΡΠ½Π΅ΡΠ³ΠΈΠΈ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ Π²Π΅ΠΊΡΠΎΡΠΎΠΌ Π³ΡΠ°Π΄ΠΈΠ΅Π½ΡΠ° Ο = 0, ΡΡΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΡΠΌ, Π½ΠΎ Π½Π΅ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠΌ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ΠΌ Π³Π»ΠΎΠ±Π°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΠ°. Π‘ ΡΠΎΡΠΊΠΈ Π·ΡΠ΅Π½ΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ, ΡΠ°ΠΊΠΎΠΉ ΠΏΠΎΠΈΡΠΊ ΡΡΠ΅Π±ΡΠ΅Ρ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ, ΠΏΠΎΡΡΠΎΠΌΡ Π² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΡΠ°ΡΡΠΎ Π²ΠΊΠ»ΡΡΠ°ΡΡΡΡ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ, ΡΡΠΎΠ±Ρ Π³Π°ΡΠ°Π½ΡΠΈΡΠΎΠ²Π°ΡΡ, ΡΡΠΎ ΠΏΡΡΠΆΠΈΠ½Π½Π°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° Π½Π΅ ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ Π² Π»ΠΎΠ²ΡΡΠΊΠ΅ Π² Π΄ΠΎΠ»ΠΈΠ½Π΅ Π»ΠΎΠΊΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΠ°.
Π ΠΎΡΠ»ΠΈΡΠΈΠ΅ ΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΄Π΅ΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ ΡΠ²Π½ΠΎ Π½Π΅ Π²ΠΊΠ»ΡΡΠ°Π΅Ρ Π·Π°ΠΊΠΎΠ½ ΠΡΠΊΠ°, Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ°ΠΌΠ°Π΄Ρ ΠΈ ΠΠ°Π²Π°ΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅Ρ Π²Π΅ΡΡΠΈΠ½Ρ Π² Π½ΠΎΠ²ΡΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ, ΡΠ°ΠΊ ΡΡΠΎ ΠΎΠ±ΡΠ°Ρ ΡΠ½Π΅ΡΠ³ΠΈΡ ΠΏΡΡΠΆΠΈΠ½Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ ΡΠΌΠ΅Π½ΡΡΠ°Π΅ΡΡΡ Ρ Π½ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠ½ΡΠΈΠ³ΡΡΠ°ΡΠΈΠ΅ΠΉ. ΠΠ½ ΡΠ°ΠΊΠΆΠ΅ Π²Π²ΠΎΠ΄ΠΈΡ ΠΏΠΎΠ½ΡΡΠΈΠ΅ ΠΆΠ΅Π»Π°Π΅ΠΌΠΎΠ³ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΌΠ΅ΠΆΠ΄Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ Π½Π° ΡΠ΅ΡΡΠ΅ΠΆΠ΅: ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ Π΄Π²ΡΠΌΡ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎ Π΄Π»ΠΈΠ½Π΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ ΠΌΠ΅ΠΆΠ΄Ρ Π½ΠΈΠΌΠΈ.
Π‘Π»Π΅Π΄ΡΡ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΡΠΌ ΠΠ°ΠΌΠ°Π΄Ρ ΠΈ ΠΠ°Π²Π°ΠΈ (1989), Π΄Π»Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ ΠΈΠ· n ΡΠ°ΡΡΠΈΡ, ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΡ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΠ±ΠΎΠΉ ΠΏΡΡΠΆΠΈΠ½Π°ΠΌΠΈ, ΠΏΡΡΡΡ p1, p2 ... pn Π±ΡΠ΄ΡΡ ΡΠ°ΡΡΠΈΡΠ°ΠΌΠΈ Π² ΠΎΠ±Π»Π°ΡΡΠΈ ΡΠΈΡΡΠ½ΠΊΠ°, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ v1, v2 ... vn V ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ. . Π‘Π±Π°Π»Π°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ΅ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠ½ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π΄ΠΎΡΡΠΈΠ³Π½ΡΡΠΎ Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈ ΡΠ±Π°Π»Π°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΠΏΡΡΠΆΠΈΠ½Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ. ΠΠ°ΠΌΠ°Π΄Π° ΠΈ ΠΠ°Π²Π°ΠΈ ΡΡΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²Π°Π»ΠΈ ΡΡΠ΅ΠΏΠ΅Π½Ρ Π΄ΠΈΡΠ±Π°Π»Π°Π½ΡΠ° ΠΊΠ°ΠΊ ΠΎΠ±ΡΡΡ ΡΠ½Π΅ΡΠ³ΠΈΡ ΠΏΡΡΠΆΠΈΠ½:
ΠΡ ΠΌΠΎΠ΄Π΅Π»Ρ ΠΏΠΎΠ΄ΡΠ°Π·ΡΠΌΠ΅Π²Π°Π΅Ρ, ΡΡΠΎ Π½Π°ΠΈΠ»ΡΡΡΠ΅Π΅ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π³ΡΠ°ΡΠ° β ΡΡΠΎ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ E. Π Π°ΡΡΡΠΎΡΠ½ΠΈΠ΅ dij ΠΌΠ΅ΠΆΠ΄Ρ Π΄Π²ΡΠΌΡ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ vi ΠΈ vj Π² Π³ΡΠ°ΡΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ Π΄Π»ΠΈΠ½Π° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ ΠΌΠ΅ΠΆΠ΄Ρ vi ΠΈ vj. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ Π½Π° ΡΠΎΠ³Π»Π°ΡΠΎΠ²Π°Π½ΠΈΠ΅ Π΄Π»ΠΈΠ½Ρ ΠΏΡΡΠΆΠΈΠ½Ρ lij ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ°ΡΡΠΈΡΠ°ΠΌΠΈ pi ΠΈ pj Ρ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ ΠΏΡΡΠΈ, ΡΡΠΎΠ±Ρ Π΄ΠΎΡΡΠΈΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ ΠΌΠ΅ΠΆΠ΄Ρ Π½ΠΈΠΌΠΈ Π½Π° ΡΠ΅ΡΡΠ΅ΠΆΠ΅. ΠΠ»ΠΈΠ½Π° lij ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
Π³Π΄Π΅ L β ΠΆΠ΅Π»Π°Π΅ΠΌΠ°Ρ Π΄Π»ΠΈΠ½Π° ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° Π² ΠΎΠ±Π»Π°ΡΡΠΈ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ. L ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π³ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΌΠ΅ΠΆΠ΄Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ Π² Π³ΡΠ°ΡΠ΅. ΠΡΠ»ΠΈ Lo β Π΄Π»ΠΈΠ½Π° ΡΡΠΎΡΠΎΠ½Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ° ΠΎΠ±Π»Π°ΡΡΠΈ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ, L ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
Π‘ΠΈΠ»Π° ΠΏΡΡΠΆΠΈΠ½Ρ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅ΠΉ pi ΠΈ pj, ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°Π΅ΡΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠΌ kij:
ΠΠ°ΡΠ΅ΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ ΠΈΡΠ΅Ρ Π²ΠΈΠ·ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ·Π»Π° v Π² ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΠΈ ΡΠ΅ΡΠΈ ΠΈ ΠΏΡΡΠ°Π΅ΡΡΡ ΡΠΌΠ΅Π½ΡΡΠΈΡΡ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ½Π΅ΡΠ³ΠΈΠΈ Π²ΠΎ Π²ΡΠ΅ΠΉ ΡΠ΅ΡΠΈ. Π’ΠΎ Π΅ΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ Π²ΡΡΠΈΡΠ»ΡΠ΅Ρ ΡΠ°ΡΡΠ½ΡΠ΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄Π½ΡΠ΅ Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ·Π»ΠΎΠ² ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΠΈ ΡΠ΅ΡΠΈ Ρ ΡΠΎΡΠΊΠΈ Π·ΡΠ΅Π½ΠΈΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ xv ΠΈ yv, ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠ°Π²Π½Ρ Π½ΡΠ»Ρ (Ρ.Π΅. βE / βxv = βE / βyv = 0; 1 < v < n).
ΠΠ΄Π½Π°ΠΊΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π²ΡΠ΅Ρ ΡΡΠΈΡ Π½Π΅Π»ΠΈΠ½Π΅ΠΉΠ½ΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΎΠ½ΠΈ Π·Π°Π²ΠΈΡΡΡ Π΄ΡΡΠ³ ΠΎΡ Π΄ΡΡΠ³Π°. ΠΠΎΡΡΠΎΠΌΡ Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΎΠ½Π½ΡΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΠΉ Π½Π° ΠΌΠ΅ΡΠΎΠ΄Π΅ ΠΡΡΡΠΎΠ½Π°-Π Π°ΡΡΠΎΠ½Π°. ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π²ΡΠ±ΠΈΡΠ°Π΅Ρ ΡΠ·Π΅Π» m Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ΠΌ (Ξm). ΠΡΡΠ³ΠΈΠΌΠΈ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ, ΡΠ·Π΅Π» m ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅ΡΡΡ Π² Π½ΠΎΠ²ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅, Π³Π΄Π΅ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ Π΄ΠΎΡΡΠΈΡΡ Π±ΠΎΠ»Π΅Π΅ Π½ΠΈΠ·ΠΊΠΎΠ³ΠΎ ΡΡΠΎΠ²Π½Ρ Ξm, ΡΠ΅ΠΌ ΡΠ°Π½ΡΡΠ΅. ΠΠ΅ΠΆΠ΄Ρ ΡΠ΅ΠΌ, Π΄ΡΡΠ³ΠΈΠ΅ ΡΠ·Π»Ρ ΠΎΡΡΠ°ΡΡΡΡ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ. ΠΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ (Ξm) ΡΠ°ΡΡΡΠΈΡΡΠ²Π°Π΅ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π€ΡΡΡ ΡΠ΅ΡΠΌΠ°Π½Π°-Π Π΅ΠΉΠ½Π³ΠΎΠ»ΡΠ΄Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ Π½Π° ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΏΡΡΠΆΠΈΠ½Π½ΠΎΠ³ΠΎ Π²ΡΡΡΠ°ΠΈΠ²Π°Π½ΠΈΡ ΠΠ΄ΡΠ°. ΠΠ½ ΡΠ°Π²Π½ΠΎΠΌΠ΅ΡΠ½ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΡΠ·Π»Ρ, ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡΡΡ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ΅Π±Π΅Ρ. ΠΠ½ ΡΠ°ΠΊΠΆΠ΅ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅Ρ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΡ Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±Π΅Ρ. Π ΠΎΡΠ»ΠΈΡΠΈΠ΅ ΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ, ΠΎΠ½ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ Π΄Π²Π΅ ΡΠΈΠ»Ρ (ΡΠΈΠ»Ρ ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ ΠΈ ΡΠΈΠ»Ρ ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ) Π΄Π»Ρ ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΡ ΡΠ·Π»ΠΎΠ², Π° Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ½Π΅ΡΠ³ΠΈΠΈ Ρ ΡΠ΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ Π³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ. ΠΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , ΡΠΈΠ»Π° ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ (fa) ΠΈ ΡΠΈΠ»Π° ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ (fr) ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
Π³Π΄Π΅ d β ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ Π΄Π²ΡΠΌΡ ΡΠ·Π»Π°ΠΌΠΈ, Π° k β ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΈΠ΄Π΅Π°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎΠΏΠ°ΡΠ½ΠΎΠ³ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ. ΠΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΈΠ΄Π΅Π°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ k = β(area / n). ΠΠ΄Π΅ΡΡ area β ΠΎΠ±Π»Π°ΡΡΡ ΡΠ°ΠΌΠΊΠΈ ΡΠ΅ΡΡΠ΅ΠΆΠ°, n β ΠΎΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ·Π»ΠΎΠ² Π² ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΠΈ ΡΠ΅ΡΠΈ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π€ΡΡΡ ΡΠ΅ΡΠΌΠ°Π½Π°-Π Π΅ΠΉΠ½Π³ΠΎΠ»ΡΠ΄Π° Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΠ²Π½ΠΎ, ΠΈ Π²ΡΠ΅ ΡΠ·Π»Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°ΡΡΡΡ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΠΏΠΎΡΠ»Π΅ ΡΠ°ΡΡΠ΅ΡΠ° ΡΠΈΠ» Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅Ρ Π°ΡΡΠΈΠ±ΡΡ Β«ΡΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅Β» Π΄Π»Ρ ΠΊΠΎΠ½ΡΡΠΎΠ»Ρ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ·Π»ΠΎΠ². Π Π½Π°ΡΠ°Π»Π΅ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π€ΡΡΡ ΡΠ΅ΡΠΌΠ°Π½Π°-Π Π΅ΠΉΠ½Π³ΠΎΠ»ΡΠ΄Π° Π²ΡΡΠΈΡΠ»ΡΠ΅Ρ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΡ Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ·Π»ΠΎΠ² Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΡΠΈΠ»Ρ ΠΎΡΡΠ°Π»ΠΊΠΈΠ²Π°Π½ΠΈΡ (fr). ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°ΠΊΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΡΠΈΠ»Ρ ΠΏΡΠΈΡΡΠΆΠ΅Π½ΠΈΡ (fa) Π΄Π»Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΡ Π²ΠΈΠ·ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ·Π»ΠΎΠ² Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ΅Π±ΡΠ΅. ΠΠ°ΠΊΠΎΠ½Π΅Ρ, ΠΎΠ½ ΠΎΠ±Π½ΠΎΠ²Π»ΡΠ΅Ρ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ·Π»ΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΠΌΠ΅ΡΠ΅Π½ΠΈΡ.
ΠΡΠΎ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π΄Π²ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ²: ΠΠ°ΠΌΠ°Π΄Π°-ΠΠ°Π²Π°ΠΈ ΠΈ Π€ΡΡΡ ΡΠ΅ΡΠΌΠ°Π½Π°-Π Π΅ΠΉΠ½Π³ΠΎΠ»ΡΠ΄Π° Π½Π° ΡΠ·ΡΠΊΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π‘ΠΈ. Π‘ΡΡΡΠΊΡΡΡΠ° Graph Π²ΠΊΠ»ΡΡΠ°Π΅Ρ Π² ΡΠ΅Π±Ρ Π΄Π²Π° Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΡ ΠΌΠ°ΡΡΠΈΠ²Π°: ΠΎΠ΄ΠΈΠ½ ΠΌΠ°ΡΡΠΈΠ² ΡΠΊΠ°Π·Π°ΡΠ΅Π»Π΅ΠΉ Π½Π° Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ ΠΎΠ΄ΠΈΠ½ ΠΌΠ°ΡΡΠΈΠ² ΡΠ΅Π±Π΅Ρ c ΠΈΡ ΡΠ°Π·ΠΌΠ΅ΡΠ°ΠΌΠΈ.
struct Graph
{
struct Vertex **vertexes;
struct Edge *edges;
int vertexes_num;
int edges_num;
};
ΠΠ°ΠΆΠ΄Π°Ρ Π²Π΅ΡΡΠΈΠ½Π° ΠΈΠΌΠ΅Π΅Ρ ΠΈΠΌΡ ΠΈ ΡΠ²ΠΎΠ΅ ΠΌΠ΅ΡΡΠΎΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π² Π²Π΅ΠΊΡΠΎΡΠ½ΠΎΠΉ ΡΠΎΡΠΌΠ΅:
struct Vertex { int name; struct Vector location; };
Π Π΅Π±ΡΠΎ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Π΅ΠΉ Π½Π° Π²Π΅ΡΡΠΈΠ½Ρ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΎΠ½ΠΎ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ΅Ρ:
struct Edge { struct Vertex *start; struct Vertex *end; };
void ForceDirectedLayout(struct Graph *graph, int max_iteration)
{
int v_num = graph->vertexes_num;
double k = sqrt(LENGTH * LENGTH / v_num);
double t = 20;
int stop_count = 0;
// Stop when total movement falls under a certain range
// for (int i = 0; i < max_iteration; i++)
while (stop_count < max_iteration)
{
struct Vector displacement[v_num];
// Calculate the repulsive forces on vertexes/electrons
for (int i = 0; i < v_num; i++)
{
displacement[i] = new_vector(0, 0);
for (int j = 0; j < v_num; j++)
{
if (i != j)
{
struct Vector diff = sub(graph->vertexes[i]->location, graph->vertexes[j]->location);
// displacement = displacement + (diff / |diff|) * Fr
displacement[i] = add(displacement[i], multiply(devide(diff, absolute(diff)), Fr(absolute(diff), k)));
}
}
}
// Calculate the attractive forces on edges/springs
for (int i = 0; i < graph->edges_num; i++)
{
int start_i = findVIndex(graph->edges[i].start, graph);
int end_i = findVIndex(graph->edges[i].end, graph);
struct Vector diff = sub(graph->vertexes[start_i]->location, graph->vertexes[end_i]->location);
// displacement = displacement +- (diff / |diff|) * Fa
displacement[start_i] = sub(displacement[start_i], multiply(devide(diff, absolute(diff)), Fa(absolute(diff), k)));
displacement[end_i] = add(displacement[end_i], multiply(devide(diff, absolute(diff)), Fa(absolute(diff), k)));
}
double total_displacement = 0;
// Limit the max displacement to a temperature t and keep them inside the frame
// The temperature t allows for large movements at the beginning of the loop
// and smaller, more refined movements near the end.
for (int i = 0; i < v_num; i++)
{
struct Vector disp = displacement[i];
struct Vector lim_disp = multiply(devide(disp, absolute(disp)), __min(absolute(disp), t));
graph->vertexes[i]->location = add(graph->vertexes[i]->location, lim_disp);
total_displacement += absolute(lim_disp);
}
// Stop when total movement falls under a certain range
if (total_displacement < 0.0001 * (v_num))
{
printf("Small displacement\n");
stop_count++;
}
t = cool(t);
}
printf("Graph placed with force-directed layout!\n");
}
void LocalMinimum(struct Graph *gr, double eps)
{
// Two dimensional array of shortest path between two vertexes
// Calculate using Floyd-Warshall algorithm
int **d = floyd_warshall(*gr);
int v_num = gr->vertexes_num;
int e_num = gr->edges_num;
double Lo = LENGTH * 10 / e_num;
double K = 100;
int d_max = d[0][0];
for (int i = 0; i < v_num; i++)
{
for (int j = i + 1; j < v_num; j++)
{
d_max = __max(d_max, d[i][j]);
}
}
// Initializing l_ij, k_ij
double **l = (double **)malloc(sizeof(double *) * v_num);
double **k = (double **)malloc(sizeof(double *) * v_num);
for (int i = 0; i < v_num; i++)
{
l[i] = (double *)malloc(sizeof(double) * v_num);
k[i] = (double *)malloc(sizeof(double) * v_num);
for (int j = 0; j < v_num; j++)
{
l[i][j] = Lo / d_max * d[i][j];
k[i][j] = K / pow(d[i][j], 2);
}
}
// Moving the vertex with highest energy decrease
double *Delta = (double *)malloc(sizeof(double) * v_num);
int max_i = calcDelta(gr, k, l, Delta);
while (Delta[max_i] > eps)
{
while (Delta[max_i] > eps)
{
struct Vector dE = new_vector(0, 0);
double Exx = 0;
double Exy = 0;
double Eyy = 0;
for (int i = 0; i < v_num; i++)
{
if (i == max_i)
continue;
struct Vector dmax_i = sub(gr->vertexes[max_i]->location, gr->vertexes[i]->location);
double n = 1.0 - l[max_i][i] / absolute(dmax_i);
dE = add(dE, multiply(multiply(dmax_i, n), k[max_i][i]));
Exy += k[max_i][i] * l[max_i][i] * dmax_i.x * dmax_i.y / pow(absolute(dmax_i), 3);
Exx += k[max_i][i] * (1.0 - l[max_i][i] * dmax_i.y * dmax_i.y / pow(absolute(dmax_i), 3));
Eyy += k[max_i][i] * (1.0 - l[max_i][i] * dmax_i.x * dmax_i.x / pow(absolute(dmax_i), 3));
}
double D = Exx * Eyy - Exy * Exy;
struct Vector d;
d.x = -(Eyy * dE.x - Exy * dE.y) / D;
d.y = -(-Exy * dE.x + Exx * dE.y) / D;
gr->vertexes[max_i]->location = add(gr->vertexes[max_i]->location, d);
Delta[max_i] = absolute(dE);
}
max_i = calcDelta(gr, k, l, Delta);
}
printf("Graph placed with local minimum layout!\n");
}
int calcDelta(struct Graph gr, double **k, double **l, double *Delta)
{
double maxDelta = 0;
int m_i = 0;
for (int i = 0; i < gr.vertexes_num; i++)
{
// dE is vector energy
struct Vector dE = new_vector(0, 0);
for (int j = 0; j < gr.vertexes_num; j++)
{
if (i == j)
continue;
struct Vector d = sub(gr.vertexes[i]->location, gr.vertexes[j]->location);
double n = 1.0 - l[i][j] / absolute(d);
dE = add(dE, multiply(multiply(d, n), k[i][j]));
}
// Find vertex with highest energy
Delta[i] = absolute(dE);
if (Delta[i] > maxDelta)
{
maxDelta = Delta[i];
m_i = i;
}
}
return m_i;
}
Π Π°ΡΠΊΠ»Π°Π΄ΠΊΠ° Π³ΡΠ°ΡΠ° Local minmum - Kamada - Kawaii
Π Π°ΡΠΊΠ»Π°Π΄ΠΊΠ° Π³ΡΠ°ΡΠ° Force-directed layout - Fruchterman - Reingold