Removing loop dependencies from a directed graph with fixed edges

Question

I have a directed cyclic graph. Some ribs are FIXED and cannot be removed. Other edges can be removed to break the loop.

What is the best way to delete loops in this graph? The workaround should be as large as DFS and start with the given node.

Answer 1

I used the following algorithm to solve my problem:

Start by plotting all fixed edges marked as confirmed.

From the very beginning of the node, repeat all confirmed edges, as well as those not yet confirmed. But when you are going to reinstall an edge that has not yet been confirmed, first check to see if the node has the edge following the confirmed edges in the node in the current search tree (i.e. node with the visit flag set). This check should be done recursively, following all confirmed edges, but this is too slow for me, so I will stop here to check if the node is visiting or is connected to any of the nodes to which it is connected. This will cover most of my cases, but octave to leave cycles on the chart.

After the above step, I use the Tarjan algorithm to find the tightly coupled components remaining on the graph (this can be done in O (V + E)). The number of tightly coupled components will be very small in my cases, so I just go through each tightly coupled component and remove one removable edge. Then I do this step again until there are more cycles left on the chart.

It works fine and fast enough.

Answer 2

What you can do is use the Dijkstra algorithm: start with a graph containing only FIXED edges. Then apply the adaptation of the algorithm, starting with the existing chart:

• Start with the starting node and all the FIXED edges in the start node component. Suppose this is a tree.
• Add the node closest to the tree.
• Also add any FIXED edges to the newly added node component.
• If all nodes are in the tree, complete. Otherwise, go to step 4.

This, of course, assumes that a graph consisting only of FIXED edges does not contain loops. If so, then there is no solution (i.e., a subgraph without edges, but containing all FIXED edges).

For directed graphs this is a bit more complicated. In this case, any component of the graph of FIXED edges must be a tree. In a Dijkstra-like algorithm, only the roots of these nodes should be candidates that must be added to the tree.

Answer 3

the problem is underestimated because you did not specify, for example. if the graph must remain connected, or if you want to remove the "small" number of non-FIXED edges to break all the loops, or you really need the minimum minimum number of FIXED edges to be excluded globally.

If the graph should not remain connected, simply cross all the edges and remove all the non-fixed ones. This removes all loops that you can remove without removing the FIXED edges.

If you want a simple greedy algorithm to remove edges that are pure DFS, you can use something like this IF the graph remains connected when you delete some of the non-FIXED edges:

proc recurse(vertex n, vertex_set ns) if (n appers_in ns) // it is a cycle return BREAK_CYCLE else for (e in list_outgoing_edges_from(n)) np = e.destination result = recurse(np, add_to_set(ns, np)) if (result == BREAK_CYCLE) if (e.FIXED) return BREAK_CYCLE else [remove e from the graph] return RETRY else if (result == RETRY) return recurse(n, ns) return FINISHED if (recurse (your_initial_node, empty_vertex_set())) [graph contains a cycle through only FIXED edges] else [the reachable component from initial_node has no longer cycles]