Как нарисовать граф, имея 2-мерную матрицу

@saroff · Регистрация: 09.11.2013

Студворк — интернет-сервис помощи студентам

На входе есть двумерная матрица смежности, нужно по нему нарисовать сам граф. Как это сделать - не представляю. Ведь вершин может быть и пять, и сорок пять. Понимаю, что нужно сделать так чтобы ни одни любые три вершины не находились на одной прямой, подскажите как это можно сделать.

@Qwertiy · 30.12.2013, 13:41

Программно нарисовать или на бумаге?

@saroff · 30.12.2013, 16:32 **[ТС]**

Qwertiy, Прогамно, естественно) есть идея сделать алгоритм, который рандомом бы задавал положения вершин (т.е. координаты их на мониторе), а потом проверял, не находятся ли любые три из них на одной прямой и если находятся, то как нибудь изменял бы их. Но я не представляю как сделать эту проверку.

@Catstail · 31.12.2013, 16:04

А почему три вершины не могут быть на одной прямой? Что в этом страшного?

@Mysterious Light · 31.12.2013, 16:32

Сообщение от Catstail

А почему три вершины не могут быть на одной прямой? Что в этом страшного?

Если вершины A,B и C находятся на одной прямой, то отрезок, соединяющий крайние точки можно неоднозначно трактовать как одно ребро или как два.

Сообщение от saroff

есть идея сделать алгоритм, который рандомом бы задавал положения вершин (т.е. координаты их на мониторе), а потом проверял, не находятся ли любые три из них на одной прямой и если находятся, то как нибудь изменял бы их. Но я не представляю как сделать эту проверку.

Почему бы не расположить на окружности все точки?

Вообще, по этому вопросу много есть литературы, хотя бы:
http://ru.wikipedia.org/wiki/Визуализация_графов
http://en.wikipedia.org/wiki/G... ut_methods
Особо обратите внимание на Force-based layout и Circular layout.

Последнее я Вам предложил выше: расположить точки по окружности.
А силовой метод мне кажется наиболее симпатичным: сначала рандомно располагаем точки, потом в вершины помещаются заряды, а ребра мыслятся как пружинки, и вся эта система приводится в движение с диссипацией (трением), пока не займет устойчивое положение. Требует симуляции движения, но там законы не сложные и точность-то нам не особо важна.

@saroff · 31.12.2013, 16:49 **[ТС]**

Mysterious Light, Если и делать движение, то как нибудь потом. Т.к. делается это все на канве в делфи, с которой постоянные проблемы. А за идею с окружность спасибо, покурю на досуге)

@Qwertiy · 03.01.2014, 20:38

Сообщение от saroff

Если и делать движение, то как нибудь потом. Т.к. делается это все на канве в делфи, с которой постоянные проблемы

Эм.. Так движение же не надо рисовать. Просто просчитать как оно будет и вывести результат

@saroff · 04.01.2014, 02:20 **[ТС]**

Qwertiy, Что то у меня наверное очередной затуп был... А можно какую нибудь статейку или еще чего по теме именно силовой реализации? Или хотя бы гуглопригодное название.

@Qwertiy · 04.01.2014, 04:13

Не искал... Вроде должно нормально гуглиться по чему-то вроде раскладки графов.

В общем, там идея простая. Берём и рассматриваем всё рёбра как одинаковые пружины, натянутые между шариками. От каждой такой пружины на шарик действует сила. Итерационным методом эмулируем перемещение. Стабилизировавшаяся система - это и есть раскладка. Чтобы не возникло колебаний, надо использовать затухание типа умножения на 0.9 на каждом шаге.

@Igor3D · 04.01.2014, 10:44

Идея с системой которая "самобалансируется" конечно красивая. Когда-то делал немного подобное и удивительно как быстро наступает состояние равновесия. Но в данном случае - наверное нет т.к. могут быть длинные ребра, пересекающие слишком много остального.

Я бы сначала поставил самое длинное ребро, а потом бы присоединял новые вершины, немного похоже на триангуляцию Делоне, только др критерии

@Qwertiy · 04.01.2014, 13:31

Сообщение от Igor3D

Я бы сначала поставил самое длинное ребро

А какое ребро самое длинное? Точнее, что вообще понимается под его длиной?

Сообщение от Igor3D

Идея с системой которая "самобалансируется" конечно красивая. ... Но в данном случае - наверное нет

Насколько мне известно, она вполне успешно используется. Вроде где-то даже демка была, как это работает. Если не ошибаюсь, это позволяет получить близкое к минимальному число пересечений в раскладказ графов.

@saroff · 04.01.2014, 16:08 **[ТС]**

Qwertiy, Наверное в данном случае под длинной понимался вес ребра... Не вижу в чем там может быть сложность т.к. еще не разбирался.
ПС вот нашел что-то наиболее похожее.

@Qwertiy · 04.01.2014, 19:07

Сообщение от saroff

Наверное в данном случае под длинной понимался вес ребра...

Для укладки графа вес ребёр не имеет никакого значения.

@Mysterious Light · 04.01.2014, 20:50

Сейчас перед нами стоит такая задача: нарисовать по-красивее неориентированный невзвешенный граф, расположив на плоскости вершины.
Ребра мы изображаем отрезками. Я ещё не видел (а в этой теме я не знаток) силовых методов, в которых ребра отталкивались бы друг от друга или изгибались бы. Пример несилового алгоритма с изгибающимися ребрами, который я не могу не упомянуть, Метод связывания ребер.

Давайте посмотрим на ссылку, предложенную ТС. В ней говорится, между всего прочего, что притягивание стоит делать логорифмическим, паче линейного закона Гука. Между тем, и закон притягивания, и закон отталкивания могут быть любыми, лишь бы потенциальными.
К слову, можно ввести явно потенциал — функцию 2N переменных (N — число вершин), причем сила есть градиент потенциала (до знака). Например, потенциал системы Гук+Кулон выглядит так:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?U(\vec{r_1},\vec{r_2},\ldots,\vec{r_N}) \;=\; \sum_{i,j} \frac{e^2}{\| \vec{r_i}-\vec{r_j}\|} \;+\; \frac k2\sum_{\langle i,j\rangle} \left(\|\vec{r_i}-\vec{r_j}\| - l\right)^2$

первая сумма по всем вершинам, вторая — по связанным; $https://www.cyberforum.ru/cgi-bin/latex.cgi?e^2$ значит из статьи, k/2 является примерным (закон-то другой) аналогом .
Потенциал системы из статьи про модель Идеса выглядит так (первая сумма по несвязанным, вторая — по связанным)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?U(\vec{r_1},\vec{r_2},\ldots,\vec{r_N}) \;=\; \sum_{\langle\langle i,j \rangle\rangle} \frac{c_{rep}}{\| \vec{r_i}-\vec{r_j}\|} \;+\; \sum_{\langle i,j\rangle} c_{spring} \|\vec{r_i}-\vec{r_j}\| \left( 1 + \ln l - \ln \|\vec{r_i}-\vec{r_j}\| \right)$

Как только мы выписали потенциал, задачу можно сформулировать так: найти полный минимум функции. Задача минимизации функции известна и решаема. Отмечу, что потенциал как правило имеет очень большое число локальных экстремумов, поэтому о градиентном спуске (соотв. системе с бесконечным трением скольжения) стоит забыть. Зато всякие там генетические методы упоминаются часто.

Повторю, что в этом я не разбираюсь, но поэкспериментировать было бы занятно. Займусь, если только дойдут руки

@Igor3D · 04.01.2014, 21:28

Оказывается про длину ребра речь не идет - ну так еще лучше.

Сообщение от saroff

вот нашел что-то наиболее похожее.

Ну вот, барицентрик (наши в городе) - делайте, это будет точно работать.

По поводу "пружинок", "потенциальной энергии" и.т.п. Все это конечно здорово, но только если нет само-пересечений. А вот как их избежать - нигде ясно не звучит. Поэтому первый расклад лучше сделать методом барицентров (1.6), он этой проблемы не имеет. А потом (если останется энтузиазм) можно и с пружинками поиграться

@Qwertiy · 04.01.2014, 22:18

Сообщение от Mysterious Light

нарисовать по-красивее неориентированный невзвешенный граф

Взвешенность графа вообще ни на что не влияет. Это же просто подписи на рёбрах при необходимости.
Да и неориентированность тоже, за исключением того, что отсутствие кратных рёбер позволяет соединять вершины прямыми.

Сообщение от Igor3D

Все это конечно здорово, но только если нет само-пересечений. А вот как их избежать - нигде ясно не звучит.

Потому что их нельзя избежать, если граф не планарный.

Видел на каком-то сайте java-апплет-демку, где можно было понатыкать вершин и рёбер, нажать кнопку и посмотреть, как оно распрямится. К сожалению, понятия не имею, где ссылку искать...

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

Как нарисовать граф, имея 2-мерную матрицу

Решение

Решение

@saroff 5 / 1 / 2 Регистрация: 09.11.2013 Сообщений: 161

	Как нарисовать граф, имея 2-мерную матрицу 29.12.2013, 16:52. Показов 2916. Ответов 15 Метки нет (Все метки) На входе есть двумерная матрица смежности, нужно по нему нарисовать сам граф. Как это сделать - не представляю. Ведь вершин может быть и пять, и сорок пять. Понимаю, что нужно сделать так чтобы ни одни любые три вершины не находились на одной прямой, подскажите как это можно сделать. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	30.12.2013, 13:41
	Программно нарисовать или на бумаге? 0

@saroff 5 / 1 / 2 Регистрация: 09.11.2013 Сообщений: 161
	30.12.2013, 16:32 [ТС]
	Qwertiy, Прогамно, естественно) есть идея сделать алгоритм, который рандомом бы задавал положения вершин (т.е. координаты их на мониторе), а потом проверял, не находятся ли любые три из них на одной прямой и если находятся, то как нибудь изменял бы их. Но я не представляю как сделать эту проверку. 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,707 Записей в блоге: 14
	31.12.2013, 16:04
	А почему три вершины не могут быть на одной прямой? Что в этом страшного? 0

@saroff 5 / 1 / 2 Регистрация: 09.11.2013 Сообщений: 161
	31.12.2013, 16:49 [ТС]
	Mysterious Light, Если и делать движение, то как нибудь потом. Т.к. делается это все на канве в делфи, с которой постоянные проблемы. А за идею с окружность спасибо, покурю на досуге) 0

@saroff 5 / 1 / 2 Регистрация: 09.11.2013 Сообщений: 161
	04.01.2014, 02:20 [ТС]
	Qwertiy, Что то у меня наверное очередной затуп был... А можно какую нибудь статейку или еще чего по теме именно силовой реализации? Или хотя бы гуглопригодное название. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	04.01.2014, 04:13
	Не искал... Вроде должно нормально гуглиться по чему-то вроде раскладки графов. В общем, там идея простая. Берём и рассматриваем всё рёбра как одинаковые пружины, натянутые между шариками. От каждой такой пружины на шарик действует сила. Итерационным методом эмулируем перемещение. Стабилизировавшаяся система - это и есть раскладка. Чтобы не возникло колебаний, надо использовать затухание типа умножения на 0.9 на каждом шаге. 0

@Igor3D 1968 / 824 / 115 Регистрация: 01.10.2012 Сообщений: 4,870 Записей в блоге: 2
	04.01.2014, 10:44
	Сообщение было отмечено как решение Решение Идея с системой которая "самобалансируется" конечно красивая. Когда-то делал немного подобное и удивительно как быстро наступает состояние равновесия. Но в данном случае - наверное нет т.к. могут быть длинные ребра, пересекающие слишком много остального. Я бы сначала поставил самое длинное ребро, а потом бы присоединял новые вершины, немного похоже на триангуляцию Делоне, только др критерии 1

@saroff 5 / 1 / 2 Регистрация: 09.11.2013 Сообщений: 161
	04.01.2014, 16:08 [ТС]
	Qwertiy, Наверное в данном случае под длинной понимался вес ребра... Не вижу в чем там может быть сложность т.к. еще не разбирался. ПС вот нашел что-то наиболее похожее. 1

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	04.01.2014, 20:50
	Сейчас перед нами стоит такая задача: нарисовать по-красивее неориентированный невзвешенный граф, расположив на плоскости вершины. Ребра мы изображаем отрезками. Я ещё не видел (а в этой теме я не знаток) силовых методов, в которых ребра отталкивались бы друг от друга или изгибались бы. Пример несилового алгоритма с изгибающимися ребрами, который я не могу не упомянуть, Метод связывания ребер. Давайте посмотрим на ссылку, предложенную ТС. В ней говорится, между всего прочего, что притягивание стоит делать логорифмическим, паче линейного закона Гука. Между тем, и закон притягивания, и закон отталкивания могут быть любыми, лишь бы потенциальными. К слову, можно ввести явно потенциал — функцию 2N переменных (N — число вершин), причем сила есть градиент потенциала (до знака). Например, потенциал системы Гук+Кулон выглядит так: $https://www.cyberforum.ru/cgi-bin/latex.cgi?U(\vec{r_1},\vec{r_2},\ldots,\vec{r_N}) \;=\; \sum_{i,j} \frac{e^2}{\\| \vec{r_i}-\vec{r_j}\\|} \;+\; \frac k2\sum_{\langle i,j\rangle} \left(\\|\vec{r_i}-\vec{r_j}\\| - l\right)^2$ первая сумма по всем вершинам, вторая — по связанным; $https://www.cyberforum.ru/cgi-bin/latex.cgi?e^2$ значит из статьи, k/2 является примерным (закон-то другой) аналогом . Потенциал системы из статьи про модель Идеса выглядит так (первая сумма по несвязанным, вторая — по связанным) $https://www.cyberforum.ru/cgi-bin/latex.cgi?U(\vec{r_1},\vec{r_2},\ldots,\vec{r_N}) \;=\; \sum_{\langle\langle i,j \rangle\rangle} \frac{c_{rep}}{\\| \vec{r_i}-\vec{r_j}\\|} \;+\; \sum_{\langle i,j\rangle} c_{spring} \\|\vec{r_i}-\vec{r_j}\\| \left( 1 + \ln l - \ln \\|\vec{r_i}-\vec{r_j}\\| \right)$ Как только мы выписали потенциал, задачу можно сформулировать так: найти полный минимум функции. Задача минимизации функции известна и решаема. Отмечу, что потенциал как правило имеет очень большое число локальных экстремумов, поэтому о градиентном спуске (соотв. системе с бесконечным трением скольжения) стоит забыть. Зато всякие там генетические методы упоминаются часто. Повторю, что в этом я не разбираюсь, но поэкспериментировать было бы занятно. Займусь, если только дойдут руки 1