Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка 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 .