1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 23, 2012 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations
    Aldous-Broder algorithm

    3. The attempt at a solution
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Dec 24, 2012 #2


    User Avatar
    Homework Helper
    Gold Member

    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.
  4. Dec 24, 2012 #3
    Here is what I have tried.
    I am still debugging some problems, but can anyone debug it?

    This is for task1 btw.

    Attached Files:

  5. Dec 25, 2012 #4


    User Avatar
    Homework Helper
    Gold Member

    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):
    Code (Text):

    %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;

    Code (Text):
    function [T] = USTsample_version_1(E)

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

        %establish empty set W
        W = [];

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

        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];
                    W = [W; u, v];
                V_visited(u) = 0;
            %v = u
             v = u;
            V_visited = [0,0,0,0]; %just to escape for now

    %setup T
    T = W;

    Last edited: Dec 25, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook