Is it possible to calculate the x,y position of a node in a complete weighted graph with euklidic metric when i have the weight of every edge in the graph? it would be really usefull for me to plot such a graph... i coulnd find any algorithm which can do this :(
Get Point Cloud from Complete Weighted Graph
-
0Is the weight of each edge given by the Euclidean distance between the two vertices on that edge? – 2011-06-15
-
0yes it is... but i have some graphs were it isnt... i think it woulnd work there right? – 2011-06-15
3 Answers
Let me add detail to user6312's suggestion.
Because a triangle is rigid, you can start by finding three mutually connected nodes in your graph, embedding that in the plane (say, in some standard position: one vertex at the origin, one on the $x$-axis, one in the positive quadrant), and then building upon that triangle. Call the first triangle $(a,b,c)$. The building could be accomplished by selecting another node $p$ connected to $a$, $b$, and $c$, and computing its location from the distances $|ap|$, $|bp|$, $|cp|$. Intersecting the circles for two of those distances yields two possible locations for $p$, and the third distance can serve to disambiguate.
This type of problem has been considered by others, and there are various algorithms available. I imagine that there is also ready-made code available.
The following reference may give you a start. There weights are the Euclidean distances.
You could develop something on your own, based on straightforward analytic geometry. Do like surveyors do, compute the coordinates of a base triangle, preferably a fairly large one. Then the locations of the remaining points can be found by intersecting suitable circles. The algebra is not too bad.
However, there are more efficient ways to proceed, and if your graph is has a fair number of vertices, the naive geometric approach will be excessively slow.
Added: The base triangle should also be fairly round, the smallest angle should not be too small. This will improve the numerical stability of the algorithm.
-
0so if i understand you right, i take just three points out of my list and set for the first a pseduo coordinate e.g. (10,10). then i take another and set it on the same x axis with the distance weight and then the third node on the calculated point between a and b? – 2011-06-15
-
0I would put one point $P$ at $(0,0)$, another point $Q$ at $(d,0)$ where $d$ is the distance between $P$ and $Q$. The third point $R$ is put at the place $(a,b)$ which is at the right distances from $(0,0)$ and $(d,0)$. – 2011-06-15
-
0@reox (continued) There are two choices for $R$, pick one. After that, the locations of the remaining points can be computed using the base triangle $PQR$. But I still would advise using someone else's work. Professionals write highly optimized code, and take care of subtle side issues. – 2011-06-15
-
0i wrote some piece of code now, and its working someway :D yes best is to try somebody elses code, but mine is a little bit proove of concept anyway, this should work for me! thank you a lot! – 2011-06-22
-
0@reox: I am happy that you got some possibly useful ideas from the various responses. – 2011-06-22
Try neato from Graphviz.
-
0mhh is there any cool option? otherwise its not working really good.... – 2011-06-15