nxmetis.partition

nxmetis.partition(G, nparts, node_weight='weight', node_size='size', edge_weight='weight', tpwgts=None, ubvec=None, options=None, recursive=False)[source]

Partition a graph using multilevel recursive bisection or multilevel multiway partitioning.

Parameters:
  • G (NetworkX graph) – An undirected graph.
  • nparts (int) – Number of parts to partition the graph. It should be at least 2.
  • node_weight (object, optional) – The data key used to determine the weight of each node. If None, each node has unit weight. Default value: ‘weight’.
  • node_size (object, optional) – The data key used to determine the size of each node when computing the total communication volumne. If None, each node has unit size. Default value: ‘size’
  • edge_weight (object, optional) – The data key used to determine the weight of each edge. If None, each edge has unit weight. Default value: ‘weight’.
  • tpwgts (list of lists of floats, optional) – The target weights of the partitions and the constraints. The target weight of the \(i\)-th partition and the \(j\)-th constraint is given by tpwgts[i][j] (the numbering for both partitions and constraints starts from zero). For each constraint the sum of the tpwgts[][] entries must be 1.0 (i.e., \(\sum_i \text{tpwgts}[i][j] = 1.0\)). If None, the graph is equally divided among the partitions. Default value: None.
  • ubvec (list of floats, optional) – The allowed load imbalance tolerance for each constraint. For the \(i\)-th and the \(j\)-th constraint, the allowed weight is the ubvec[j] * tpwgts[i][j] fraction of the \(j\)-th constraint’s total weight. The load imbalances must be greater than 1.0. If None, the load imbalance tolerance is 1.001 if there is exactly one constraint or 1.01 if there are more. Default value: None.
  • options (MetisOptions, optional.) – METIS options. If None, the default options are used. Default value: None.
  • recursive (bool, optional) – If True, multilevel recursive bisection is used. Otherwise, multileve multilevel multiway partitioning is used. Default value: False.
Returns:

  • objval (int) – The edge-cut or the total communication volume of the partitioning solution. The value returned depends on the partitioining’s objective function.
  • parts (lists of nodes) – The partitioning.
Raises:
  • NetworkXNotImplemented – If the graph is directed or is a multigraph.
  • NetworkXError – If the parameters cannot be converted to valid METIS input format, or METIS returns an error status.