wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Knots
        
(Message started by: william wu on Nov 11^th, 2012, 4:47am)

Title: Knots
Post by william wu on Nov 11^th, 2012, 4:47am

This is my demonstration of knots being untangled.

Title: Re: Knots
Post by towr on Nov 11^th, 2012, 6:46am

Neat. So you find the least tangled up way to display a graph? How efficiently does it work?

Title: Re: Knots
Post by william wu on Nov 11^th, 2012, 10:07pm

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.

Title: Re: Knots
Post by Grimbal on Nov 12^th, 2012, 8:05am

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?

Title: Re: Knots
Post by william wu on Nov 12^th, 2012, 9:45am

The problem is: given the adjacency matrix for a graph, assign x-y coordinates for the nodes such that the total number of edge crossings is minimized.

(Full contest rules:
http://www.mathworks.com/matlabcentral/contest/contests/38/rules
In the description they also care about how much you moved the points relative to their original positions, but in practice I found edge crossing count and CPU time to be the dominating factors in the score.)