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
Hi, Yes i go through your description and i can get this done for you
I will get this done as per your requirement.
Please come over to chat we will discuss further.
waiting to hear back from you.
Thanks in advance.@
Regards
Ratnesh
This is a typical data structures problem, as the task is to create the partition graph some constraints must be imposed on the limit of the value for 'n' .I'm confident that I can provide you with a code in c++, once if the constraint on the value of n is manageable by me.
Checked you problem. Tried it and I am almost done with the task.
A developer with an experience of more than 6 years. Keen to solve problems.
Experienced in Java, OO Design principles. Believe in high performance and scalable code.