
% Create the input matrix: adjacency matrix for the weighted graph of interest 
A0 = [0 1 0 4 0 0 0 0 0 0 0 0; 
     1 0 9 0 4 0 0 0 0 0 0 0; 
     0 9 0 0 0 5 0 0 0 0 0 0; 
     4 0 0 0 3 0 6 0 0 0 0 0; 
     0 4 0 3 0 7 0 5 0 0 0 0; 
     0 0 5 0 7 0 0 0 3 0 0 0; 
     0 0 0 6 0 0 0 7 0 6 0 0;
     0 0 0 0 5 0 7 0 2 0 2 0;
     0 0 0 0 0 3 0 2 0 0 0 1; 
     0 0 0 0 0 0 6 0 0 0 1 0;
     0 0 0 0 0 0 0 2 0 1 0 2;
     0 0 0 0 0 0 0 0 1 0 2 0;
    ];
% set n to be the unmber of nodes in the input graph
n = size(A0,1);
% MST is a variable that keeps track of the minimum spanning tree that we
% iteratively grow, and we initialize it to be the adjacency matrix of a
% graph with no edges
MST = zeros(n,n);
% infinity is a value we use as a surrogate for infinity
infinity = 10000;
% A is the adjacency matrix of current graph at certain iteration in the
% algorithm. We start from the input graph, and erase all the edges that
% are 1) added to the MST or 2) creates a cycle when added to MST
A=A0;
% We loop until MST has n-1 edges. 0.5*nnz(MST) is the half of the total
% number of non-zero entries in MST, which is the total number of edges in
% current MST
while ( 0.5*nnz(MST)<n) 
    % candidate is the candidate edge that we consideer adding to MST
    candidate = [0; 0;];
    % candidate_weight is the weight of the candidate edge
    candidate_weight = infinity;
    % for all possible pairs of nodes, we check if there is an edge
    % (A(i,j)>0) and if the weight is smallest in all candidate edges (A(i,j)<candidate_weight)
    for i=1:n-1 
        for j=i+1:n 
            if ( A(i,j)>0 & A(i,j)<candidate_weight) 
                % We set the candidate edge as the minimum weight edge in A
                candidate_weight = A(i,j);
                candidate = [i;j;];
            end
        end
    end
%% FILL IN THE MISSING PARTS STARTING FROM THIS LINE
% define and compute augmentT



% check if augmentT has a cycle

% if there is no cycle, let MST be augmentT and erase edge(candidate(1),candidate(2)) from A

% otherwise erase edge(candidate(1),candidate(2)) from A

%% END OF MISSING LINES
    % We stop when MST has n-1 edges.
    if (0.5*nnz(MST)==n-1) break; end
end
 
for inode=1:n-1
    for jnode=inode+1:n
        if(MST(inode,jnode)>0) 
            fprintf('(%i,%i),%i\n',inode,jnode,A0(inode,jnode));
        end
    end
end
