-
Notifications
You must be signed in to change notification settings - Fork 149
/
metis.go
137 lines (121 loc) · 3.79 KB
/
metis.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// Copyright 2016 The Gosl Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package gm
/*
#cgo CFLAGS: -O2
#cgo LDFLAGS: -L/usr/lib -L/usr/local/lib -lmetis
#include <metis.h>
*/
import "C"
import (
"unsafe"
"github.com/cpmech/gosl/chk"
"github.com/cpmech/gosl/utl"
)
// MetisShares returns a map of shares owned by vertices
// i.e. each vertex is shared by a number of edges, so,
// we return the map vertexId => [edgeIds...] attached to this vertexId
//
// Example:
// 0 1
// 0-------1--------2
// | | |
// 2| 3| 4|
// | | |
// 3-------4--------5
// 5 6
//
// Input. edges = {0,1}, {1,2}, {0,3}, {1,4}, {2,5}, {3,4}, {4,5}
//
// Output. shares = 0:(0,2), 1:(0,1,3), 2:(1,4)
// 3:(2,5), 4:(3,5,6), 5:(4,6)
// (notation. vertexID:(firstEdgeID, secondEdgeID))
//
// NOTE: (1) the pairs or triples will have sorted edgeIDs
// (2) len(shares) = number_of_vertices
//
func MetisShares(edges [][2]int) (shares map[int][]int) {
shares = make(map[int][]int) // [nverts] edges sharing a vertex
for k, edge := range edges {
i, j := edge[0], edge[1]
utl.IntIntsMapAppend(shares, i, k)
utl.IntIntsMapAppend(shares, j, k)
}
return
}
// MetisAdjacency returns adjacency list as a compressed storage format for METIS
// shares is the map returned by MetisShares
func MetisAdjacency(edges [][2]int, shares map[int][]int) (xadj, adjncy []int32) {
// total size of array
nv := len(shares)
szadj := 0
for vid := 0; vid < nv; vid++ {
szadj += len(shares[vid]) // = number of connected vertices
}
// data for METIS
xadj = make([]int32, nv+1)
adjncy = make([]int32, szadj)
k := 0
for vid := 0; vid < nv; vid++ {
list := shares[vid]
for _, eid := range list {
otherVid := edges[eid][0]
if otherVid == vid {
otherVid = edges[eid][1]
}
adjncy[k] = int32(otherVid)
k++
}
xadj[1+vid] = xadj[vid] + int32(len(list))
}
return
}
// MetisPartitionLowLevel performs graph partitioning using METIS
func MetisPartitionLowLevel(npart, nvert int, xadj, adjncy []int32, recursive bool) (objval int32, parts []int32) {
// output array
parts = make([]int32, nvert)
if npart < 2 {
return
}
if npart > nvert {
chk.Panic("number of partitions must be smaller than the number of vertices. npart=%d is invalid. nvert=%d\n", npart, nvert)
}
// set default options
noptions := int(C.METIS_NOPTIONS)
options := make([]int32, noptions)
opt := (*C.idx_t)(unsafe.Pointer(&options[0]))
C.METIS_SetDefaultOptions(opt)
// information
ncon := 1 // number of balancing constraints
npa := int32(npart)
nv := int32(nvert)
np := (*C.idx_t)(unsafe.Pointer(&npa))
n := (*C.idx_t)(unsafe.Pointer(&nv))
nc := (*C.idx_t)(unsafe.Pointer(&ncon))
xa := (*C.idx_t)(unsafe.Pointer(&xadj[0]))
ad := (*C.idx_t)(unsafe.Pointer(&adjncy[0]))
// output data
ov := (*C.idx_t)(unsafe.Pointer(&objval))
p := (*C.idx_t)(unsafe.Pointer(&parts[0]))
// call METIS
var status C.int
if recursive {
status = C.METIS_PartGraphRecursive(n, nc, xa, ad, nil, nil, nil, np, nil, nil, opt, ov, p)
} else {
status = C.METIS_PartGraphKway(n, nc, xa, ad, nil, nil, nil, np, nil, nil, opt, ov, p)
}
if status != C.METIS_OK {
chk.Panic("METIS failed\n")
}
return
}
// MetisPartition performs graph partitioning using METIS
// This function computes the shares, adjacency list, and partition by calling the other 3 functions
func MetisPartition(edges [][2]int, npart int, recursive bool) (shares map[int][]int, objval int32, parts []int32) {
shares = MetisShares(edges)
xadj, adjncy := MetisAdjacency(edges, shares)
nvert := len(shares)
objval, parts = MetisPartitionLowLevel(npart, nvert, xadj, adjncy, recursive)
return
}