mpp.m

Gaussian belief propagation code in matlab.

% MPP(A) runs depth-first search on an undirected graph to obtain a valid
% message passing protocol. By valid, we mean that a message is not sent
% from one node to another before the incoming messages have been sent. MPP
% returns a correct message passing protocol as long as the graph does not
% contain cycles. A is a sparse adjacency matrix, such that entry A(i,j) = 1
% means that vertices i and j are adjacent. Otherwise, A(i,j) = 0. The
% return value is a N x 1 struct array S, such that the uth entry S{u} says
% to send a message from vertex i to vertex j. Since the edges are
% undirected, A should be a symmetric matrix. We assume that the graph is
% fully connected. In other words, there is an undirected path between any
% pair of vertices in the graph.

function S = mpp (A)
  
  % Get the number of vertices and edges in the graph.
  n = length(A);
  m = sum(sum(triu(A)));
  
  % Initialize the message passing schedule (this is the return value).
  S = repmat(struct('i',0,'j',0),m,1);
  
  % The number of edges visited so far.
  m = 0;
  
  % Initialize the depth-first search queue to the first vertex in the
  % graph, and repeat as long as the queue is not empty.
  Q = 1;
  while length(Q)
    
    % Remove the first element from the queue.
    i = Q(1);
    Q = Q(2:end);
    
    % Repeat for every undirected edge leaving i.
    for j = find(A(i,:))
      
      % Add the edge (i,j) to the message passing schedule.
      m      = m + 1;
      S(m).i = i;
      S(m).j = j;

      % Add the vertex j to the queue.
      Q = [Q j];
      
      % Remove the edge from the graph so that we do not traverse it
      % again. 
      A(i,j) = 0;
      A(j,i) = 0;
    end
  end
  
  S = [revschedule(S); S];