nxmetis.node_nested_dissection

nxmetis.node_nested_dissection(G, weight='weight', options=None)[source]

Compute a node ordering of a graph that reduces fill when the Laplacian matrix of the graph is LU factorized. The algorithm aims to minimize the sum of weights of vertices in separators computed in the process.

Parameters:
  • G (NetworkX graph) – A graph.
  • weight (object, optional) – The data key used to determine the weight of each node. If None, each node has unit weight. Default value: ‘weight’.
  • options (MetisOptions, optional) – METIS options. If None, the default options are used. Default value: None.
Returns:

perm – The node ordering.

Return type:

list of nodes

Raises:

NetworkXError – If the parameters cannot be converted to valid METIS input format, or METIS returns an error status.