# kmetis partitioning

Hello,

I am a new user of kmetis and pmetis. I have used them successfully with relatively smaller graphs, but I have a problem when I try to partition a graph that has large variation in vertex weights.

Below are the results I see:

1. min_umiacs_d5.txt is a graph with 6453 vertices and 14137 edges. The sum of vertex weights is 3,018,915,564. The largest vertex weight is less than 100,000,000.

**********************************************************************
METIS 5.0 Copyright 2001-06, Regents of the University of Minnesota

Graph Information ---------------------------------------------------
Name: min_umiacs_d5.txt, #Vertices: 6453, #Edges: 14137, #Parts: 30

K-way Partitioning... -----------------------------------------------
***Cannot bisect a graph with 0 vertices!
***You are trying to partition a graph into too many parts!
***Cannot bisect a graph with 0 vertices!
***You are trying to partition a graph into too many parts!
***Cannot bisect a graph with 0 vertices!
***You are trying to partition a graph into too many parts!
***Cannot bisect a graph with 0 vertices!
***You are trying to partition a graph into too many parts!
30-way Edge-Cut: 0, Balance: -0.00

Timing Information --------------------------------------------------
I/O: 0.010
Partitioning: 0.020 (KMETIS time)
Total: 0.030
**********************************************************************

I only see '29' in the resulting output file, min_umiacs_d5.txt.part.30

2. Now I try to partition the same graph into only 2 partitions:

**********************************************************************
METIS 5.0 Copyright 2001-06, Regents of the University of Minnesota

Graph Information ---------------------------------------------------
Name: min_umiacs_d5.txt, #Vertices: 6453, #Edges: 14137, #Parts: 2

K-way Partitioning... -----------------------------------------------
2-way Edge-Cut: 0, Balance: -0.00

Timing Information --------------------------------------------------
I/O: 0.010
Partitioning: 0.010 (KMETIS time)
Total: 0.030
**********************************************************************

Again, I only see '1' in the resulting file, min_umiacs_d5.txt.part.2

Thank you very much in advance,

Sangchul Song

### RE: seems to be an idxtype overflow issue

Hi Sangchul,

It looks like you got integer overflow, I already had this kind of problems, you need to ensure that your weights are not
to "big" , because the total edge cut beeing the sum of the cutted edge's weights, it needs to fit into an integer, in this case I assume your using 32 bit integers, so you might try 5.0pre2 compiling it using idxtype as 64 bit integers and/or you need to normalize somehow your weigths to ensure total edge cut will always fit into idxtype size ...

note : by default idxtype is int32 : a signed type so currently your vertex weight sum effectively overflow this type ...

Vincent Juliard , Phd

### RE: That solved the problem

Hi Vincent,

As you pointed out, compiling with idxtype as int64 solved the problem. Thank you very much for your help.

Sang