Coding Question on Acyclic Graph

The partition graph G n = (V, E) for an integer n ≥ 2 is an acyclic digraph where V is the vertex set and E is the edge set such that • v ∈ V represents a partition of an integer n. • An edge (v i , v j ) ∈ E represents that an element in the partition at v i is decomposed into two parts to obtain v j and thus the number of elements in the partition associated with v j = 1 + the number of elements in the partition associated with v i . Number of nodes in the partition graph G n is equal to the partition number of n. The partition graph G 7 for an integer n = 7 is shown in Figure 1. A node in a partition graph G n is represented as Node = hnodeId, partition, childListi. • nodeId: It corresponds to the unique id assigned to each node. It is represented as Node.nodeId. • partition: It represents the partition of an integer n. It is denoted as Node.partition. • childList: It denotes the list of nodeIds of all the nodes whose corresponding partitions are generated from partition. It is denoted as Node.childList. From the Uploaded Image Example:- The partition graph G 7 has 15 nodes. Let a node be Node = hId 3 , h5, 2i , {Id 5 , Id 6 , Id 8 }i. Here the nodeId corresponding to the given node is Id 3 . The partition corresponding to the given node is h5, 2i. childList contains nodeIds of the nodes whose corresponding partitions are generated from the partition h5, 2i. The partitions which are generated from h5, 2i are h5, 1, 1i, h4, 2, 1i and h3, 2, 2i. So childList contains the nodeIds of the nodes corresponding to these generated partitions and the corresponding nodeIds are Id 5 , Id 6 and Id 8 . To Find:- Given a positive integer n ≥ 3. Do the following in an efficient manner. 1. Generate the corresponding partition graph. 2. Count the total number of nodes and total number of vertices in the partition graph. 3. Count the number of nodes at each level. 4. Obtain all the tree edges 5. Obtain all the back edges 6. Obtain all the forward edges