I’m trying to find an algorithm for graphs with the following contents:
- Nodes with no edges leading out of them (shown here as a red circle)
- All other nodes have exactly two edges leading out (shown here as green diamonds)
I need to render these graphs a specific way:
- Each circle has a known position.
- Each diamond’s position is determined by the positions of the nodes it is connected to.
The data is arranged as shown, but to be clear
CircleNode : { Position }
DiamondNode : { NodeA, NodeB, Position = Route(NodeA, NodeB) }
Graph : { CircleNodes, DiamondNodes }
My solution works for most of the graphs I’ve constructed, but the more complex graphs I have overflow the stack long before they converge. I think I can use most of my existing code if I provide the nodes in depth last order – circles, then nearest diamonds, then next nearest to those, and so on. However, I’m not sure how to prove this will work for all graphs of this type.
What is this kind of problem called?
Is there a proven algorithm that can be applied?
Note: the diagrams above do not reflect the intended render layout, only how the data is represented in memory.
1) about stack overflow – if your algorithm will stop, but graph is too large, use explicit stack (on heap) instead of recursion.
One way (not the only way) to prove that it will stop someday, is that size of problem is reduced EACH “round” and that “round” itself is limited by some constant.
2)
You didn’t say how exactly should position of diamons be determined, so i will assume, that you want to node to be somewhere between nodes it connects to.
One way to do it would be something like simulated anealing:
place fixed nodes.
randomly place other nodes.
All nodes repulse other nodes (reduces with for example square of distance), nodes connected by edge are atracted (increases with square of distance).
Compute “forces” on all movable nodes. Move proportionaly to force and “time”.
At first start with larger time, each step reduce it.
To get out of local minima, add random force (and reduce it with time).
After some iterations stablepositions for nodes will be found and there is chance it will be reasonable.