In more software-friendly terms, the problem can be restated as this: Given a list of points and their connectivity as supplied by an adjacency matrix, move them around so that the lines do not cross.
You start with a network of connected nodes. Sometimes the edges between nodes intersect, as in the diagram below. We refer to these intersections as "knots."
You don't like knots. Every knot gives you a substantial penalty, so you want to make the knots go away. But you can't simply cut the connections with scissors. All you can do is move the nodes. Your job is to keep moving the nodes until there are as few crossings as possible (it may be impossible to remove all the knots). The image below has the same network topology as the image above, but one of the nodes has been moved to eliminate line crossings.
Now everything looks nice and tidy. But there's a complication. Beyond the knot penalty, you also have to pay to move nodes. So the goal is to minimize the overall cost: crossing penalty plus moving penalty.
Here is the syntax you will use.
xyOut = solver(a, xyIn, wts)
You are given a set of n nodes in the form of an n-by-2 matrix, xyIn. Each row corresponds to the (x,y) coordinates of a single node. The matrix a is the adjacency matrix defining the connectivity between the various points. The graph is undirected, so the adjacency matrix is guaranteed to be symmetric. wts is a vector that corresponds to how hard it is to move a given node. You must return the updated coordinates of all the points in xyOut. Each row in xyOut corresponds to the same row in xyIn. If you want to show that the nth point doesn't move, then xyOut(n,:) = xyIn(n,:).
The most important consideration is minimizing the number of crossings (knots). We will indicate number of knots with the variable nKnots. So to a first approximation,
Score = nKnots
As a tie-breaker among entries that all have the minimum number of knots, you should try to move the nodes as little as possible. We'll track that using a modification to the score. This modification depends on the weight vector wts, the distance vector dist (i.e. the distance moved by each individual node), and the maximum distance between any two points, max_dist.
sum(dist .* wts) / (max_dist*sum(wts))
Thus the overall scoring algorithm is...
Score = nKnots + sum(dist .* wts) / (max_dist*sum(wts))
Let's work through the example shown above. As mentioned, there are five nodes and two intersections, or knots. The nodes are numbered like so:
Here are the parameters for this problem.
xyIn = [ 1 5; 1 2; 3 1; 5 2; 5 5] a = [ 0 1 1 0 0; 1 0 0 1 0; 1 0 0 0 1; 0 1 0 0 1; 0 0 1 1 0] wts = [1 4 2 1 2]
Incidentally, you can visualize this problem with the gplot command like so.
Let's go ahead and find two values that show up repeatedly in the calculations below. The sum of all weights and the maximum distance between any two nodes.
sum(wts) = 1 + 4 + 2 + 1 + 2 = 10 max_dist = distance from node 1 to node 4 = sqrt( (5-1)^2 + (2-5)^2 ) = sqrt( 16 + 9 ) = 5
We're going to look at the score for each of three different scenarios to see which turns up the best score. But first, consider that not moving any nodes is an acceptable answer. Since there was no motion, the dist vector is [0 0 0 0 0]. But there are 2 knots, so the score is 2.
dist = [0 0 0 0 0] wts = [1 4 2 1 2] scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 2 + 0/(5*10) = 2
In this case we're shifting node 3 straight up a distance of two. It would be legal, but pointless, to move node 3 up a distance of one, since a node resting on a line between two other nodes counts as two knots.
dist = [0 0 2 0 0] wts = [1 4 2 1 2] scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + 4/(5*10) = 0.08
Suppose instead we move node 3 to the left 3 steps. This removes one of the knots, leaving one in place.
dist = [0 0 3 0 0] wts = [1 4 2 1 2] scoreB = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 1 + 6/(5*10) = 1.12
Clearly a bad idea.
Finally consider moving node 4 down two steps and to the left two steps as shown.
dist = [0 0 0 sqrt(8) 0] wts = [1 4 2 1 2] scoreC = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + sqrt(8)/(5*10) = 0.0566
This is the best result we've seen so far. Can you do better?
To become a player in the contest, follow this setup:
solver.musing the signature described above Syntax.
runcontest.mto test this function with the test suite in the zip file.
The overall score for your entry is a combination of several factors. Items 1 and 2 below are the most important factors. Items 3 and 4 have a milder effect.
Because the goal is to minimize each of these factors, the lowest overall score at the end of the contest wins.
Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number increases, understanding what's happening in a program becomes more difficult. This difficulty makes it harder to test, modify, and refactor.
Because a file can contain multiple functions, the complexity for any given file is defined as the maximum complexity of any functions contained within the file. A good practice is to keep the complexity for each function below 10. For the contest, your overall score increases according to complexity in excess of 10. No complexity penalty applies to submissions in which all functions have a complexity of 10 or less.
You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB
cyc switch for
checkcode, for example:
>> checkcode -cyc magic.m
Node count is a rough measure of the length of your code. Note that you are not penalized for comments and variable name length.
t = mtree(filename,'-file'); length(t.nodesize)
To keep the queue moving smoothly, we limit your code in the following ways:
After you submit an entry, you cannot change it. However, any player can view, edit, and resubmit an existing entry as a new entry. This rule means that you can view and copy any entry in the queue.
If you change an existing entry and improve its score, then you are considered the author of that entry when we determine contest winners. We encourage you to examine and optimize existing entries.
We also encourage you to discuss your solutions and strategies with others by posting to the contest thread on MATLAB Newsgroup. (See Resources.)
Allowable functions are those contained in the basic MATLAB package available in
$MATLAB is the MATLAB root directory. Functions from
other toolboxes are not available. All entries are tested against the latest version of
MATLAB. (See Resources.)
The following items are prohibited:
In consideration of all players, we ask that you do not abuse the system and follow these rules:
Check out these helpful resources:
Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest: