0

For a project I am working on I have some txt files that have from id's, to id's, and weight. The id's are used to identify each vertex and the weight represents the distance between the vertices. The graph is undirected and completely connected and I am using c++ and openFrameworks. How can I translate this data into (x,y) coordinate points for a graph this 1920x1080, while maintaining the weight specified in the text files?

Joe B
  • 1
  • 1
  • Any way software that generates an undirected graph and gives coordinate points will work also – Joe B Aug 01 '20 at 22:06
  • **This will not be possible in cases where the dimension of the graph is higher than 2.** The first thing you should do is verify that the graph dimension is not greater than 2. If it is greater than 2, then you can plot the graph, but only if you distort the lengths of edges. – C. Ventin Aug 01 '20 at 22:15
  • 1
    @M.Reeves the is only two dimensions. My issue is with plotting the graph itself. Do I just arbitrarily assign a coordinate value to one of the vertices and then plot the rest of the vertices relative to that one? – Joe B Aug 01 '20 at 22:43
  • (a) Is the graph known to be consistent in regard to the distances between vertices conforming to Euclidean geometry? If it is not consistent, it is impossible to assign coordinates to each point as desired. For example, if the A-B weight is 1 and the B-C weight is 1 and the A-C weight is 1000, it is impossible to position A, B, and C so the distances between them are in the proportions 1:1:1000. – Eric Postpischil Aug 02 '20 at 00:10
  • (b) By “completely connected,” do you mean that, for each pair of nodes A and B, there is an edge A-B? If so, the positioning is completely determined, aside from reflection and scale: Any three vertices form a triangle with sides of fixed length (up to scaling), so the entire graph layout is forced. – Eric Postpischil Aug 02 '20 at 00:11

1 Answers1

0

You can only do this if the dimension of the graph is 2 or less. You therefore need to determine the dimension of the graph--this is a measure of its connectivity. If the dimension is 2 or less, then you will always be able to plot the graph on a Euclidian plane while preserving relative edge lengths, as long as you allow the edges to intersect. If you prohibit intersecting edges, then you can only plot the graph on a Euclidian plane if the ratio of cycle size to density of cycles in the graph is sufficiently low throughout the graph (quite hard to compute). I can tell you how to plot the trickiest bit--cycles--and give you a general approach, but you actually have some freedom in how you plot this, so please, drop a comment or edit the question if you have a more specific request.

If you don't know whether you have cycles, then find out! Here are some efficient algorithms.

Plotting cycles. Give the first node in the cycle arbitrary coordinates. Give the second node in the cycle coordinates bounded by the distance from the first node. For example, if you plot the first node at (0,0) and the edge between the first and second nodes has length 1, then plot the second node at (1, 0). Now it gets tricky because you need to calculate angles.

Count up the number n of nodes in the cycle. In order for the cycle to form a polygon, the sum of the angles formed by the cycle must be (n - 2) * 180 degrees, where n is the number of sides (i.e., the number of nodes). Now you won't have a regular polygon unless all the edge lengths are the same, so you can't just use (n - 2) / n * 180 degrees as your angle. If you make the angles too sharp, then the edges will be forced to intersect; and if you make them too large, then you will not be able to close the polygon. Compute the internal angles as explained on StackExchange Math.

Repeat this process to plot every cycle in the graph, in arbitrary positions if needed. You can always translate the cycles later if needed.

Plotting everything else. My naive, undoubtedly inefficient approach is to traverse each node in each cycle and plot the adjacent nodes (the 'branches') layer by layer. Then rotate and translate entire cycles (including connected branches) to ensure every edge can reach both of its nodes. Finally, if possible, rotate branches (relative to their connected cycles) as needed to resolve intersecting edges.

Again, please modify the question or drop a comment if you are looking for something more specific. A full algorithm (or full code, in any common language) would make a very long answer.

C. Ventin
  • 135
  • 7