2.2 Planning the Attack with Graph Theory!
You must submit this in an archive named "vertsep.zip".
Flavor text: Moroni must plan his attack on Amalickiah’s supply chains. But first he must determine what the bi-connected components, bridges, and separating vertices are to correctly target those important points.
You must implement an algorithm to compute the bi-connected components, bridges, and separating vertices of a graph.
Your program should accept a description of an undirected graph in the following format:
| ‹graph› | ::= | ‹integer› ‹edge›* |
| ‹edge› | ::= | ‹node› >- ‹weight› -> ‹node› |
| ‹node› | ::= | ‹integer› |
| ‹weight› | ::= | ‹integer› |
You may want to write a program to generate such inputs.
Separating Vertices: |
<node> ... |
|
Bi-connected Components: |
(<node> ...) |
... |
|
Bridges: |
(<node> -> <node>) ... |
You must test your program on graphs of at least 1000 nodes.
Your program must output the time it took to solve the problem (not read in the input and solve the problem.)
If you want to, follow these directions instead.