Reference no: EM13909990

You will write a program to count the number of non-isomorphic simple un-weighted directed graphs with a given number of vertices. The number of vertices will be specified at run time. A simple unweighted directed graph is a directed graph, without edge weights, such that there is never an edge from a vertex to itself. The program must be in the C language.

Pseudocode Your code will perform the following steps:

1. Let N be the number of vertices for the graphs - this is read from the command line.

2. Implement a data structure Graph that can hold a simple unweighted directed graph

3. Initialize GraphList to an empty list of Graph objects. A singly linked list will work.

4. Initialize a counter to zero.

5. Compute all the permutations of N, once, and store them in an array

6. Use the Odometer algorithm to enumerate all vertex-labeled simple unweighted directed graphs.

7. For each of these graphs, G:

(a) Use the list of permutations of N to check whether G is isomorphic to any graph in GraphList

(b) If G is isomorphic to any graph inGraphList, move on to the next graph.

(c) Otherwise add G to GraphList and increment the counter.

8. Print the final value of the counter to stdout

Invoking your program I will invoke your program in the following fashion. Assume that the executable is named program4.out.

program4.out N

N is the number of vertices of the graph. Your program will count the number of simple unweighted directed graphs with this number of vertices.

Evaluation I will evaluate your code by compiling and running it, and by also reading it. To receive full credit, your program must meet these criteria:

1. The program compiles cleanly, with no warnings or errors.

2. The program implements appropriate data structures

3. The program implements the pseudocode above correctly

4. The program does not need to be extremely optimized, but it is implemented in a reasonably efficient manner, as discussed in class.

5. The output is sent to stdout. The output clear and readable, but it does not need to match my output exactly.

6. The code itself follows good coding practices and is well commented without being over-commented. You can use the command cloc --by-file *.c to count the number of lines of code and number of lines of comments in your files.

When you use an internet reference, include a comment in the appropriate part of your code that gives the source

Attachment:- Assignment.rar