Note

This is the documentation for the current state of the development branch of Qiskit Experiments. The documentation or APIs here can change prior to being released.

partition_nodes

partition_nodes(graph, distance, node_subset=None)[source]

Partition graph nodes into groups with minimum distance between nodes in each group.

Partitions the graph nodes into groups, such that in each group the minimum distance (number of edges in the shortest path) between nodes is at least distance.

Returns a list of list of list of integers, with the following explanation:

  • Each node label is encapsulated in a singleton list. This is in order to be consistent with groups of multiple nodes, like groups of edges.

  • Each group of nodes constitutes a list.

  • We return the list of groups. For example: [[[0], [2]], [[1]]] means two groups, one of nodes 0 and 2 and the other group contains only node 1.

If node_subset is not None then the partitioning contains only nodes that belong to node_subset.

Parameters:

  • graph (PyGraph) – A rustworkx.PyGraph instance

  • distance (int) – Minimum distance between nodes in the same group

  • node_subset (list | None) – Optional subset of nodes to partition

Returns:

List of groups of singleton node lists

Return type:

list

Note

This uses a greedy graph coloring algorithm. It may not produce the optimal (minimum number of groups) partitioning, but it’s simple and fast.