Identifying cyclic bubbles?

[fedarko]

Identifying cyclic bubbles?

[fedarko]

Coming back to this: a silly property (that I should have thought of earlier) is that these kinds of "cyclic bubbles" (when they are an isolated component of the graph) technically contain a chain from the end to the start node. The figure below shows that, depending on whether you identify the bubble or the chain first, the resulting decomposition looks different:

(I didn't draw it out in the figure, but the final step of the right side would be merging the chain and bubble into a cyclic chain. Also, the L and R subscripts indicate node splitting: see #167)

Notably, this is not the case when these bubbles are located within a chain of bubbles (i.e. when the start node has any other incoming edges, and/or when the end node has any other outgoing edges). Because in that case there is no longer a valid chain from the end to the start.

This means that we can't just say "oh, identify the chain first, then find the bubble, etc." -- because this will fail if this cyclic bubble exists in a chain of bubbles. So we have to make a choice -- do we continue to allow cyclic bubbles (which means that their decomposition in isolated components may look like either of the two figures above), or do we reject them completely?

I guess we can continue to allow cyclic bubbles for now. This isn't really a problem per se -- the fact that the decomposition is slightly inconsistent irks me, but it isn't really a bug (you could argue that either decomposition is meaningful -- in both cases we identify a bubble, anyway). My work on this project is already embarrassingly behind schedule as is.

Note that this also impacts cyclic frayed ropes (#242), when the connected end and start nodes have no non-pattern adjacencies. It doesn't impact cyclic chains since the "chain" from the end to the start of the cyclic chain is naturally a part of the cyclic chain anyway.