Есть ли алгоритм, который дает мне координаты вершин в графе, когда я даю ему взвешенный граф, и вес ребер между вершинами указывает на расстояние между вершинами ?
Что-то вроде:
public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){ return _foo_; }
Обычно это невозможно: представьте себе граф с 3 узлами n1, n2 и n3.
Теперь рассмотрим следующие расстояния:
n1-n2: 4 n1-n3: 1 n2-n3: 1
(Это нарушает неравенство треугольника).
То, на что вы ссылаетесь, называется Многомерное масштабирование (MDS) , и вы должны найти множество реализаций, теперь вы знаете, как его искать.
Как и другие говорили, в некоторой степени невозможно нарисовать идеальный график, не нарушив некоторые из ваших ограничений (расстояния между точками). Алгоритмы MDS специально предназначены для минимизации таких нарушений.
ОК, я нашел библиотеку для python, и она создает графическое изображение для меня :), и я могу дать вес для ребер, например, атрибут: Вес ребра.В точке, чем тяжелее вес, тем короче, прямее и вертикальнее край.
Если график нарисован в евклидовом пространстве , вы не сможете этого сделать, потому что, как указано в в этом ответе , вы можете нарушить Неравенство треугольника .
Обычно вы можете визуально представить веса ребер, используя другой цвет (т.е. сопоставляя веса с цветовой картой), или используя разные толщины ребер (то есть, сопоставляя веса с масштабом толщины).).