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.
The function of primary interest in this module is part_graph().
Other objects in the module may be of interest to those looking to mangle their graph datastructures into the required format. Examples of this include the networkx_to_metis() and adjlist_to_metis() functions. These are automatically called by part_graph(), so there is little need to call them manually.
See the BitBucket repository for updates and issue reporting.
It’s on PyPI, so installation should be as easy as:
pip install metis -or- easy_install metis
METIS itself is not included with this wrapper. Get it here.
Note that the shared library is needed, and isn’t enabled by default by the configuration process. Turn it on by issuing:
make config shared=1
Your operating system’s package manager might know about METIS, but this wrapper was designed for use with METIS 5. Packages with METIS 4 will not work.
This wrapper uses a few environment variables:
This wrapper uses Python’s ctypes module to interface with the METIS shared library. If it is unable to automatically locate the library, you may specify the full path to the library file in this environment variable.
The sizes of the idx_t and real_t types are not easily determinable at runtime, so they can be provided with these environment variables. The default value for each of these (at both compile time and in this library) is 32, but they may be set to 64 if desired. If the values do not match what was used to compile the library, Bad Things(TM) will occur.
>>> import networkx as nx >>> import metis >>> G = metis.example_networkx() >>> (edgecuts, parts) = metis.part_graph(G, 3) >>> colors = ['red','blue','green'] >>> for i, p in enumerate(parts): ... G.node[i]['color'] = colors[p] ... >>> nx.write_dot(G, 'example.dot') # Requires pydot or pygraphviz
Perform graph partitioning using k-way or recursive methods.
Returns a 2-tuple (objval, parts), where parts is a list of partition indices corresponding and objval is the value of the objective function that was minimized (either the edge cuts or the total volume).
Any additional METIS options may be specified as keyword parameters.
For k-way clustering, the appropriate options are:
objtype = 'cut' or 'vol' ctype = 'rm' or 'shem' iptype = 'grow', 'random', 'edge', 'node' rtype = 'fm', 'greedy', 'sep2sided', 'sep1sided' ncuts = integer, number of cut attempts (default = 1) niter = integer, number of iterations (default = 10) ufactor = integer, maximum load imbalance of (1+x)/1000 minconn = bool, minimize degree of subdomain graph contig = bool, force contiguous partitions seed = integer, RNG seed numbering = 0 (C-style) or 1 (Fortran-style) indices dbglvl = Debug flag bitfield
For recursive clustering, the appropraite options are:
ctype = 'rm' or 'shem' iptype = 'grow', 'random', 'edge', 'node' rtype = 'fm', 'greedy', 'sep2sided', 'sep1sided' ncuts = integer, number of cut attempts (default = 1) niter = integer, number of iterations (default = 10) ufactor = integer, maximum load imbalance of (1+x)/1000 seed = integer, RNG seed numbering = 0 (C-style) or 1 (Fortran-style) indices dbglvl = Debug flag bitfield
See the METIS manual for specific meaning of each option.
Convert NetworkX graph into something METIS can consume The graph may specify weights and sizes using the following graph attributes:
>>> G.edge['weight'] = 3 >>> G.node['quality'] = 5 >>> G.node['specialness'] = 8 >>> G.graph['edge_weight_attr'] = 'weight' >>> G.graph['node_weight_attr'] = ['quality', 'specialness']
If node_weight_attr is a list instead of a string, then multiple node weight labels can be provided.
All weights must be integer values. If an attr label is specified but a node/edge is missing that attribute, it defaults to 1.
If a graph attribute is not provided, no defaut is used. That is, if edge_weight_attr is not set, then 'weight' is not used as the default, and the graph will appear unweighted to METIS.
Rudimentary adjacency list converter. Primarily of use if you don’t have or don’t want to use NetworkX.
Note that all weights and sizes must be non-negative integers.