metis is a Python wrapper for the METIS library for partitioning graphs (and other stuff).
This library is unrelated to PyMetis, except that they wrap the same library. PyMetis is a Boost Python extension, while this library is pure python and will run under PyPy and interpreters with similarly compatible ctypes libraries.
NetworkX is recommended for representing graphs for use with this wrapper, but it isn't required. Simple adjacency lists are supported as well.
Please see the full documentation for examples or the BitBucket repository for bug reports.