function [newG, curV]=preorder_by_GLF(G, preordered)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% General description:
%
% This function orders vertices using greedy largest first (GLF) algorithm, 
% that is, vertex v(k) is connected to more of v(1), v(2), ..., v(k-1) 
% than any of the vertices v(k+1), ..., v(n). Ties are broken by choosing
% the vertex with the most degree.
%
% See details in:
% M. Kubale and B. Jackowski. "A generalized implicit enumeration algorithm
% for graph coloring." Communications of the ACM, 28:412-418, 1985.
%
% input:
%       G(n,n) - The whole graph. If G(i,j)=1, then (i,j) is an edge in G
%       preordered - A subgraph that has already been ordered by GLF.
%
% output: 
%       newG(n,n) - Graph after ordered
%       curV - Indices of ordered vertices
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

deg=sum(G);
n=size(G,1);
[newdeg,idxV]=sort(deg,'descend');
InvVidx(idxV)=[1:n]; % inverse mapping of idxV

curV=preordered;
lb=numel(preordered);
for i=lb+1:n
    restV=[1:n];
    restV(curV)=[];
    
    % Find vertex connect most to preordered vertices, curV.
    degcur=sum(G(restV,curV),2);
    [tdeg,tidx]=sort(degcur,'descend');
    tpos=find(tdeg==max(tdeg));
    locs=restV(tpos);
    
    if length(locs)==1
        curV=[curV locs];
        continue;
    end
    
    % Breaking tie by choosing vertex with the most edges 
    td=InvVidx(locs);
    tt=find(td==min(td));
    loc=locs(tt(1));
    curV=[curV loc];     
end
newG=G(curV,curV);

