How to detect a particular type of cycle in a directed graph?

Question

I am using NetworkX to analyse some directed graphs and their properties, but I'm stuck with a particular example. Let's consider a simple digraph:

  1 -----> 2
 /          \
F            M
 \          /
  3 -----> 4

This graph can be constructed with networkx:

graph = networkx.DiGraph()
graph.add_edges_from([("F", 1), (1, 2), (2, "M"), ("F", 3), (3, 4), (4, "M")])

Let's call the node F the fork node and M the merge node. All edges are unidirectional, and go from the left to the right.

I would like to detect a particular case of cycles that start within the "fork section" (i.e. between the fork and the merge nodes) but end outside of it. Let's call them invalid cycles. We can create such a cycle by adding an edge from node 4 to node F:

    1 -----> 2
   /           \
  F             M
/  \           /
\   3 -----> 4
 \          /
  <---------    

The new edge forms a feedback loop that starts between the nodes F and M, but ends outside of these nodes.

The two following examples, on the contrary, are valid:

The feedback loop starts and ends outside nodes `F` and `M`:
    1 -----> 2
   /           \
  F             M
/  \           / \
\   3 -----> 4   /
 \              /
  <-------------

The feedback loop starts and ends between nodes `F` and `M`:
  O -----> O
 /           \
F             M
 \           /
  O -----> O
   \      /
    <-----    

My main question is: how can I detect this kind of cycles? I don't need to retrieve the nodes part of the cycle, I only need to know that the graph has such a cycle. My graphs are not very large so I'm not concerned with performance.

Auxiliary questions: How to find the merge node corresponding to a given fork node in a potentially larger graph where there are multiple forks? Is there a name for such cycles? Do these cycles have some special properties?

Answer 1

It seems odd to talk about the start and end of a cycle. Cycles go around and around, with no start and no end.

I think what you mean is: cycles that contain some of the vertices between F and M, but neither of F nor M.

If I am correct about that then the algorithm is straighforward.

- Find all cycles in the graph
- LOOP C over all cycles
  - IF C contains some of the vertices between F and M, but neither of F nor M.
     - Add C to output.

Answer 2

1. Find all paths from F to M.
2. Let S be the set of nodes G ≠ M for which there is an edge F → G in such a path.
3. Delete M and all its edges from the graph.
4. For each G in S, find all paths from G to F.

The above algorithm finds every such cycle. If you just want to test whether or not the graph has any such cycle, then instead of step 4 you can do a breadth-first search in the reverse graph, from F until you find any node in S.