gflow(g) is not None, but extract_circuit(g) fails

[mafaldaramoa]

Hello,

I want to extract circuits from diagrams using extract_circuit. Before using this function, I make sure they are suitable for conversion by calling the gflow function which implements the algorithm by Perdrix and Mhalla. Since gflow is a necessary and sufficient condition for deterministic computation, I expect that a graph with (without) a gflow would be (not be) convertible.

However, this was contradicted by some graphs. This is the simplest example I could create to exemplify the problem:

The gflow function says that it has a gflow, but feeding this same graph to extract_circuit yields an error. The problem seems to be with gflow:

> print(gflow(graph))
({3: 0, 2: 1, 1: 2}, {2: {3}, 1: {2}}, 3)

Which isn't attributing a correction set to vertex 4.

I believe this is due to the gflow function only returning None (line 114) if the correct list is empty and the candidates list is not. Since the candidates list does not include vertices which, albeit not having an attributed correction set, do not have any neighbours in the set of possible correction vertices (line 96), it is possible that the gflow function returns something even though there are some (non-output) vertices which do not admit any correction set. And this something is not a valid gflow.

From my understanding of the algorithm, either candidates should include all non-output vertices which do not have an attributed correction set, or the gflow function should check whether all non-output vertices have an attributed correction set before returning (and return None if this is not the case). I don't know if there is something I'm missing.

[jvdwetering]

You are correct that this graph should not have a gflow. The gflow function has not been extensively used, so I'm not surprised there would be bugs in it.
@mafaldaramoa are you interested in trying to create a PR for a fix for this?