title: Breaking cycles in a digraph with the condition of preserving connectivity for certain nodes
body: <p>I have a digraph consisting of a strongly connected component (blue) and a set of nodes (orange) that are the inputs to it. The challenge is to break as many cycles as possible with a minimum of removed edges. In addition, there must be a path from each orange node to each blue node.</p>
  <p><a href="https://i.stack.imgur.com/hOFWB.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hOFWB.png" alt="my graph" /></a></p>
  <p>I solve the problem with a brute force:</p>
  <ol>
  <li>Removing the random edge</li>
  <li>Check for a path from every orange node to every blue one. If everything is ok, I add an edge to the list and count the number of cycles.</li>
  <li>I return the edge to the graph and go to step 1 until I iterate over all the edges</li>
  <li>Next, from the resulting list (of length n) I generate combinations C (n, k) where k = {2 ... n}</li>
  <li>I perform operations 1, 2, 3 for all combinations of edges</li>
  </ol>
  <p>The core of the code looks like this:</p>
  <pre><code>    for level in range(2, len(edges)):
          stop = True
          edges2 = combinations(edges,level)
          for i, e in enumerate(edges2):
              g.remove_edges_from(e)
  
              test = True
              for node in orange_nodes:
                  d = nx.algorithms.descendants(g, node)
                  test = blue_nodes == d
                  if not test:
                      break
              if test:
                  stop = False
                  cycles_count = len(list(nx.simple_cycles(g)))
                  print(f'{i}\t{level}\t{cycles_count}\t{e}')
  
              g.add_edges_from(e)
  
          if stop:
              break
  </code></pre>
  <p>Questions:</p>
  <ol>
  <li>Is it possible to somehow optimize the code (nx.algorithms.descendants() and nx.simple_cycles() are dramatically slow)? Is it possible to rewrite code using <a href="https://en.wikipedia.org/wiki/Spanning_tree" rel="nofollow noreferrer">Spanning tree</a> or <a href="https://en.wikipedia.org/wiki/Feedback_arc_set#Minimum_feedback_arc_set" rel="nofollow noreferrer">Feedback arc set</a>?</li>
  <li>Maybe there is a fast search algorithm for not the best solution, but a good one?</li>
  </ol>
  <p><strong>Additionally:</strong>
  I rewrote the code as it is using the <a href="https://graph-tool.skewed.de/" rel="nofollow noreferrer">graph-tool</a>, which gave a ~20x...50x speed boost. But this still does not allow us to approach the set practical task =(</p>