Реализация пружинного / электростатического чертежа для графиков с заданной длиной ребра

Question

Предположим, у меня есть некоторый неплоский граф $ G $ с полностью заданными длинами ребер $ (r_1, ..., r_N) \ in R $, но у меня нет заданных координат для вершин.Я хочу нарисовать $ G $ на двухмерной поверхности, указав ребра как пружины некоторой длины, имея электростатическое отталкивание между вершинами, а затем выполняя что-то похожее на имитацию отжига.

Mathematica, кажется, обладает функциональностью для всего вышеперечисленного, но она не позволяет указывать длину ребер.Есть ли какое-либо программное обеспечение, находящееся в свободном доступе или нет, которое все это делает?Я пробовал Tulip и GraphViz.Tulip просто не позволяет указывать длину ребер, а Graphviz имеет очень ограниченные функциональные возможности с точки зрения задания длин ребер и установки любых параметров для этапа имитации отжига.

Обновление - я знаю об этом заранеечто мой конкретный набор длин ребер работает!График был ранее нарисован на двухмерной плоскости, но у меня нет доступа к координатам.

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

Answer 1

Как сказал Марк, не всегда можно делать то, что ты хочешь. Однако я бы предложил LevelScheme нарисовать волнистые стрелки, похожие на пружины. Вот пример:

<< "LevelScheme`"
pts = {{{0, 0}, {1, 1}}, {{0, 0}, {1, 1}}, {{1, 1}, {2, 0}}, {{2, 
     0}, {1, -1}}, {{1, -1}, {0, 0}}, {{0, 0}, {2, 0}}};
Figure[{
  SetOptions[SchemeArrow, ArrowType -> SquiggleArrow],
  SchemeArrow @@@ pts
  },
 PlotRange -> {{-0.1, 2.1}, {-1.1, 1.1}}
 ]

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

Answer 2

Нет причин ожидать, что сможет сделать это.Например, вы не можете разместить 4 точки на расстоянии друг от друга в плоскости.

Answer 3

ОК, обсуждение моего предыдущего ответа проясняет, что у OP есть длина ребер, которая работает. В этом случае задача может быть задана алгебраически, а затем решена. Вот один из подходов к этому. Конечно, всегда хорошо иметь конкретный пример, изложенный в вопросе. Не имея этого, мы можем сгенерировать основы примера.

Вот случайный граф с 10 вершинами и 20 ребрами.

SeedRandom[1];
g = RandomGraph[{10, 20}];

Давайте нарисуем это и извлечем информацию о местонахождении вершины. Таким образом, мы будем знать длины, которые работают.

pic = GraphPlot[g];
pts = pic[[1, 1, 1]];

Для любой конфигурации с такой длиной следующее выражение будет равно нулю.

length[UndirectedEdge[u_, v_]] := 
  Norm[pts[[u]] - pts[[v]]];
expr = Sum[((x[e[[1]]] - x[e[[2]]])^2 +
  (y[e[[1]]] - y[e[[2]]])^2 -
  length[e]^2)^2, {e, EdgeList[g]}];

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

vars = Flatten[Table[{
   {x[i], pts[[i, 1]] + RandomReal[{-0.4, 0.4}]},
   {y[i], pts[[i, 2]] + RandomReal[{-0.4, 0.4}]}},
  {i, 1, 10}], 1];

Теперь следующее должно дать работающие местоположения вершин.

FindMinimum[expr, vars]

Answer 4

Вы также можете попробовать реализовать это самостоятельно. Это не так сложно и очень весело. «Имитация отжига» в этом случае - просто применение электростатической физики с трением.

Ключевым моментом является использование Kd-Tree или Octree для ограничения сложности симуляции. Иначе O (n²) сложность победит вас:)

Answer 5

Может быть тюльпан делает что хочешь?