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