Author |
Topic: Knots (Read 5630 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Knots
« Reply #1 on: Nov 11th, 2012, 6:46am » |
 Quote  Modify
|
Neat. So you find the least tangled up way to display a graph? How efficiently does it work?
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Knots
« Reply #2 on: Nov 11th, 2012, 10:07pm » |
Quote Modify
|
I used a spring electric embedding to do it. Namely, i replaced edges with springs, and nodes with positive point charges. The electrostatic forces make the nodes want to spread out, while the spring forces make the nodes want to come together. We can then propagate forward the new particle positions and velocities by applying F = ma over small time increments. I stop the evolution when k iterations have been spent. The runtime is thus O( k n^2 ), where n = # of nodes. For the specific example in the screenshot, and k = 300, this took about .43 seconds on my computer.
By using the Barnes-Hut algorithm with quadtrees, we might be able to replace that n^2 with n log n. The main observations here are that:
1) nodes which are far away contribute negligible electrostatic force, and
2) nodes which are close by contribute negligible spring force.
So one can imagine decomposing 2D space into regions via a tree data structure such that we can efficiently determine which nodes are relevant to computing the force that I feel and which are not.
Another alternative stopping condition is to introduce damping coefficients and then stop when the total kinetic energy in the system falls below some threshold. Then "k" is replaced with the convergence time f(t,n) --- some function that is graph specific, but roughly proportional to n and inversely proportional to t. I am not sure what the asymptotic form of f(t,n) would be for a random connected graph.
Also, in practice I found that perturbing the forces by circularly symmetric random vectors improved performance greatly. My colleague Ken was of great help in vectorizing the code.
The problem is from the MATLAB programming contest --- my first time participating. In the twilight phase, my approach was scored 6th or 7th by author. However, the best submissions used algebraic graph theory, in which the second and third eigenvectors of the Laplacian matrix can provide natural coordinates for the vertices. This is non-iterative, and the performance in terms of crossing count and CPU time was far better.
|
| « Last Edit: Nov 11th, 2012, 10:14pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Knots
« Reply #3 on: Nov 12th, 2012, 8:05am » |
Quote Modify
|
I guess that if apply your method in 3D or 4D, it will have more space (literally) to unfold. You then need to project the solution by keeping the directions where the points spread more.
That could work well if the solution looks like your examlpe, close to a flat surface. If the solution is more like a tube, (that you need to spread out around a center) it could be a problem.
BTW what is the goal? Is it to minimize the number of remaining crossings?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
knots_demo_WWu.png