[CSE2304] [progress]

### 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, `vi vj', which represents an edge from vi to vj. 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 {va, vb, ..., vi, vj} such that va->vb, ..., vi->vj, and vj->va 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 vi to vj (and from vj to vi) for every vi and vj?
[2 marks]

Total: [6 marks]

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

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