Allow graph to be directed

[Gabriel-in-Toronto]

Hi,

I'm interested in using this work as a basic building block in my research. However, I require the graphs to be directed, and edge contraction to be only limited to certain edges. So if I understand correctly, I will need to first add the directed option in function find_embedding, and also add restrictions to edge contractions.

Any suggestion on where might be the best place for me to make these two changes? Thanks!

[boothby]

Hello,

The changes you propose sound quite intrusive. To be perfectly honest, if I were to make the algorithm handle directed graphs, I would probably rewrite it from scratch.

Almost all of the work is done in the C++ library, under the include/find_embedding directory. In there, the "real work" is done in the find_chain function (and its dependencies) in the pathfinder class:

minorminer/include/find_embedding/pathfinder.hpp

Lines 345 to 371 in ff4935d

	//! after `u` has been torn out, perform searches from each neighboring chain,
	//! select a minimum-distance root, and construct the chain
	int find_chain(embedding_t &emb, const int u, int target_chainsize) {
	// HEURISTIC WACKINESS
	// we've already got a huge amount of entropy inside these queues,
	// so we just swap out the queues -- this costs a very few operations,
	// and the impact is that parent selection in compute_distances_from_chain
	// will be altered for at least one neighbor per pass.
	auto &nbrs = ep.var_neighbors(u, rndswap_first{});
	if (nbrs.size() > 0) {
	int v = nbrs[ep.randint(0, static_cast<int>(nbrs.size() - 1))];
	qubit_permutations[u].swap(qubit_permutations[v]);
	}
	prepare_root_distances(emb, u);
	// select a random root among those qubits at minimum heuristic distance
	collectMinima(total_distance, min_list);
	int q0 = min_list[ep.randint(0, static_cast<int>(min_list.size()) - 1)];
	if (total_distance[q0] == max_distance) return 0; // oops all qubits were overfull or unreachable
	emb.construct_chain_steiner(u, q0, parents, distances, visited_list);
	emb.flip_back(u, target_chainsize);
	return 1;
	}

But before you get there, as you mention, you'll need to add those options to find_embedding. I created a handy checklist for doing just that:

https://github.com/dwavesystems/minorminer/blob/main/parameter_checklist.txt