The project is to help the local authorities with their installation of security cameras at traffic intersections.
You will solve a particular kind of optimization problem, called the Vertex Cover problem, in this context. The idea is for the department to be able to minimize the number of cameras they need to
install, and still be as effective as possible with their monitoring.
For this you need to:
1. Take as input a series of commands that describe streets.
2. Use that input to construct a particular kind of undirected graph.
Sample Input
The input comprises lines each of which species a command. There are 4 kinds of commands.
(1) add a street, (2) change a street, (3) remove a street, or, (4) generate a graph. Here is an
example of how your program should work. Visualizing this example using the Cartesian coordinate
system may help you understand what's going on.
a "Weber Street" (2,-1) (2,2) (5,5) (5,6) (3,8)
a "King Street S" (4,2) (4,8)
a "Davenport Road" (1,4) (5,8)
g
V = {
1: (2,2)
2: (4,2)
3: (4,4)
4: (5,5)
5: (1,4)
6: (4,7)
7: (5,6)
8: (5,8)
9: (3,8)
10: (4,8)
}
E = {
<1,3>,
<2,3>,
1
<3,4>,
<3,6>,
<7,6>,
<6,5>,
<9,6>,
<6,8>,
<6,10>
}
c "Weber Street" (2,1) (2,2)
g
V = {
2: (4,2)
5: (1,4)
6: (4,7)
8: (5,8)
10: (4,8)
}
E = {
<2,6>,
<6,5>,
<6,8>,
<6,10>
}
r "King Street S"
g
V = {
}
E = {
}
Commands