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

  • Thread starter SooEunKim
  • Start date
  • #1
2
0

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


Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
lewando
Homework Helper
Gold Member
1,349
135
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.
 
  • #3
2
0
Here is what I have tried.
I am still debugging some problems, but can anyone debug it?

This is for task1 btw.
 

Attachments

  • #4
lewando
Homework Helper
Gold Member
1,349
135
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:
%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:
Code:
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
 
Last edited:

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

Replies
1
Views
1K
  • Last Post
Replies
0
Views
2K
Replies
2
Views
806
Replies
5
Views
764
Replies
1
Views
766
  • Last Post
Replies
2
Views
291
  • Last Post
Replies
14
Views
4K
Replies
1
Views
732
  • Last Post
Replies
2
Views
4K
Top