2 %> Algorithm 21.4: Jarnik-Prim. Implementation of algorithm 21.4 of \cite Bier15-book
4 %> @note Tested with \ref run2120.m
6 %> @author Michel Bierlaire
7 %> @date Sun Mar 29 17:54:11 2015
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
16 if (columns(adj) != nnodes)
17 error(
"Adjacency matrix must be square") ;
21 rightBank = setdiff(1:nnodes,leftBank) ;
22 while (size(leftBank) != nnodes)
29 if (cost(adj(i,j)) < c)
38 printf(
"Disconnected network. No edge between\n") ;
39 printf(
"%d\t",leftBank) ;
41 printf(
"%d\t",rightBank) ;
43 error(
"No spanning tree exists") ;
45 spanningTree = [ spanningTree ; theEdge] ;
46 leftBank = [ leftBank theNode] ;
47 rightBank = setdiff(1:nnodes,leftBank) ;
function jarnikPrim(in adj, in cost)
Identifies the minimum spanning tree of an undirected network.