Optimization: principles and algorithms, by Michel Bierlaire
jarnikPrim.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 21.4: Jarnik-Prim. Implementation of algorithm 21.4 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2120.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Sun Mar 29 17:54:11 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap21
10 
11 %> Identifies the minimum spanning tree of an undirected network.
12 %> @param adj the symmetric adjacency matrix of the undirected network. It is a \f$m \times m\f$ matrix, such that the element at row i and column j, and the element at row j and column i, contain to the id of the edge (i,j). The numbering should be from 1 to n.
13 %> @param cost a vector of size n containing the cost of each edge
14 function spanningTree = jarnikPrim(adj,cost)
15  nnodes = rows(adj) ;
16  if (columns(adj) != nnodes)
17  error("Adjacency matrix must be square") ;
18  endif
19  spanningTree = [] ;
20  leftBank = [1] ;
21  rightBank = setdiff(1:nnodes,leftBank) ;
22  while (size(leftBank) != nnodes)
23  c = realmax ;
24  theEdge = -999 ;
25  theNode = -999 ;
26  for i = leftBank
27  for j = rightBank
28  if (adj(i,j) != 0)
29  if (cost(adj(i,j)) < c)
30  c = cost(adj(i,j)) ;
31  theEdge = adj(i,j) ;
32  theNode = j ;
33  endif
34  endif
35  endfor
36  endfor
37  if (theEdge == -999)
38  printf("Disconnected network. No edge between\n") ;
39  printf("%d\t",leftBank) ;
40  printf("\n") ;
41  printf("%d\t",rightBank) ;
42  printf("\n") ;
43  error("No spanning tree exists") ;
44  else
45  spanningTree = [ spanningTree ; theEdge] ;
46  leftBank = [ leftBank theNode] ;
47  rightBank = setdiff(1:nnodes,leftBank) ;
48  endif
49  endwhile
50  endfunction
function jarnikPrim(in adj, in cost)
Identifies the minimum spanning tree of an undirected network.
Copyright 2015-2016 Michel Bierlaire