Draw a graph where the distance between the vertices corresponds to the weights of the edges

Question

Is there an algorithm that gives me the coordinates of the vertices in the graph when I give it a weighted graph, and the weight of the edges between the vertices indicates the distance between the vertices

Sort of:

public _ArrayOfCoordinatesForVertices_ **super_hyper_algorithm**(weighted_graph){ return _foo_; } 

Answer 1

This is not possible at all: imagine a graph with three nodes n1, n2 and n3.

Now consider the following distances:

 n1-n2: 4 n1-n3: 1 n2-n3: 1 

(This violates the quality of the triangle).

Answer 2

What you're talking about is called Multidimensional Scaling (MDS) , and you have to find many implementations, now you know how to look for it.

Like others, to some extent it is impossible to build a perfect graph without violating some of your limitations (distance between points). MDS algorithms are specifically designed to minimize such violations.

Answer 3

If a graph is drawn in Euclidean space , you cannot do this because, as indicated in this answer , you can violate Triangular inequality .

Usually you can visually display the weights of the edges using a different color (i.e., by matching the weights with a color map) or using different thicknesses of the edges (i.e. by matching the weights with a scale of thickness).

Answer 4

OK, I found a library for python, and it creates a graphic image for me :), and I can give weights for edges such as the attribute: Edge weight. More precisely, the heavier the weight, the shorter the straight and more vertical edge.