Нарисуйте график, где расстояние между вершинами соответствует весу ребер

Есть ли алгоритм, который дает мне координаты вершин в графе, когда я даю ему взвешенный граф, а веса ребер между вершинами указывают на расстояние между вершинами?

Что-то вроде:

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, и она создает графическое изображение для меня:), и я могу дать веса для ребер, как атрибут: Вес ребра. В точке, чем тяжелее вес, тем короче, прямее и вертикальнее край.

Другие вопросы по тегам