Hints for Lab 4

Topological Sort:

Colors translate to states of visiting an object. Say blue means unvisited and yellow means visited and red means processing a visit (an object is not visited until it is output in order). Thus, we may want to mark objects as unvisited, visited, or being visited. The matlab implementation might be as follows:

   visited = zeros(1,nobjects);
   visiting = zeros(1,nobjects);
when visiting and object, say number 11, do this:
   visiting(11) = 1;
and when the object is visited do this:
   visited(11) = 1;
We will need a stack. We can put an object on a stack and take an object off a stack. A stack is implemented as a vector. To intialize a stack do this:
   stack = [];
To add an object, say 11, to a stack so this:
   stack = [11 stack];
To remove an object from a stack and use it do this:
   object = stack(1);
   stack = stack(2:length(stack));
We may assume all objects have a list of dependencies. Keep these lists in a matrix, one row per dependency list. Call the matrix dependencies. This matrix is intialized through the following:
   dependencies = input('matrix> ');
Let current be the 'current' object. To find the first dependency of current that has not been visited use this:
   i = 1;
   while dependencies(current,i) ~= 0 && visited(dependencies(current,i))
      i=i+1; 
   end

 

Minimum Cost Network:

The solution is built from nothing by considering cables in increasing order of cost and adding to the solution only those cables for which its end cities are not already connected by cables in the solution. To initialize a solution use this:

   solution = [];
Use an input matrix of 3 columns: the first column is a city, the second column is another city, the third column is the cost of connecting the first two cities with a transmission line. Call the matrix cables. use this to initialize cables:
   cables = input('matrix> ');
The potential transmission lines can be sorted in increasing order of cost as follows:
   cables = sortrows(cables,3);
Consider each potential transmission line in increasing order as follows:
   for i=1:size(cables,1)
      ...cables(i,..)
   end
The test to determine whether the transmission line should be added to the solution is the only tricky part. Assign group numbers to all cities with the following restriction: if two cities have the same group number they are already connected, otherwise not. Initialize the group vector as follows:
   group = 1:ncities;
When a cable is added to the solution the groups numbers of some of the cities (those with the same group number as one of the end cities) must be changed (to the group number of the other end city).
   g1 = group(cables(i,2));  % so the invariant holds on all iterations
   for k=1:ncities 
      if group(k) == g1; group(k) = group(cables(i,1)); end; 
   end