Final phase project 3:

Due Friday 19 May 2006 by Midnight

phase 1

phase 2<--broken

Bring your text book for the last week of lab.

For this phase you need to get just the 'S' command working

Here is some psuedo code outlining the spanning tree algorithm: 


// create helper structures
map<string, bool> component   // let's us know not to add the same vertex twice to the spanning tree
map<string, int> distance     // helps us decide which vertex to add inside the outer loop
map<string, string> neighbor  // when we add an edge we add from:v to:neighbor[v]

// initialize component to false and neighbor to the start_city for every vertex in the graph

// add entries to the distance map for every edge of the start_city, all other vertices are unreachable so far

// mark the start city entry in the component map true
// add the start_city to the spanning_tree

// make a local variable for the "current node being processed",
string v;

// The outer loop executes once for each vertex not in the spanning_tree
// so graph.size() - 1 times
for (.......)
{
        int min = INT_MAX;  // used to determine which non-component of the spanning tree is closest

/* 1 */ // first inner loop chooses which vertex should be added to the spanning_tree next
        for (every vertex in the distance map)
        {
            if (its not already in the spanning_tree (check component) &&
                its distance is less than min)
            {
                set v to this vertex;
                min = distance to v;
            }
        }

/* 2 */ // now that we have the next vertex to be added do so
        add v to component map;

        // add v to the spanning_tree graph
        spanning_tree.add(v);

        // add the edge from v to its neighbor in the neighbor map
        from = v
        to = neighbor[v]
        cost = distance[v]

/* 3 */ // now update the distance and neighbor maps
        for (iterate over the edge map for the last vertex added to the spanning_tree: v)
        {
            if (a vertex that is an adjacent to v is NOT already a part of the spanning_tree &&am;
                (
                  this vertex either has no entry in the distance map ||
                  we can get there with lesser cost from the last vertex just added
                )
               )
            {
                // update the cost entry in the distance map for this adjacent vertex to v
                // change the entry for this adjacent vertex in neighbor to v
            }
        }
}

return true;

For my script to score your work you must:

  1. put your files at the top level of your turn directory
  2. provide your own Makefile
  3. name your executable graph