CSC 482/582: Fall 2016 Assignment #5
Due Mon. Dec. 5, 2016 at 11:55pm

Write a program to find voltage graphs (that could be non-uniform or uniform).

Input

The adjacency list format consists of:
<number of vertices>
Then for each vertex v:

<degree of v> <neighbours of v>

For this graph (which represents a 4-Venn diagram):

The input for this graph plus two of its automorphisms is given by:

 14
 4   1   2   3   4 
 4   0   4   5   2 
 4   0   1   6   7 
 4   0   7   8   9 
 4   0   9  10   1 
 4   1  10  11   6 
 4   2   5  12   7 
 4   2   6  12   3 
 4   3  12  11  13 
 4   3  13  10   4 
 4   4   9  13   5 
 4   5  13   8  12 
 4   6  11   8   7 
 4   8  11  10   9 

 2
 6  7 12  5  2  3  8 11 10  1  0  9 13  4
 7  6 12  3  2  5 11  8  9  0  1 10 13  4

The first permutation in cycle structure notation is:

( 0 6 8 10) ( 1 7 11 9) ( 2 12 13 4) ( 3 5)

The second permutation in cycle structure notation is:

( 0 7 8 9) ( 1 6 11 10) ( 2 12 13 4) ( 3) ( 5)

Output

To output the voltage graphs: The first entry is the number of vertices in the voltage graph. Then for each vertex, give the number of vertices in the original graph that it corresponds to (the cycle size), the out-degree of the vertex, and for each arc exiting the vertex, list the neighbour followed by the jump. For the sample input problem, the output is:

  4
 4  4   1  0      2  0      3  0      2  3
 4  4   0  0      2  3      3  1      2  0
 4  4   0  0      1  0      0  1      1  1
 2  4   0  0      1  1      0  2      1  3

  5
 4  4   1  0      2  0      3  0      2  3
 4  4   0  0      2  3      4  0      2  0
 4  4   0  0      1  0      1  1      0  1
 1  4   0  0      0  1      0  2      0  3
 1  4   1  0      1  3      1  2      1  1

Specifications