function clusterIdx = myNCuts (anAffinityMat, k)
%Implementation of the N-cuts algorithm
%   Usage clusterIdx = myNCuts (anAffinityMat, k), where:
%       Inputs
%       - anAffinityMat is a rectangular, symmetrical affinity matrix
%           representation of an image
%       - k is the desired number of clusters
%       Output
%       - clusterIdx is a vector storing the cluster Id of each node

    % Makes sure preconditions are met
    if ~issymmetric(anAffinityMat)
        error('The affinity matrix provided is not symmetric.');
    end
    if k < 2
        error('The number of clusters must be greater than two.');
    end

    % Calculates the eigenvectors
    D = diag(sum(anAffinityMat, 2));
    [eigenvectorsMatrix, ~] = eigs(double(D - anAffinityMat), double(D), ...
        k, 'sm');
    
    % Does the clustering using K-Means
    clusterIdx = kmeans(eigenvectorsMatrix, k);
end