CS 351: Design of Large Programs
                --------------------------------

               Assignment # 2, Due Date  09/20/01
               ----------------------------------


The goal of this assignment is 
(i)  to gain familiarity/confidence in the use of the Standard Template
     Library (STL) containers, iterators, STL algorithms and function objects.
     
(ii) to make performance-sensitive choices in the use of containers and
     operations on them.

The two applications to be considered here are the graph connectivity problem
and Dijkstra's shortest path algorithm.

*******************************************************************************

Statement of Problem 1:
-----------------------
We are given an undirected graph represented as a set of all pairs of
adjacent vertices.
Your program should
(a) Determine if the graph is connected. If not connected, it should determine 
    the number of components in the graph and the vertices in each component.
(b) Given an arbitrary vertex, S, it should compute the number of hops
    to every vertex reachable from S.

************************************

Example
-------

               aa__________x1              tg_________tt
               /|          |                |
              / |          |                |
           r3/  |          |                |
             \  |          |                |
              \ |          |                |
               \|__________|m               s
              bq|  
                |
                |
                |
               ayz
   
The input file is
r3,aa		bq,aa		bq,m		m,x1		aa,x1
bq,ayz		r3,bq		tg,tt		s,tg   
      
************
The output of your program for part (a) should be 
Graph has 2 components 
{aa, x1, r3, bq, m, ayz}
{tg, tt, s}

************
For part (b), the program should prompt the user for the source vertex. If 
the user enters aa, the program should output
1 hop away:  r3 bq x1
2 hops away: m ayz

************************************
Experiment with different containers and operations for this part. Time your
program and only turn in (e-mail to your TA) the best working solution. Also,
e-mail a one or two page summary of the alternatives you explored and their
impact on performance.
For example, "I could have chosen a multimap to represent the graph but I
elected to use a map with the "mapped to"  component being a set/list, etc."
You may also wish to comment on any performance/memory tradeoffs that you
considered.


*******************************************************************************

Statement of Problem 2:
-----------------------

We are given an undirected but weighted graph (each edge has an associated 
cost.) 
A graph is usually represented as G = (V,E) where V is the set of vertices
(or nodes) and E is the set of edges (or links). (v1, v2) belongs to E 
if there exists an edge between vertices v1 and v2. 
(Since G is undirected, (v1, v2) is the same as (v2, v1). )  
cost(v1, v2) is the cost of traversing edge (v1, v2).

Given a source node, S, we need to find the shortest path from S to every
other node. For this purpose, the following algorithm first proposed by
Dijkstra needs to be implemented making liberal use of STL containers, etc.


tent[S] = 0;   		// tent designates cost of a tentative shortest path
tent[i] = infty, for i in V and  i!=S
T = V;

for (i=0 to |V|-1)   	// |V| denotes number of vertices in G (cardinality)
  find vm in T with minimum tent[vm];
  for each edge (vm, vx) with vx in T {
      if (tent[vx] > tent[vm] + cost(vm, vx)
          tent[vx] = tent[vm] + cost(vm, vx);  //path from S via vm is cheaper
  }
  T = T - vm;
}
     
************
The first line of the input file is the source node, S,  followed by the 
destination, D. Then, each edge is represented by a triplet, the first two
elements are the nodes on which it is incident (as in Problem 1), 
the third element of the triplet is the edge cost.

************
The output should identify the shortest path from S to D and its cost.