Содержание
- 2. Методы размещения, основанные на физических аналогиях Методы, основанные на физических аналогиях очень популярны по следующим причинам:
- 3. Методы размещения, основанные на физических аналогиях Основу любого силового алгоритма составляют две компоненты: модель, описывающая физические
- 4. Методы размещения, основанные на физических аналогиях (общие рассуждения) Рассмотрим, к примеру, связный неориентированный граф G(V,E) и
- 5. Методы размещения, основанные на физических аналогиях (общие рассуждения) Эти пожелания можно обосновать только интуитивно. Равномерное распределение
- 6. Методы размещения, основанные на физических аналогиях (общие рассуждения) Пружины подходят больше, чем жесткие палки или веревки,
- 7. Методы размещения, основанные на физических аналогиях (общие рассуждения) Если система описана, и объектам разрешено двигаться под
- 8. Силовые алгоритмы (Spring embedder, Eades 1984) Дан связный неориентированный граф G = (V, E) Пусть P
- 9. Силовые алгоритмы (Eades 1984) 1) Сила отталкивания действует между каждой парой не-смежных вершин: u, v ∈V
- 10. Силовые алгоритмы (Eades 1984) Алгоритм Spring embedder (Eades 1984) Вход: связный неориентированный граф G = (V,
- 11. Пример изображения, порождаемого алгоритмом Eades
- 12. Силовые алгоритмы (Fruchterman &Reingold, 1991) Алгоритм Фрюхтермана и Рейнгольда 1991 года ввел критерий равномерного распределения и
- 13. Fruchterman&Reingold(1991). Модификация сил, действующих на вершины Силы отталкивания действуют между каждой парой вершин для всех (u,
- 14. Fruchterman&Reingold(1991). Сила притяжения вычисляется быстрее, потому что не надо вычислять корень. Процесс быстрее сходится к решению,
- 15. Силовые алгоритмы (Fruchterman &Reingold, 1991) area:= W * L; {W и L – это ширина и
- 16. Силовые алгоритмы (Fruchterman &Reingold, 1991) /* вычислить силы отталкивания, действующие на каждую вершину со стороны всех
- 17. Силовые алгоритмы (Fruchterman &Reingold, 1991) /*вычислить силы притяжения между двумя смежными вершинами смещения обеих вершин под
- 18. Силовые алгоритмы (Fruchterman &Reingold, 1991) /*ограничить max_смещение температурой t и предотвратить перемещения за границу фрейма*/ for
- 19. Модификации, связанные с вектором смещения вместо использования константного множителя δ ввели смещение, зависящее от температуры δ(t)
- 20. Fruchterman&Reingold(1991) На каждой итерации базовый алгоритм вычисляет O(|E|) сил притяжения и O(|V|2) сил отталкивания. Для уменьшения
- 21. Пример изображения, получаемого алгоритмом Fruchterman- Reingolda
- 22. Силы гравитации и алгоритм Frick Одной пружинной модели оказалось недостаточно, поскольку обнаружилось, что в случае несвязного
- 23. Силовые алгоритмы (Frick et al,1995) Поэтому в работе (Frick et al 1995) была введена еще дополнительная
- 24. Силовые алгоритмы (Frick et al,1995) То есть, вершины с высокой степенью двигаются медленнее, они ведь «тяжелые»
- 25. Силовые алгоритмы (Frick et al,1995) Кроме того, была введена сила гравитации, которая толкает каждую вершину к
- 26. Силовые алгоритмы (Frick et al,1995) Чтобы уменьшить количество итераций, вектор Fv(t-1) запоминался и сравнивался с Fv(t)
- 27. Силовые алгоритмы (Frick et al,1995)
- 28. Силовые алгоритмы (Frick et al,1995)
- 29. Силовые алгоритмы (Frick et al,1995)
- 30. Силовые алгоритмы (Frick et al,1995)
- 31. Силовые алгоритмы, сила гравитации Нет силы гравитации коэфф. гравитации = 0,6 Коэфф. гравитации = 1,5 Поскольку
- 32. Силовые алгоритмы, сила гравитации нет силы гравитации коэфф. гравитации = 2,0 Специфика гравитации становится заметна, если
- 33. Силовые алгоритмы Результат работы силового алгоритма с использованием силы гравитации, силы отталкивания и силы притяжения пружин
- 34. Магнитное поле. Sugiyama, Misue “A simple and unified method for drawing graphs: magnetic-spring algorithm”1995. Пружинные алгоритмы
- 35. Магнитное поле. cm, α, β > 0 параметры настройки системы Сила магнитного поля, действующая на ребро,
- 36. Магнитные поля [SM95] Разные типы магнитных полей: Параллельное: все силы действуют в одном направлении, может быть
- 37. Магнитные силы комбинируются с электрической силой и силой пружины Алгоритм поиска равновесия Случайное начальное размещение и
- 38. Влияние магнитного поля Нет магнитного поля Параллельное магнитное поле
- 39. Влияние магнитного поля Нет магнитного поля концентрическое магнитное поле
- 40. Влияние магнитного поля Нет магнитного поля ортогональное магнитное поле
- 41. S.Hong, D.Merrick H.Nascimento Automatic Visualization of Metro Maps, 2006 План метро Сиднея, с применением ортогонального магнитного
- 42. Размещения, основанные на энергии Силы, определенные в предыдущих алгоритмах, указывают, в каком направлении надо сдвинуть вершину,
- 43. [Kamada, Kawai 89] В 1989 году Камада и Кавай ввели другой взгляд на то, что считать
- 44. [Kamada, Kawai 89] Была взята за основу потенциальная энергия пружины, имеющей естественную длину l, растянутой до
- 45. [Kamada, Kawai 89] Пусть dij означает длину кратчайшего пути между вершинами i и j в графе
- 46. [Kamada, Kawai 89] Таким образом, получаем следующую функцию энергии: Координаты частицы pi в Евклидовой плоскости определяются
- 47. [Kamada, Kawai 89] Требуется найти такие значения переменных, которые минимизируют функцию энергии EКК(x1,x2,...xn,y1,y2, , yn). Поскольку
- 48. [Kamada Kawai 89] Уравнение можно решить при помощи итеративного подхода На каждом шаге перемещается одна вершина,
- 49. [Kamada, Kawai 89] Вычислить di,j for 1 ≤ i ≠j ≤ n; Вычислить li,j for 1
- 50. Пример размещения полученного методом Фрюхтерман-Рейнгольда
- 52. Пример результата размещения методом Камада-Кавая графа связей Автор_публикации с предварительным выделением несвязных компонент
- 53. [Kamada, Kawai 89] Алгоритм Камада-Кавая является вычислительно затратным, поскольку требует вычисления кратчайших путей между всеми парами
- 54. Метод барицентров(алгоритм Tutte,63) Исторически, метод барицентровТатта 1963 года был первым силовым алгоритмом для получения изображения без
- 55. Метод барицентров(алгоритм Tutte,63) Вместо пружин переменной длины, как у Камада –Кавая, Татт считает, что идеальная длина
- 56. Разбить V на 2 подмножества: фиксированные вершины (не меньше 3) и свободные вершины Для достижения равновесия,
- 57. Метод барицентров(алгоритм Tutte,63) Все уравнения линейные. Количество уравнений и количество неизвестных равны количеству свободных вершин. Решается
- 58. Пример G: Сделаем грань {v1, v2, v3} внешней v1 v2 v3 v4 v5 v1(3,6) v2(0,3) v3(4,1)
- 59. Пример (2) V(J) = {v1, v2, v3} N(4) = {v1, v2, v3, v5} N(5) = {v2,
- 60. Пример: Алгоритм Tutte Пусть координаты вершин имеют следующие значения: v1= (3,6), v2= (0, 3), v3 =
- 61. Пример: Алгоритм Tutte В соответствии с нашим выбором v1x= 3, v2x= 0, v3x= 4. L44 равно
- 62. Пример: Алгоритм Tutte Точно так же y-координаты вершин v4 и v5 вычисляются через известные y-координаты вершин
- 63. Пример: Алгоритм Tutte v1(3,6) v2(0,3) v3(4,1) x y
- 64. Algorithm Barycenter-Draw Вход: разбиение множества вершин V, V0: не менее 3 фиксированных вершин V1: множество свободных
- 65. Метод барицентров(алгоритм Tutte,63) Основная теорема, доказанная Tutte (1963) утверждает, что барицентрическое размещение 3-связных планарных графов является
- 66. Пример размещения, полученного методом барицентров Применим только для трехсвязных графов Одним существенным недостатком этого метода является
- 68. Скачать презентацию