MATLAB code for Aldous-Broder algorithm from spanning trees of a graph

[SooEunKim]

Homework Statement

Let G = (V,E) be a graph with vertices V and edge set E.

Aldous-Broder algorithm:
Input: G = (V,E)
Output: T = (V, W), where W is a subset of E such that T is a spanning tree of G.

Let W be the empty set. Add edges to W in the following manner: starting at any vertex v in V,
1) If all vertices in V have been visited, halt and return T
2) Choose a vertex u uniformly at random from the set of neighbors of v.
3) If u has never been visited before, add the edge (u,v) to the spanning tree.
4) Set v, the current vertex, to be u and return to step 1.

1) Write a MATLAB function USTsample that takes a connected graph specified in the form of a 2-by-n matrix E, where n is the number of edges in the graph, and returns an output from the Aldous-Broder algorithm in the form of a 2-by-r matrix T, where r is the number of edges in the tree generated by the algorithm. Each row of E specifies the two vertices that constitute an edge: e.g. if G has an edge between the 5th vertex and 80th vertex, then either [5 80] or [80 5] (but not both) will be a row of E; T is a similar specification of the edges in the spanning tree. Note that we don't pass in or out the vertex sets: we assume that the vertices of G are 1 through m, where you can determine m as the largest number in E.

2) Write a script function that demonstrates your USTsample function:
- In one cell, specify K5, the complete graph on 5 vertices, in the form that USTsample takes as input, and use USTsample to return a spanning tree of K5
- In another cell, visualize K5 and its spanning tree in one plot. You will need coordinates for the vertices of the graph; according to your own preference, assign the coordinates by hand. Plot the vertices of the graph as red dots and the edges of G as gray lines of width 1. Plot the edges of T as thick red lines of width 2.
- Add two cells that repeat the above two steps (of calling USTsample and visualizing the output) for the grid graph on 10 vertices.

Homework Equations

Aldous-Broder algorithm

The Attempt at a Solution

 

[lewando]

In order to make any progress on this, you need to show what you have tried, and what, specifically, it is that is giving you troubles.

 

[SooEunKim]

Here is what I have tried.
I am still debugging some problems, but can anyone debug it?

This is for task1 btw.

 

[lewando]

Sorry, I couldn't deal with debugging what you had provided. So I hope you don't mind, but I took the liberty of reorganizing it, adding a commented structure, following the instructions provided more or less verbatim, not trying to pass V, adding a calling script, etc. Plus leaving you still with plenty to do.

Calling script (K4 complete graph to start):

%USTscript.m

%setup V (K4)
V = 1:4

%setup E (2xn for complete K4 graph)
n = 6;
E = zeros(2,n);

E(1,1)= 1;
E(2,1)= 2;

E(1,2)= 2;
E(2,2)= 3;

E(1,3)= 3;
E(2,3)= 4;

E(1,4)= 1;
E(2,4)= 4;

E(1,5)= 1;
E(2,5)= 3;

E(1,6)= 2;
E(2,6)= 4;

USTsample_version_1(E)

function:

function [T] = USTsample_version_1(E)

    %determine V, m
    m = max(max(E));
    V=1:m;

    %establish empty set W
    W = [];

    %pick a random v
    v = ceil(m*rand)

    %LOOP UNITL DONE
    V_visited = V; %(all elements non-zero. update element with a zero when visited)

    while sum(V_visited)~= 0
        %identify the set of neighbors at v
            %(you have some fun and add some code..)
       
        %pick a neighbor, u, uniformly at random
            %(you have some fun and add some code..)
            u = 3;
    
        %if V_visited(u) ~= 0, update W: add edge (v,u)
        if V_visited(u) ~= 0
            %per convention, specify edges (smallest_v, largest_v)
            if u > v
                W = [W; v, u];
            else
                W = [W; u, v];
            end
            
            V_visited(u) = 0;
        end
    
        %v = u
         v = u;
    
        V_visited = [0,0,0,0]; %just to escape for now
    end    

%setup T
T = W;

end