Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтарды визуализациялау үшін физикалық модельдеу. Күшке бағытталған граф сызу алгоритмдері – графтарды эстетикалық тұрғыдан әдемі етіп салуға арналған алгоритмдер класы. Олардың мақсаты – графтың түйіндерін екі өлшемді немесе үш өлшемді кеңістікте орналастыру, соның нәтижесінде барлық қабырғалар шамамен бірдей ұзындықта болады және қиылысатын қабырғалар саны ең аз болады. Бұл үшін қабырғалар мен түйіндердің өзара орналасуына байланысты оларға күштер тағайындалады, содан кейін осы күштер қабырғалар мен түйіндердің қозғалысын модельдеу үшін немесе олардың энергиясын азайту үшін қолданылады. Граф сызу қиын мәселе болуы мүмкін, бірақ күшке бағытталған алгоритмдер физикалық модельдеу болғандықтан, әдетте, граф теориясы туралы, мысалы, жазықтық туралы арнайы білімді қажет етпейді.
Physical simulation to visualize graphs
Force directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically pleasing way. 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, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the motion of the edges and nodes or to minimize their energy. While graph drawing can be a difficult problem, force directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as planarity.
Қуаттар
Күшке бағытталған график сызу алгоритмдері график сызбасының қабырғалары мен түйіндер жиынтығына күштер тағайындайды. Әдетте, Гук заңына негізделген серіппеге ұқсас тартымды күштер графиктің қабырғаларының жұптарын бір-біріне тарту үшін қолданылады, ал Кулон заңына сәйкес электр зарядталған бөлшектер сияқты, бір мезгілде тебу күштері барлық түйіндер жұбын бөлу үшін пайдаланылады. Бұл күштер жүйесінің тепе-теңдік күйінде қабырғалар біркелкі ұзындыққа ие болады (серіппе күштерінің әсерінен), ал қабырғалармен байланыспаған түйіндер бір-бірінен алшақтайды (электрлік тебудің әсерінен). Қабырғалардың тартылуы және түйіндердің тебу күштерін серіппелер мен бөлшектердің физикалық қасиеттеріне негізделмеген функциялар арқылы анықтауға болады; мысалы, кейбір күшке бағытталған жүйелер тартымды күші сызықты емес, логарифмдік болатын серіппелерді қолданады. Балама модельде әрбір түйін жұбы үшін серіппеге ұқсас күш қарастырылады, онда әрбір серіппенің идеалды ұзындығы i және j түйіндері арасындағы граф теориялық қашықтыққа пропорционалды, бөлек тебу күшін қолданбайды. Түйіндер арасындағы Эвклидтік және идеалды қашықтықтардың айырмасын (әдетте квадрат айырмасын) азайту метрикалық көпөлшемді масштабтау мәселесіне тең. Күшке бағытталған график механикалық серіппелер мен электрлік тебуден басқа күштерді де қамтуы мүмкін. Ауырлық күшіне ұқсас күш түйіндерді сызу кеңістігінің белгілі бір нүктесіне қарай тарту үшін қолданылуы мүмкін; бұл үзілген графиктің әртүрлі байланысқан компоненттерін біріктіруге мүмкіндік береді, әйтпесе тебу күштерінің әсерінен олар бір-бірінен алшақтауға бейімделеді, сондай-ақ сызбадағы орталыққа жақын түйіндерді орталыққа жақын жерлерге тарту үшін; ол сонымен қатар бір компонент ішіндегі түйіндер арасындағы арақашықтыққа да әсер етуі мүмкін. Бағытталған графтар үшін магниттік өрістердің аналогтары қолданылуы мүмкін. Соңғы сызбада бір-біріне жақын орналасуын болдырмау үшін қабырғаларға да, түйіндерге де тебу күштері қолданылуы мүмкін. Иілген қабырғалары бар сызбаларда, мысалы, шеңбер доғалары немесе сплайн қисықтарында, күштер осы қисықтардың басқару нүктелеріне де қолданылуы мүмкін, мысалы, бұрыштық ажыратымдылықты жақсарту үшін.
Force directed graph drawing algorithms assign forces among the set of edges and the set of nodes of a graph drawing. Typically, spring like attractive forces based on Hooke's law are used to attract pairs of endpoints of the graph's edges towards each other, while simultaneously repulsive forces like those of electrically charged particles based on Coulomb's law are used to separate all pairs of nodes. In equilibrium states for this system of forces, the edges tend to have uniform length (because of the spring forces), and nodes that are not connected by an edge tend to be drawn further apart (because of the electrical repulsion). Edge attraction and vertex repulsion forces may be defined using functions that are not based on the physical behavior of springs and particles; for instance, some force directed systems use springs whose attractive force is logarithmic rather than linear. An alternative model considers a spring like force for every pair of nodes where the ideal length of each spring is proportional to the graph theoretic distance between nodes i and j, without using a separate repulsive force. Minimizing the difference (usually the squared difference) between Euclidean and ideal distances between nodes is then equivalent to a metric multidimensional scaling problem. A force directed graph can involve forces other than mechanical springs and electrical repulsion. A force analogous to gravity may be used to pull vertices towards a fixed point of the drawing space; this may be used to pull together different connected components of a disconnected graph, which would otherwise tend to fly apart from each other because of the repulsive forces, and to draw nodes with greater centrality to more central positions in the drawing; it may also affect the vertex spacing within a single component. Analogues of magnetic fields may be used for directed graphs. Repulsive forces may be placed on edges as well as on nodes in order to avoid overlap or near overlap in the final drawing. In drawings with curved edges such as circular arcs or spline curves, forces may also be placed on the control points of these curves, for instance to improve their angular resolution.
Әдістер
Графтың түйіндері мен қабырғаларындағы күштер анықталғаннан кейін, осы күштер әсерімен бүкіл графтың мінез-құлқы физикалық жүйе сияқты модельделуі мүмкін. Мұндай модельдеуде күштер түйіндерге қолданылады, оларды жақындастырады немесе алыстатады. Бұл жүйе механикалық тепе-теңдікке жеткенше итеративті түрде қайталанады; яғни, олардың өзара орналасуы бір итерациядан екіншісіне өзгермейді. Осы тепе-теңдіктегі түйіндердің орналасуы графтың суретін салу үшін пайдаланылады. Егер серіппе күштерінің идеалдық ұзындығы граф теориялық қашықтыққа пропорционалды болса, кернеуді мажоризациялау осы айырмашылықтарды өте жақсы (яғни, монотонды түрде жинақталушы) және математикалық тұрғыдан әдемі жолмен азайтуға, сонымен қатар граф үшін жақсы орналасуды табуға мүмкіндік береді. Физикалық модельдеудің орнына немесе онымен қатар энергияның ең төмен нүктесін тікелей іздейтін механизмдерді қолдануға да болады. Мұндай механизмдер, жалпы жаһандық оңтайландыру әдістерінің мысалдары, симуляцияланған қайнату және генетикалық алгоритмдерді қамтиды.
Once the forces on the nodes and edges of a graph have been defined, the behavior of the entire graph under these sources may then be simulated as if it were a physical system. In such a simulation, the forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to a mechanical equilibrium state; i. e., their relative positions do not change anymore from one iteration to the next. The positions of the nodes in this equilibrium are used to generate a drawing of the graph. For forces defined from springs whose ideal length is proportional to the graph theoretic distance, stress majorization gives a very well behaved (i. e., monotonically convergent) and mathematically elegant way to minimize these differences and, hence, find a good layout for the graph. It is also possible to employ mechanisms that search more directly for energy minima, either instead of or in conjunction with physical simulation. Such mechanisms, which are examples of general global optimization methods, include simulated annealing and genetic algorithms.
Тарих
Графтарды сызудағы күшпен бағытталған әдістердің тарихы , оның көпбұрышты графтарды барлық жақтары дөңгелек болатындай жазықтықта салуға болатынын көрсеткен жұмысына дейін жетеді. Бұл үшін графтың жазықтыққа енгізілуінің сыртқы жағындағы төбелері дөңгелек орналасуы керек, әр қабырғаға серпімді күш сияқты тартымды күш қойылады, содан кейін жүйе тепе-теңдікке келеді. Бұл жағдайда күштердің қарапайымдылығының арқасында жүйе жергілікті минимумға ілігіп қалмайды, керісінше бірегей жаһандық оңтайлы конфигурацияға жуысады. Осы жұмыстың нәтижесінде, дөңгелек жақтары бар жазықты графтардың енгізілуі кейде Тютте енгізілуі деп аталады. Үйірлі төбелерде тартымды күштердің және барлық төбелерде итергіш күштердің үйлесімі алғаш рет ; осы типтегі күшпен бағытталған орналасу бойынша алғашқы жұмыстар жасалды. Барлық төбелер арасында тек серпімді күштерді қолдану идеясы, мұндағы серпімді күштердің идеалды ұзындығы төбелердің граф теориялық қашықтығына тең, -ден шыққан.
Force directed methods in graph drawing date back to the work of , who showed that polyhedral graphs may be drawn in the plane with all faces convex by fixing the vertices of the outer face of a planar embedding of the graph into convex position, placing a spring like attractive force on each edge, and letting the system settle into an equilibrium. Because of the simple nature of the forces in this case, the system cannot get stuck in local minima, but rather converges to a unique global optimum configuration. Because of this work, embeddings of planar graphs with convex faces are sometimes called Tutte embeddings. The combination of attractive forces on adjacent vertices, and repulsive forces on all vertices, was first used by ; additional pioneering work on this type of force directed layout was done by The idea of using only spring forces between all pairs of vertices, with ideal spring lengths equal to the vertices' graph theoretic distance, is from .