Finish 2012-11-07 16:00:00 UTC

toc toc

by Franck Dernoncourt

Status: Passed
Results: 77452 (cyc: 5, node: 498)
CPU Time: 0.823
Score: 77467.9
Submitted at: 2012-11-01 05:24:11 UTC
Scored at: 2012-11-01 17:16:00 UTC

Current Rank: 1674th (Highest: 15th )

Comments
Please login or create a profile.
Code
function xyOut = solver(a, xyIn, wts)

[x, y] = make_layout(a);
xyIn = remove_overlapping_nodes(round(vertcat(x, y)*30)');

xyOut = xyIn;

end


 function G = remove_overlapping_nodes(e)
 
[C, ia, ic] = unique(e,'rows');
D = setdiff(1:size(e, 1), ia);
if numel(D)>0    
    for i = 1:size(D)
        e(D(i),:) =   e(D(i),:) + [0 1];
    end
    e = remove_overlapping_nodes(e);
end

G=e;
 end

function [x, y] = make_layout(adj)
%  [x, y] = make_layout(adj)  Creates a layout from an adjacency matrix
%
% INPUT:   adj - adjacency matrix (source, sink)
% OUTPUT: x, y - Positions of nodes
%
% WARNING: Uses some very simple heuristics, any algorithm would do better 

N = size(adj,1);
tps = toposort(adj);
if ~isempty(tps),       % is directed ?
    level = zeros(1,N);
    for i=tps,
        idx = find(adj(:,i));
        if ~isempty(idx),
            l = max(level(idx));
            level(i)=l+1;
        end;
    end;
else
    level = poset(adj,1)'-1;  
end;
level;
y = (level+1)./(max(level)+2);
y = 1 - y;
x = zeros(size(y));
for i = 0:max(level),
    idx = find(level==i);
    offset = (rem(i,2)-0.5)/10;
    x(idx) = (1:length(idx))./(length(idx)+1)+offset;
end;
end

function [depth] = poset(adj, root)
% [depth] = poset(adj, root)   Identify a partial ordering among the nodes of a graph
% INPUT:   adj  -  adjacency matrix
%          root -  node to start with
% OUTPUT:  depth - Depth of the node
% Note     : All Nodes must be connected
adj = adj + adj';
N = size(adj,1);
depth = zeros(N,1);
depth(root) = 1;
queue = root;
while 1,
    if isempty(queue),
        if all(depth), 
            break; 
        else
            root = find(depth==0); 
            root = root(1);
            depth(root) = 1;
            queue = root;
        end
    end
    r = queue(1); queue(1) = [];
    idx = find(adj(r,:));
    idx2 = find(~depth(idx));
    idx = idx(idx2);
    queue = [queue idx];
    depth(idx) = depth(r) + 1;
end;
end

function [seq] = toposort(adj)
% [seq] = toposort(adj)  A Topological ordering of nodes in a directed graph
% INPUT:  adj  -  adjacency matrix 
% OUTPUT: seq  -  a topological ordered sequence of nodes
%                 or an empty matrix if graph contains cycles
N = size(adj);
indeg = sum(adj,1);
outdeg = sum(adj,2);
seq = [];
for i = 1:N,
    idx = find(indeg==0);    % Find nodes with indegree 0
    if isempty(idx),   % If can't find than graph contains a cycle
        seq = [];
        break;
    end;
    [dummy idx2] = max(outdeg(idx)); % Remove the node with the max number of connections
    indx = idx(idx2);
    seq = [seq, indx];
    indeg(indx) = -1;
    idx = find(adj(indx,:));
    indeg(idx) = indeg(idx)-1;
end 


end