Practical #4, semester 1, 2000
Group A: week 10, 8 May...
Group B: week 11, 15 May...

Write a C program to read a directed graph from standard input. The vertices are weighted. Each vertex has a name; you can assume this is less than 20 characters long and you can truncate any longer name. Each vertex also has a non-negative integer weight, e.g. a duration.

Vertices are given one per line. There is then a blank line, followed by the edges of the graph. Each edge consists of two vertices, `v_i v_j', which represents an edge from v_i to v_j. e.g.

   foundations 10
   frame 6
   roof 3
   bricks 4
    ... etc.
   plaster 5

   foundations frame        -- i.e. frame must follow foundations
   frame roof
    ... etc.

• All: Write a C program to read in the graph (checking its validity). If you wish, you can have a constant `MaxNumberVertices' in your program and can assume that it will be no more than 100.
  You will need to have some data structure to map vertex names (strings) onto vertex numbers and back again; a simple array of strings, possibly sorted, is adequate for this. (This is not an exercise in lookup tables.)
  [4 marks]
  
  
• Group A: Your program must print whether the graph is cyclic or not. i.e. is there a cycle {v_a, v_b, ..., v_i, v_j} such that v_a->v_b, ..., v_i->v_j, and v_j->v_a are edges in the graph?
  [2 marks]
  
  
• Group B: Your program must print whether the graph is fully connected or not, i.e. is there a path from v_i to v_j (and from v_j to v_i) for every v_i and v_j?
  [2 marks]
  
  

Total: [6 marks]

Your solution will be needed for the [next prac'].

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia