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
-
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.
-
0@reox: I am happy that you got some possibly useful ideas from the various respo$n$ses. – 2011-06-22
Try neato from Graphviz.
-
0mhh is there any cool option? otherwise its not working really good.... – 2011-06-15