# 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.

[scsong@naradev05 ~/bin]$ ./kmetis5.0pre2 min_umiacs_d5.txt 30

**********************************************************************

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:

[scsong@naradev05 ~/bin]$ ./kmetis5.0pre2 min_umiacs_d5.txt 2

**********************************************************************

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

For your information, I uploaded the graph file at http://narawiki.umiacs.umd.edu/twiki/pub/Main/WebArchiving/min_umiacs_d5.txt

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