Question about Metis

Hi,

I ran into a problem with METIS that it can not get a solution with the following problem (node # : 121 , edge #: 826). Following is the input file I used. Could anyone help suggest how to resolve this? Thanks!

121 826
118 119
4 5 6 7 8 9 10 12 13 14 15 16 19 20 21 22 23 24 26 27 28 29 30 35 36 37 39 46 48 50 51 54 60 67 69 70 71 72 73 80 81 87 88 89 90 93 95 96 100 102 111 113 114 115 118 119 121 122 123 124 125 129 130 131 134 135 137 138 139 140 142 143 148 149
3 13 19 20 26 30 35 48 52 53 70 80 104 105 110 111 112 119 123 129 134 137 138 140 143 148
3 7 14 15 18 19 24 31 44 51 69 71 80 116 118 119
3 22 26 29 35 36 37 47 91 93 104 111 121 125 129 134
3 5 8 14 15 18 19 31 42 44 48 51 54 71 77 80 85 118
3 7 14 15 16 18 19 24 31 42 43 44 48 51 77 80 85 93 116 118 119 148
3 35 37 51 54 67 71 96 100 124 139
3 20 35 41 82 98 103 111 137 142
3 24 35 37 39 67 71 80 82 86 87 93 110 111 130
3 4 27 82 90 111 129 137
3 5 7 8 15 16 18 19 31 44 69 77 80 118 119 120 137 141 143 148
3 5 7 8 14 16 24 31 37 42 43 48 51 69 77 80 118 119 143
3 8 14 15 19 31 43 44 45 69 71 80 116 118
5 7 8 14 19 31 53 61 77 80 85 98 103 118 119
3 4 5 7 8 14 16 18 31 32 40 42 43 44 45 48 57 69 71 80 81 85 96 103 111 116 118 119 120 124 134 139 140
3 4 10 27 34 37 39 67 77 82 89 111 131 134 137 142
3 22 24 37 39 48 54 71 88 111 114 123 130 137
3 6 21 26 28 29 35 37 43 48 52 53 70 80 91 93 102 104 111 118 121 122 125 129 131 137 145
3 26 35 57 70 104 111
3 5 8 12 15 21 35 37 48 51 54 71 82 111 119 124 134 135 139
48 49 55 79 107 141 146
3 4 6 22 23 28 29 52 53 70 73 82 91 111 121 129 143
3 13 20 34 35 39 50 67 82 83 89 90 111 137
3 22 26 29 35 52 91 129 131 135
3 6 22 26 28 35 36 37 70 72 73 98 102 121 122 125 129 131 142 145
3 4 35 48 111 113 141 143
5 7 8 14 15 16 18 19 32 42 43 44 45 63 69 80 85 93 103 116 117 118 119 120 133
19 31 45 80 116 117 120
20 27 35 39 40 41 46 51 83 86 89 90 96 115 137
3 4 6 9 10 12 22 23 24 27 28 29 30 34 36 41 54 67 72 73 80 82 86 87 88 93 95 96 100 102 104 111 113 114 121 122 123 125 129 130 131 134 135 137 142 145
3 6 29 35 37 72
3 6 9 12 15 20 21 22 24 29 36 51 54 67 71 72 77 121 125 131 134
3 12 20 21 27 34 46 47 60 67 83 89 90 95 115 137
19 34 41 86
10 34 35 40 51 82 86 93 142
7 8 15 19 31 44 63 69 80 116 118
8 15 16 19 22 31 44 45 63 69 80 116 118
5 7 8 14 16 19 31 42 43 45 63 69 80 85 116 118 119
16 19 31 32 43 44 63 69 80 85 116 117 120
3 34 39 83 90 137
6 39 57 73 121
3 4 7 8 15 19 21 22 24 25 30 49 53 57 71 79 80 81 85 107 111 119 129 131 134 135 139 140 141 143 146 148 149
25 48 55 107 141 146
3 27 67 71 82 90 111 114 124 137
3 5 7 8 9 15 24 34 37 41 54 67 71 77 80 86 96 100 114 124 139
4 22 26 28 53 61 83 98 110 111
4 18 22 26 48 52 56 57 64 70 80 93 98 109 110 111 141 143 148 149
3 7 9 21 24 35 37 51 71 96 100 114 124 139
25 49 79 107 141 146
53 98 109 134 149
19 23 47 48 53 85 90
137
3 39 90 137
18 52 98 103 109
31 42 43 44 45 80 116
53 98 109 110 111 131 149
3 9 12 20 27 35 37 39 50 51 71 82 86 111 114 115 124 130 137 139
3 5 14 15 16 19 31 42 43 44 45 80 116 118
3 4 22 23 26 29 53 72 93 102 104 111 115
3 5 7 9 12 16 19 21 24 37 48 50 51 54 67 77 80 88 96 100 103 111 114 119 124 130 134 135 137 138 139
3 29 35 36 37 70 102 121 125
3 26 29 35 47 125 145
7 8 14 15 18 20 37 51 71 80 116 139
25 48 55 107 141 146
3 4 5 7 8 12 14 15 16 18 19 22 31 32 35 42 43 44 45 48 51 53 63 69 71 77 81 85 93 98 103 111 116 117 118 119 120 135 143 148 149
3 19 48 80 85 111 134 148
10 12 13 20 24 26 27 35 41 50 67 83 89 104 137 140 142
27 34 39 46 52 82 137 140
7 8 18 19 31 44 45 48 57 80 81 116 148 149
12 34 35 40 41 51 67 96 114 115 124 130 139
3 12 35 115 130
3 21 35 71 92 114 123
3 20 27 34 39 82 137
3 13 27 34 39 46 50 57 60 137 139
6 22 26 28 104 125 129 145
88 93 114 123
3 6 8 12 22 31 35 41 53 70 80 92 111 118 129 131
3 35 39 115 130
3 9 19 34 35 51 54 71 86 114 134 139
10 18 29 52 53 56 61 64 80 109 110 111 119 122 124 129 138 142
3 9 35 51 54 71 124 139
3 22 29 35 70 72 121 145
10 18 19 31 61 71 80 116 123 124 134 139 140
4 6 22 23 35 70 82 91 111 121 125 129
4 135 141
25 48 49 55 79 141 146
53 56 61 64 98 138
4 12 52 53 64 98 111 113 142 149
3 4 6 10 12 13 19 20 21 22 23 24 26 27 30 35 48 50 52 53 64 67 70 71 80 81 93 98 104 110 113 119 123 129 130 131 134 135 137 138 140 142 143 146 148 149
4
3 30 35 110 111 142
3 21 35 50 51 54 67 71 86 88 92 96 123 135 138
3 34 39 67 70 86 87 95 130
5 8 16 19 31 32 42 43 44 45 63 69 77 80 85 103 119 120
31 32 45 80 120
1 3 5 7 8 14 15 16 18 19 22 31 42 43 44 69 80 93 119 120
1 3 4 5 8 14 15 18 19 24 31 44 48 71 80 98 111 116 118 129
14 19 31 32 45 80 116 117 118
3 6 22 26 29 35 37 47 72 102 104 131 145
3 22 29 35 98
3 4 21 35 88 92 103 111 114 137
3 9 19 24 50 51 54 67 71 86 98 100 103 137 139
3 6 22 29 35 37 72 73 91 104 129 131
3 4 6 13 22 26 28 29 35 48 91 93 98 104 111 119 125 131 142
3 12 21 35 67 71 86 87 95 111 115 131 137 142
3 20 22 28 29 35 37 48 64 93 111 121 125 129 130 142
31
3 4 6 19 20 24 35 37 48 56 71 81 96 103 111 135 139 140 142
3 24 28 35 48 71 80 105 111 114 134 137 148
3 4 10 13 14 20 21 22 27 34 35 39 46 50 58 60 67 71 82 83 89 90 111 123 124 130 135 140
3 4 71 98 109 111 114
3 9 19 24 48 51 54 67 71 77 86 90 96 100 103 124 134 143
3 4 19 48 82 83 103 111 134 137
14 25 30 48 49 53 55 79 105 107 143 146 149
3 10 20 29 35 41 82 98 110 111 113 129 130 131 134
3 4 14 15 26 30 48 53 80 111 139 141 146 148 149
22 29 35 73 91 102 121
25 48 49 55 79 107 111 141 143
3 4 8 14 48 53 80 81 85 111 135 143
3 48 53 56 64 80 85 110 111 141 143

RE: You can, but most likely you

You can, but most likely you will get trivial solutions (i.e., all nodes on one side...)

RE: The graph does not appear to

The graph does not appear to be undirected. That is, for each (u,v) edge you should also provide a (v,u) edge. Each row should correspond to the adjacency list of the vertex.

RE: Thank you so much for

Thank you so much for answering.
Another question comes with the partition results. The input graph is a undirected weighted graph. What is the interpretation that the Edge-Cut value is negative (e.g. -665)?

Thanks again.

RE: this is probably an overflow

this is probably an overflow (your edges have very large weights which overflow a 32 bit integer).

RE: Is there anyway to work

Is there anyway to work around the large weights problem?
It is noted in the tutorial that both edge-weights and vertex-weights should be integers greater
than zero. Thanks!

RE: Thanks. It seems that output

Thanks. It seems that output from Metis generates mostly equal sized clusters. Could I modify the objective only on MIN: sum(edge-cuts)? Thanks again!