function m = makeVertexConnections( m )
%m = makeVertexConnections( m )
%   Construct m.nodecelledges, given that all of trinodevxs, edgecells,
%   edgeends, and celledges are valid.
%
%   m.nodecelledges is a cell array indexed by vertexes.
%   m.nodecelledges{vi} is a list of all of the edges and cells contacting
%   vertex vi, listed in the same order as are the vertexes of each cell.
%   Edges and cells alternate; in the sequence e c e', e and e' are edges
%   of c.  Where there is no cell between e and e' (because they are on the
%   edge of the mesh, c is zero.  If the node is on an edge of the mesh,
%   m.nodecelledges{vi} begins with an edge on the edge of the mesh and
%   ends with zero.

    numnodes = size(m.nodes,1);
    numcells = size(m.tricellvxs,1);
    m.nodecelledges = cell( numnodes, 1 );
    numwedges = numel(m.tricellvxs);
    wedges = zeros( numwedges, 4 );
    wi = 0;
    for ci = 1:numcells
        wi = wi+3;
        wedges((wi-2):wi, : ) = ...
          [ m.tricellvxs(ci,:)', ...
            [ci; ci; ci], ...
            m.celledges(ci,[3 1 2])', ...
            m.celledges(ci,[2 3 1])' ];
    end
    wedges = sortrows( wedges );
    wi = 1;
    while wi <= numwedges
        wj = wi+1;
        while (wj <= numwedges) && (wedges(wj,1)==wedges(wi,1))
            wj = wj+1;
        end
        m.nodecelledges{wedges(wi,1)} = makechains( wedges( wi:(wj-1), [2 3 4] ) );
        wi = wj;
    end
    validateChains( m );
end

function ch = makechains( r )
%ch = makechains( r )
%   R is an N*3 matrix representing a labelled relation: the row
%   [c e1 e2] represents an arrow from e1 to e2 labelled c.  The relation
%   is assumed to be either a set of linear chains, or a single cycle.  The
%   result is a representation of the chain as a list of alternate elements
%   and labels, in which the above instance of the relation will appear as
%   subsequence [... e1 c e2 ...].  Where the relation consists of more
%   than one chain, they will be separated from each other in the list by a
%   value of 0 (which is never the value of an element or label).
%   The result will begin with some ei and end with some c.
    
    relsize = size(r,1);
    items = unique(r(:,[2 3]));
    index = sparse(max(items),1);
    index(items) = 1:length(items);
    r(:,[2 3]) = full(index(r(:,[2 3])));
    maxr = max(max(r(:,[2 3])));
    mx = zeros(maxr,maxr);
    for i=1:relsize
        mx(r(i,2),r(i,3)) = i;
    end
    invalence = sum(mx,1);
    initials = find(invalence==0); % indexes into mx
    if isempty(initials)
        initials = 1;
    end
    ch = zeros(1,0);
    chi = 0;
    for i=1:length(initials)
        mistart = initials(i);  % index into mx
        mi = mistart;  % index into mx
        mj = find(mx(mi,:));  % index into mx
        ri = mx(mi,mj);  % index into r
        chi = chi+1; ch(chi) = items(r(ri,2));
        chi = chi+1; ch(chi) = r(ri,1);
        while mj ~= mistart
            chi = chi+1; ch(chi) = items(r(ri,3));
            mi = mj;
            mj = find(mx(mi,:));
            if isempty(mj)
                chi = chi+1; ch(chi) = 0;
                break;
            end
            ri = mx(mi,mj);  % index into r
            chi = chi+1; ch(chi) = r(ri,1);
        end
    end
    ch = reshape(ch,2,[]);
end
