Instantly share code, notes, and snippets.

# erikzenker/metis.cc

Created March 10, 2015 14:49
Show Gist options
• Save erikzenker/c4dc42c8d5a8c1cd3e5a to your computer and use it in GitHub Desktop.
Metis usage example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include /* NULL */ #include #include // Install metis from: // http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-5.1.0.tar.gz // Build with // g++ metis.cc -lmetis int main(){ idx_t nVertices = 6; idx_t nEdges = 7; idx_t nWeights = 1; idx_t nParts = 2; idx_t objval; idx_t part[nVertices]; // Indexes of starting points in adjacent array idx_t xadj[nVertices+1] = {0,2,5,7,9,12,14}; // Adjacent vertices in consecutive index order idx_t adjncy[2 * nEdges] = {1,3,0,4,2,1,5,0,4,3,1,5,4,2}; // Weights of vertices // if all weights are equal then can be set to NULL idx_t vwgt[nVertices * nWeights]; // int ret = METIS_PartGraphRecursive(&nVertices,& nWeights, xadj, adjncy, // NULL, NULL, NULL, &nParts, NULL, // NULL, NULL, &objval, part); int ret = METIS_PartGraphKway(&nVertices,& nWeights, xadj, adjncy, NULL, NULL, NULL, &nParts, NULL, NULL, NULL, &objval, part); std::cout << ret << std::endl; for(unsigned part_i = 0; part_i < nVertices; part_i++){ std::cout << part_i << " " << part[part_i] << std::endl; } return 0; }

Hi,

I'm not sure about the partition result that the code produces. If there are only 2 partitions, part[] must have its list elements as transpose[1,0,1,0,0,1......] showing that each vertex belongs to one of the 2 partitions, but instead the result is :

1
0 1
1 4294967296
2 4294967296
3 140725401232752
4 139695548220919
5 139693811302401

Upon giving nParts = 6;
the output comes:

Current memory used: 50522 bytes
Maximum memory used: 51228 bytes
***Memory allocation failed for SetupCoarseGraph: adjncy. Requested size: 18446744073709551592 bytes
-3
0 8589934592
1 4294967297
2 4294967297
3 140724707726896
4 139759668889079
5 139758235811841

with a little tweak in the code to validate correct initialization

std::cout << ret << std::endl;

``````for(int part_i = 0; part_i < nVertices; part_i++){
std::cout << part_i << " " << part[part_i] << " "  <<xadj[part_i+1] << std::endl;
}
``````

The result is:

1
0 0 2
1 1 5
2 4294967297 7
3 140720719165776 9
4 139778874488311 12
5 139775415681025 14

I'm not sure why the partition id in the list part [ ] would be such big numbers!

Restarting my system resulted in consistent output :

1
0 1 2
1 1 5
2 1 7
3 140732765458352 9
4 140419935229431 12
5 140419660775425 14

with first 3 elements parked in partitioned group 1.

### erikzenker commented Jun 4, 2019

I also saw weird behavior in metis but had no explaination so far. Did you come to an result? (sorry for the long delay!)

### biswa-git commented Jul 22, 2019

Works fine for me...
GCC-8
Linux

### Yingshiyu commented Jul 23, 2019

Works fine for me...
GCC-8
Linux

Why I also have this problem？How do you deal with it？
The result is
1
0 1
1 4294967296
2 4294967296
3 0
4 0
5 0
Thanks very well！

@Yingshiyu These high numbers in the partitioning array look like uninitialized memory. Best practice is to initialize memory before using it. Some platforms and compilers do it for you, this could explain the different result of you guys. I replaced the C arrays with proper initialized c++ vectors. Can you try again?

```#include <cstddef> /* NULL */
#include <metis.h>
#include <iostream>
#include <vector>

// Install metis from:
// http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-5.1.0.tar.gz

// Build with
// g++ metis.cc -lmetis

int main(){

idx_t nVertices = 6;
idx_t nEdges    = 7;
idx_t nWeights  = 1;
idx_t nParts    = 2;

idx_t objval;
std::vector<idx_t> part(nVertices, 0);

// Indexes of starting points in adjacent array

// Adjacent vertices in consecutive index order

// Weights of vertices
// if all weights are equal then can be set to NULL
std::vector<idx_t> vwgt(nVertices * nWeights, 0);

NULL, NULL, NULL, &nParts, NULL,
NULL, NULL, &objval, part.data());

std::cout << ret << std::endl;

for(unsigned part_i = 0; part_i < part.size(); part_i++){
std::cout << part_i << " " << part[part_i] << std::endl;
}

return 0;
}
```

### Yingshiyu commented Jul 23, 2019

@erikzenker
Thank you very much. But there are also have some problems when I use your code.
error: in C++98 'xadj' must be initialized by constructor, not by'{}'
error: could not convert{0,2,5,7,9,12,14} from to 'std::vector'

And I think this problem is related to the vector initialization(vector can not be initialized by {}). Therefore, I have modified it like:

idx_t a[nVertices+1]={0,2,5,7,9,12,14};

But the result is not change
1
0 1
1 4294967296
2 4294967296
3 0
4 0
5 0

Besides I cannot change nParts beyond 2.
My task is to use this API in my program, therefore, I want to try this API by a little example.
Thanks very much!

### erikzenker commented Jul 23, 2019

Which Compiler and oparating System are you using? Initialization with {} comes with c++11. I do not suggest to use c++98.

### Yingshiyu commented Jul 24, 2019

@erikzenker
OK, I have done it with -std=c+=11!
thanks very well!

### Yingshiyu commented Jul 24, 2019

@erikzenker
Sorry to disturb you again.
Your example can run on my computer and the answer is right. I want to ask are you suffer this problem?
If I am not declare vector like vector = {0,2,5,7,9,12,14}, because I don't know the size of this map or this map is too large.
Finally I output the value of vector is right. But there are some problems
munmap_chunk():invalid pointer:0x00000000013fdc70
or
free(): invalid size:0x0000000000lacccc0

Whether should I change the source code? I think it perhaps about 'new' and 'delete'?

I want to include this library/code in a makefile project, so how can I add the tag "-lmetis" at the compilation? I will be building the project using makefile.

### aavash1 commented May 25, 2021

Running METIS is really difficult as I am a newbie here and C language is not my programming language. And even though I am using the METIS manual, I haven't been able to run the program. I want to use the road network dataset to partition it. And maybe use the output file as the input in the Apache spark to achieve distributed processing. Anyone, could you please share the tutorial or something helpful so that I can follow the pattern or understand how to use it? PLEASE! HELP!