Roughly how long should KWay partitioning take?

I've been using serial METIS for quite some time now. Currently using version 4.0.1 on my 2GHz Intel MacBook with 1GB RAM.

Just upped the size of my graph on Friday to 250K vertices and 500K edges. METIS seemed to stall at partitioning this into 18 clusters. I just killed it this morning after 53 hours. My previous graph, at 100K vertices and 200K edges, took 4 hours to run my entire algorithm, and METIS was called repeatedly (100's of times) during that 4 hours.

I just took my 250K node graph and started running it using the kmetis binary this morning.
I've been hung with this output for a while now:
misty-davies-computer:Case003percent18Clust mdavies$ ~/libs/metis/kmetis metistest.graph 18
METIS 4.0.1 Copyright 1998, Regents of the University of Minnesota

Graph Information ---------------------------------------------------
Name: metistest.graph, #Vertices: 249993, #Edges: 499628, #Parts: 18

K-way Partitioning... -----------------------------------------------

Also started a run using my previous 100K node graph inside my algorithm and METIS has been successfully called about a dozen times now.

Should I expect a significant jump in time for the 250K node graph? I'm not doing any hard disk swapping and I still have unused RAM during the larger run. I'm suspecting that something is wrong with the graph, but I'm not getting any error messages.


RE: This should take no more

This should take no more than a few minutes. Can you try the 5.0pre version of metis and see if the problem remains. If it does, please open an issue on flyspray and upload the graph to take a look what the problem may be.