metis

package module
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 13, 2025 License: MIT Imports: 8 Imported by: 0

README

go-metis

Go bindings for METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering

Go Reference Go Report Card CI

Installation

go get github.com/notargets/go-metis

Requirements

  • METIS library (5.1.0 or later)
  • CGO-enabled Go installation
Installing METIS
Ubuntu/Debian
# Install dependencies
sudo apt-get install build-essential cmake

# Build from source
git clone https://github.com/KarypisLab/GKlib.git
git clone https://github.com/KarypisLab/METIS.git

cd GKlib
make config prefix=/usr/local
sudo make install

cd ../METIS
make config shared=1 prefix=/usr/local gklib_path=/usr/local
sudo make install
sudo ldconfig
macOS
brew install metis

Usage

package main

import (
    "fmt"
    "log"
    
    "github.com/notargets/go-metis"
)

func main() {
    // Simple 4-node graph (square)
    //  0 -- 1
    //  |    |
    //  2 -- 3
    xadj := []int32{0, 2, 4, 6, 8}
    adjncy := []int32{1, 2, 0, 3, 0, 3, 1, 2}
    
    // Partition into 2 parts
    part, edgeCut, err := metis.PartitionGraph(xadj, adjncy, 2)
    if err != nil {
        log.Fatal(err)
    }
    
    fmt.Printf("Partitioning: %v\n", part)
    fmt.Printf("Edge cut: %d\n", edgeCut)
}

Features

  • Graph partitioning (k-way and recursive)
  • Mesh partitioning
  • Matrix reordering
  • Graph coarsening
  • Nested dissection (coming soon)

Documentation

See GoDoc for detailed API documentation.

Examples

Check the examples directory for more usage examples.

Testing

go test -v ./...

License

This project is licensed under the MIT License - see the LICENSE file for details.

Note: METIS itself is licensed under the Apache License 2.0.

Documentation

Overview

Package metis provides Go bindings for METIS, a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.

METIS is developed by the Karypis Lab at the University of Minnesota and is widely used in scientific computing, particularly for parallel computing applications where load balancing and minimizing communication overhead are critical.

Overview

The package provides access to the main functionality of METIS:

  • Graph partitioning (recursive bisection and k-way)
  • Mesh partitioning (dual and nodal)
  • Nested dissection ordering for sparse matrices
  • Graph coarsening and refinement
  • Vertex separator computation

Installation

Before using this package, you must have METIS installed on your system: 

# Ubuntu/Debian
sudo apt-get install libmetis-dev

# macOS
brew install metis

# From source
git clone https://github.com/KarypisLab/GKlib.git
git clone https://github.com/KarypisLab/METIS.git
cd GKlib && make config prefix=/usr/local && sudo make install
cd ../METIS && make config shared=1 prefix=/usr/local && sudo make install

Then install the Go package: 

go get github.com/Notargets/go-metis

Basic Usage

Graph Partitioning

The most common use case is partitioning a graph for parallel processing: 

// Define a simple graph in CSR format
// Graph: 0-1-2
//        |X|X|
//        3-4-5
xadj := []int32{0, 2, 5, 7, 9, 12, 14}
adjncy := []int32{1, 3, 0, 2, 4, 1, 5, 0, 4, 1, 3, 5, 2, 4}

// Create options and use defaults
opts := make([]int32, metis.NoOptions)
metis.SetDefaultOptions(opts)

// Partition into 2 parts
part, edgeCut, err := metis.PartGraphKway(xadj, adjncy, 2, opts)
if err != nil {
	log.Fatal(err)
}

// part[i] contains the partition assignment for vertex i
fmt.Printf("Partition: %v, Edge cut: %d\n", part, edgeCut)

Graph Format

Graphs are represented in Compressed Sparse Row (CSR) format:

  • xadj: Index array of size n+1, where n is the number of vertices
  • adjncy: Concatenated adjacency lists
  • xadj[i] points to the start of adjacency list for vertex i
  • Vertices are numbered from 0 (C-style)

Example for a triangle graph (0-1-2-0): 

xadj   = [0, 2, 4, 6]    // Vertex 0 starts at 0, vertex 1 at 2, etc.
adjncy = [1, 2, 0, 2, 0, 1]  // Neighbors: 0->[1,2], 1->[0,2], 2->[0,1]

Weighted Graphs

Both vertices and edges can have weights: 

vwgt := []int32{10, 20, 30, 40}      // Vertex weights
adjwgt := []int32{1, 2, 1, 3, 3, 2}  // Edge weights

part, edgeCut, err := metis.PartGraphKwayWeighted(
	xadj, adjncy, vwgt, adjwgt, nparts, nil, nil, opts)

Mesh Partitioning

For finite element meshes, METIS provides specialized partitioning: 

// Define mesh connectivity
ne := int32(4)  // Number of elements
nn := int32(6)  // Number of nodes
eptr := []int32{0, 3, 6, 9, 12}  // Element pointer
eind := []int32{0, 1, 2, 1, 3, 2, 2, 3, 4, 3, 5, 4}  // Element-node list

// Partition mesh using dual graph (element-based)
objval, epart, npart, err := metis.PartMeshDual(
	ne, nn, eptr, eind, nil, nil, 3, 2, nil, opts)

Options

METIS behavior can be controlled through the options array: 

opts := make([]int32, metis.NoOptions)
metis.SetDefaultOptions(opts)

// Set specific options
opts[metis.OptionPType] = metis.PTypeKway      // Partitioning method
opts[metis.OptionObjType] = metis.ObjTypeCut   // Minimize edge cut
opts[metis.OptionNumBering] = 0                // C-style numbering
opts[metis.OptionSeed] = 42                    // Random seed
opts[metis.OptionDBGLvl] = 0                   // Debug level

Partitioning Methods

Two main partitioning approaches are available:

1. Recursive Bisection: Recursively splits the graph in half

  • Better for small number of partitions (2-8)
  • Often produces better quality partitions
  • Use: PartGraphRecursive()

2. K-way Partitioning: Directly partitions into k parts

  • Better for large number of partitions (>8)
  • Generally faster
  • Use: PartGraphKway()

Applications

Common use cases include:

1. Parallel Computing: Distribute computation across processors

  • Minimize communication (edge cut)
  • Balance computational load (vertex weights)

2. Finite Element Analysis: Partition meshes for parallel solvers

  • Element-based (dual) or node-based (nodal) partitioning
  • Minimize interface nodes/elements

3. Sparse Matrix Ordering: Reduce fill-in for direct solvers

  • Nested dissection ordering
  • Bandwidth/profile reduction

4. Graph Analytics: Process large graphs in parallel

  • Community detection preprocessing
  • Distributed graph algorithms

Performance Considerations

1. Graph Size: METIS handles graphs with millions of vertices efficiently

2. Memory Usage: Approximately O(n + m) where n = vertices, m = edges

3. Time Complexity: O(m) for most algorithms

4. Quality vs Speed: Options allow trading partition quality for speed

Error Handling

All functions return errors for invalid inputs or internal failures: 

part, edgeCut, err := metis.PartGraphKway(xadj, adjncy, nparts, opts)
if err != nil {
	switch err {
	case metis.ErrorInput:
		// Invalid input parameters
	case metis.ErrorMemory:
		// Insufficient memory
	default:
		// Other errors
	}
}

Thread Safety

METIS functions are not thread-safe. Concurrent calls must be synchronized externally. For parallel partitioning, create separate METIS instances or use locking.

References

For more information about METIS algorithms and options:

Based on METIS version 5.1.0 by George Karypis and Vipin Kumar.

Package metis provides Go bindings for the METIS graph partitioning library.

Index

Constants

View Source 
const (
	OK          = C.METIS_OK
	ErrorInput  = C.METIS_ERROR_INPUT
	ErrorMemory = C.METIS_ERROR_MEMORY
	Error       = C.METIS_ERROR
)

Error codes from METIS

View Source 
const (
	OptionPType     = C.METIS_OPTION_PTYPE
	OptionObjType   = C.METIS_OPTION_OBJTYPE
	OptionCType     = C.METIS_OPTION_CTYPE
	OptionIPType    = C.METIS_OPTION_IPTYPE
	OptionRType     = C.METIS_OPTION_RTYPE
	OptionDBGLvl    = C.METIS_OPTION_DBGLVL
	OptionNIter     = C.METIS_OPTION_NITER
	OptionNCuts     = C.METIS_OPTION_NCUTS
	OptionSeed      = C.METIS_OPTION_SEED
	OptionNo2Hop    = C.METIS_OPTION_NO2HOP
	OptionMinConn   = C.METIS_OPTION_MINCONN
	OptionContig    = C.METIS_OPTION_CONTIG
	OptionCompress  = C.METIS_OPTION_COMPRESS
	OptionCCOrder   = C.METIS_OPTION_CCORDER
	OptionPFactor   = C.METIS_OPTION_PFACTOR
	OptionNSeps     = C.METIS_OPTION_NSEPS
	OptionUFactor   = C.METIS_OPTION_UFACTOR
	OptionNumbering = C.METIS_OPTION_NUMBERING
	OptionHelp      = C.METIS_OPTION_HELP
	OptionTPWGTS    = C.METIS_OPTION_TPWGTS
	OptionNCommon   = C.METIS_OPTION_NCOMMON
	OptionNoOutput  = C.METIS_OPTION_NOOUTPUT
	OptionBalance   = C.METIS_OPTION_BALANCE
	OptionGType     = C.METIS_OPTION_GTYPE
	OptionUBVec     = C.METIS_OPTION_UBVEC
)

Options indices

View Source 
const (
	PTypeRB   = C.METIS_PTYPE_RB
	PTypeKway = C.METIS_PTYPE_KWAY
)

Partitioning types

View Source 
const (
	GTypeDual  = C.METIS_GTYPE_DUAL
	GTypeNodal = C.METIS_GTYPE_NODAL
)

Graph types

View Source 
const (
	CTypeRM   = C.METIS_CTYPE_RM
	CTypeSHEM = C.METIS_CTYPE_SHEM
)

Coarsening types

View Source 
const (
	IPTypeGrow    = C.METIS_IPTYPE_GROW
	IPTypeRandom  = C.METIS_IPTYPE_RANDOM
	IPTypeEdge    = C.METIS_IPTYPE_EDGE
	IPTypeNode    = C.METIS_IPTYPE_NODE
	IPTypeMetisRB = C.METIS_IPTYPE_METISRB
)

Initial partitioning types

View Source 
const (
	RTypeFM        = C.METIS_RTYPE_FM
	RTypeGreedy    = C.METIS_RTYPE_GREEDY
	RTypeSep2Sided = C.METIS_RTYPE_SEP2SIDED
	RTypeSep1Sided = C.METIS_RTYPE_SEP1SIDED
)

Refinement types

View Source 
const (
	ObjTypeCut  = C.METIS_OBJTYPE_CUT
	ObjTypeVol  = C.METIS_OBJTYPE_VOL
	ObjTypeNode = C.METIS_OBJTYPE_NODE
)

Objective types

View Source 
const (
	DBGInfo       = C.METIS_DBG_INFO
	DBGTime       = C.METIS_DBG_TIME
	DBGCoarsen    = C.METIS_DBG_COARSEN
	DBGRefine     = C.METIS_DBG_REFINE
	DBGIPart      = C.METIS_DBG_IPART
	DBGMoveInfo   = C.METIS_DBG_MOVEINFO
	DBGSepInfo    = C.METIS_DBG_SEPINFO
	DBGConnInfo   = C.METIS_DBG_CONNINFO
	DBGContigInfo = C.METIS_DBG_CONTIGINFO
	DBGMemory     = C.METIS_DBG_MEMORY
)

Debug levels

View Source 
const (
	NoOptions = C.METIS_NOPTIONS
)

Constants

Variables

This section is empty.

Functions

func CalculateEdgeCut 

func CalculateEdgeCut(g *Graph, part []int32) int32

CalculateEdgeCut calculates the edge cut for a given partitioning

func CalculatePartitionBalance 

func CalculatePartitionBalance(part []int32, vwgt []int32, nparts int32) (min, max, avg float64)

CalculatePartitionBalance calculates partition balance statistics

func ComputeVertexSeparator 

func ComputeVertexSeparator(xadj, adjncy, vwgt []int32, options []int32) (int32, []int32, error)

ComputeVertexSeparator computes a vertex separator from an edge separator

func MeshToDual 

func MeshToDual(ne, nn int32, eptr, eind []int32, ncommon int32) ([]int32, []int32, error)

MeshToDual converts a mesh to its dual graph

func MeshToNodal 

func MeshToNodal(ne, nn int32, eptr, eind []int32) ([]int32, []int32, error)

MeshToNodal converts a mesh to its nodal graph

func NodeND 

func NodeND(xadj, adjncy, vwgt []int32, options []int32) ([]int32, []int32, error)

NodeND computes fill reducing ordering using nested dissection

func PartGraphKway 

func PartGraphKway(xadj, adjncy []int32, nparts int32, options []int32) ([]int32, int32, error)

PartGraphKway partitions a graph using multilevel k-way partitioning

func PartGraphKwayWeighted 

func PartGraphKwayWeighted(xadj, adjncy, vwgt, adjwgt []int32, nparts int32, tpwgts, ubvec []float32, options []int32) ([]int32, int32, error)

PartGraphKwayWeighted partitions a graph with vertex and edge weights using k-way partitioning

func PartGraphRecursive 

func PartGraphRecursive(xadj, adjncy []int32, nparts int32, options []int32) ([]int32, int32, error)

PartGraphRecursive partitions a graph using multilevel recursive bisection

func PartGraphRecursiveWeighted 

func PartGraphRecursiveWeighted(xadj, adjncy, vwgt, adjwgt []int32, nparts int32, tpwgts, ubvec []float32, options []int32) ([]int32, int32, error)

PartGraphRecursiveWeighted partitions a graph with vertex and edge weights using recursive bisection

func PartMeshDual 

func PartMeshDual(ne, nn int32, eptr, eind []int32, vwgt, vsize []int32, ncommon, nparts int32, tpwgts []float32, options []int32) (int32, []int32, []int32, error)

PartMeshDual partitions a mesh using its dual graph

func PartMeshNodal 

func PartMeshNodal(ne, nn int32, eptr, eind []int32, vwgt, vsize []int32, nparts int32, tpwgts []float32, options []int32) (int32, []int32, []int32, error)

PartMeshNodal partitions a mesh using its nodal graph

func SetDefaultOptions 

func SetDefaultOptions(opts []int32) error

SetDefaultOptions initializes the options array with default values

func Version 

func Version() string

Version returns the METIS version

func WritePartitioning 

func WritePartitioning(w io.Writer, part []int32) error

WritePartitioning writes partition information to a writer

Types

type Graph 

type Graph struct {
	Xadj   []int32 // Index array for adjacency lists
	Adjncy []int32 // Adjacency lists (concatenated)
	Vwgt   []int32 // Vertex weights (optional)
	Adjwgt []int32 // Edge weights (optional)
}

Graph represents a graph in CSR format

func ConvertMeshToGraph 

func ConvertMeshToGraph(ne, nn int32, eptr, eind []int32, dual bool, ncommon int32) (*Graph, error)

ConvertToMetisGraph converts a mesh to a METIS graph for partitioning

func NewGraph 

func NewGraph(xadj, adjncy []int32) *Graph

NewGraph creates a new graph from adjacency information

func ReadGraphFile 

func ReadGraphFile(r io.Reader) (*Graph, error)

ReadGraphFile reads a graph in METIS format Format: Line 1: <# vertices> <# edges> fmt [ncon] Following lines: vertex adjacency lists (and optional weights)

func (*Graph) Degree 

func (g *Graph) Degree(v int) int

Degree returns the degree of vertex v

func (*Graph) Neighbors 

func (g *Graph) Neighbors(v int) []int32

Neighbors returns the neighbors of vertex v

func (*Graph) NumEdges 

func (g *Graph) NumEdges() int

NumEdges returns the number of edges in the graph (counting each edge once)

func (*Graph) NumVertices 

func (g *Graph) NumVertices() int

NumVertices returns the number of vertices in the graph

Source Files

View all Source files

Directories

Path Synopsis
examples
mesh command
partition command
simple command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.