qiskit/transpiler/passes/mapping/dense_layout.py
def _best_subset(self, n_qubits):
        """Computes the qubit mapping with the best connectivity.

        Args:
            n_qubits (int): Number of subset qubits to consider.

        Returns:
            ndarray: Array of qubits to use for best connectivity mapping.
        """
        if n_qubits == 1:
            return np.array([0])

        device_qubits = self.coupling_map.size()

        cmap = np.asarray(self.coupling_map.get_edges())
        data = np.ones_like(cmap[:, 0])
        sp_cmap = sp.coo_matrix((data, (cmap[:, 0], cmap[:, 1])),
                                shape=(device_qubits, device_qubits)).tocsr()
        best = 0
        best_map = None
        # do bfs with each node as starting point
        for k in range(sp_cmap.shape[0]):
            bfs = cs.breadth_first_order(sp_cmap, i_start=k, directed=False,
                                         return_predecessors=False)

            connection_count = 0
            sub_graph = []
            for i in range(n_qubits):
                node_idx = bfs[i]
                for j in range(sp_cmap.indptr[node_idx],
                               sp_cmap.indptr[node_idx + 1]):
                    node = sp_cmap.indices[j]
                    for counter in range(n_qubits):
                        if node == bfs[counter]:
                            connection_count += 1
                            sub_graph.append([node_idx, node])
                            break

            if connection_count > best:
                best = connection_count
                best_map = bfs[0:n_qubits]
                # Return a best mapping that has reduced bandwidth
                mapping = {}
                for edge in range(best_map.shape[0]):
                    mapping[best_map[edge]] = edge
                new_cmap = [[mapping[c[0]], mapping[c[1]]] for c in sub_graph]
                rows = [edge[0] for edge in new_cmap]
                cols = [edge[1] for edge in new_cmap]
                data = [1]*len(rows)
                sp_sub_graph = sp.coo_matrix((data, (rows, cols)),
                                             shape=(n_qubits, n_qubits)).tocsr()
                perm = cs.reverse_cuthill_mckee(sp_sub_graph)
                best_map = best_map[perm]
        return best_map
def _best_subset(self, n_qubits):
        """Computes the qubit mapping with the best connectivity.

        Args:
            n_qubits (int): Number of subset qubits to consider.

        Returns:
            ndarray: Array of qubits to use for best connectivity mapping.
        """
        if n_qubits == 1:
            return np.array([0])

        device_qubits = self.coupling_map.size()

        cmap = np.asarray(self.coupling_map.get_edges())
        data = np.ones_like(cmap[:, 0])
        sp_cmap = sp.coo_matrix((data, (cmap[:, 0], cmap[:, 1])),
                                shape=(device_qubits, device_qubits)).tocsr()
        best = 0
        best_map = None
        # do bfs with each node as starting point
        for k in range(sp_cmap.shape[0]):
            bfs = cs.breadth_first_order(sp_cmap, i_start=k, directed=False,
                                         return_predecessors=False)

            connection_count = 0
            sub_graph = []
            for i in range(n_qubits):
                node_idx = bfs[i]
                for j in range(sp_cmap.indptr[node_idx],
                               sp_cmap.indptr[node_idx + 1]):
                    node = sp_cmap.indices[j]
                    for counter in range(n_qubits):
                        if node == bfs[counter]:
                            connection_count += 1
                            sub_graph.append([node_idx, node])
                            break

            if connection_count > best:
                best = connection_count
                best_map = bfs[0:n_qubits]
                # Return a best mapping that has reduced bandwidth
                mapping = {}
                for edge in range(best_map.shape[0]):
                    mapping[best_map[edge]] = edge
                new_cmap = [[mapping[c[0]], mapping[c[1]]] for c in sub_graph]
                rows = [edge[0] for edge in new_cmap]
                cols = [edge[1] for edge in new_cmap]
                data = [1]*len(rows)
                sp_sub_graph = sp.coo_matrix((data, (rows, cols)),
                                             shape=(n_qubits, n_qubits)).tocsr()
                perm = cs.reverse_cuthill_mckee(sp_sub_graph)
                best_map = best_map[perm]
        return best_map
Computes the qubit mapping with the best connectivity.

        Args:
            n_qubits (int): Number of subset qubits to consider.

        Returns:
            ndarray: Array of qubits to use for best connectivity mapping.