function [r,ub, FC, last_ub, Ct, C] ...
    = coloring_forwards(r, G, C, Ct, FC, ub, last_ub,lower_bound)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function colors the vertices  sequentially within a prescribed 
% number of colors up to a vertex which cannot be colored because of a 
% lack of feasible colors, referred to as a 'resumption point'. 
% This function is called by graph_coloring.m. 
%
% 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:
%       r - starting point of coloring
%       G(n,n) - The whole graph. If G(i,j)=1, then (i,j) is an edge
%       C - The best coloring solution so far
%       Ct - A current coloring (partial or complete, C' in [Kubale])
%       FC - Feasible colors for vertices
%       ub - A upper bound on the chromatic number
%       last_ub - The previous upper bound, which is greater than ub. This
%                 is used to determine if a coloring for a new ub starts.
%       lower_bound - A lower bound on the chromatic number. Equal to the
%                     size of maximum clique 
% output: 
%       r - index of the 'resumption point'.
%       ub - A upper bound on the chromatic number
%       FC - Feasible colors for vertices
%       last_ub - The previous upper bound, which is greater than ub. This
%                 is used to determine if a coloring for a new ub starts.
%       Ct - A current coloring (partial or complete, C' in [Kubale])
%       C - The best coloring solution so far
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n=length(C);
lenFC=size(FC,2);
for i=r:n
    %
    % Only update FC when moving forward. 
    %
    if r<i % After a new sweep started, update FC of following vertices
        FC(i,:) = findFeasibleColors(G, Ct, ub-1, i, lenFC);
    elseif r==lower_bound+1 & ub~=last_ub
        %  To ensure create FC only when the first time a ub solution is
        %  seeked.
        last_ub=ub;
        FC(i,:) = findFeasibleColors(G, Ct, ub-1, i, lenFC);
    end
    
    if FC(i,1)==0 % the i-th vertex is out of feasible colors, 
                  % return it as the resumption point.
        r=i;
        return;     
    end
    
    Ct(i)=FC(i,1); % color the i-th vertex with the smallest feasible color.
end

% A new complete coloring has been found, and store the current coloring
C=Ct;
ub=max(C);

t=find(C==ub);
r=t(1); % least j such that C(j)=ub


