| Author |
Message |
    
Anonymous
Posted From: 137.248.121.165
| | Posted on Friday, April 08, 2005 - 04:33 am: | |
Hello,
my problem is that I want to partition a fully connected and weighted graph into k parts.
The first idea was to build MST and than delete k smallest edges; however this approach creates unbalanced results i.e. in my case parts consisting of only one node.
Now I'm using metis for the job; as I have the code in Java I have called in JNI both pmetis and kmetis but from what I see it doesn't take into consideration the weights at all.
E.g the graph
3 3 1
2 80 3 30
1 80 3 20
1 30 2 20
is partitioned into
1
0
1
whereas I would expect 1,1,0.
|
Anonymous
Posted From: 137.248.121.165
| | Posted on Friday, April 08, 2005 - 05:16 am: | |
Another question in this context;
How about floating point weights; as far as I saw they're not allowed. Will they be allowed in future versions ? |
george
Posted From: 128.101.32.74
| | Posted on Tuesday, April 19, 2005 - 06:23 am: | |
Metis does take into accoutn vertex weights. However, its heuristics tend to fail for very small graphs. I suggest you try a graph that has at 1000 or more vertices.
As far as fp weights, Metis does not support them. Sorry. |
|