Помогитре разработать алгоритм или какую взять библиотеку для визуализации графа?
Здравствуйте. Задача состоит в визуальном представлении информации:
Имеется граф, который формируется случайным образом - просто появляется информация о существовании вершины графа и о том, кто её родители и кто по отношению к ней является дочерней вершиной. Граф ориентированный: У любой вершины кроме нескольких первоначально заданных имеется 1 или несколько родительских вершин. (Дочерних может не быть). То есть любая вновь появившаяся вершина имеет связь с 1 или несколькими старыми.
Задача: представлять это ввиде последовательного выростания графа горизонтально вниз из нескольких первоначальных вершин (Изначально вершины не связаны, но в процессе роста разделённые графы обязательно объединяются).
Его рост должен представляться таким образом, что дочерние вершины в визуальном представлении должны находиться ниже своего непосредственного родителя. Это условие не касается тех вершин, которые не имеют непосредственной связи. То есть, образно говоря, брат деда может оказаться ниже внука этого самого деда в угоду наглядности представления.
Есть ещё одно условие: в произвольные моменты времени может появиться связь между двумя случайно выбранными вершинами. Пусть это будет называться событием A. При появлении такой связи одна из вершин становится родителем, а другая дочерней. UPD (Связь может быть ориентирована только таким образом, чтобы не возникло замкнутой петли между вершинами)
Условие наглядности следующее: по мере роста графа визуально представлять его так, чтобы он имел минимальное количество пересечений между связями (не выглядел спутанным). А при возникновении события A, перерисовывать визуальное представление графа таким образом, чтобы вновь возникшая связь оказывалась не слишком длинной, и граф вновь имел минимальное количество пересечений связей, и вышеприведённое условие о том, что все дочерние вершины должны быть отрисованы ниже своих непосредственных родителей продолжало работать.
Прошу подсказать, существуют ли библиотеки для решения подобных задач на Python или javascript (Не решил, реализовывать расчёты координат вершин в браузере клиента или на бекенде, но предпочтительно рассчитывать их в браузере).
Или алгоритм отрисовки графа, или, по крайней мере, статьи и учебники, где бы освещались похожие задачи.
Кажется, метод Сугиямы, упомянутый в статье во второй ссылке - как раз то, что мне нужно.
Метод с пружинами инетересен, однако не гарантирует, что дочерние элементы будут находиться ниже материнских
Простой
