Create a tree of the partitionment


I have a graph with 2^n vertices and few weighted edges. I would like to partition my graph in subsets of 2 vertices. For example, if my graph contains 32 vertices, I want to partition it in 16 sets of 2 vertices. Here comes my first question : I did some try with the ./parmetis binary on this example and it creates less than 16 partition (I called ParMETIS_v3_PartKWay). In this case, partitions 1, 7, 11 and 13 contain 3 vertices while partitions 9 and 15 don't exist. How can we explain that? I used this command line : ./parmetis my_test.graph 1 16 0 0 0 0

Next, I need to create a binary tree of the partitionment. Typically, with successive 2-way partitionment, I would like to create a tree. Is there a way to do this with ParMETIS? Otherwise, I could call several time ParMETIS and recreate a tree from the output. But it implies that ParMETIS partitions the graph in 2 subsets, then each of them in 2, etc... Is this hypothesis true?

Thx in advance and have a nice day!


RE: Graph embedding


I need to do some more tests case but it seems I can partition as I want. To do that, I used ParMETIS as a library in a C code and particularly, I used these parameters :

rset(graph.ncon, 1.01, ubvec);

With these values, when I ask n partitions, I get exactly n partitions with order/n vertices in each! :-)

Now, I need to do an embedding of my graph to another one. Does ParMETIS allow to do that natively?

RE: No.