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