[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, `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