删除具有固定边的有向图的循环依赖性

I have a directed cyclic graph. Some edges are FIXED and may not be removed. The other edges may be removed to break a cycle.

我有一个有向循环图。某些边缘是固定的,可能无法移除。可以移除其他边缘以打破循环。

What is the best way to do remove the cycles in this graph? The traversal should be as much as a DFS as possible and start at a given node.

删除此图中的周期的最佳方法是什么?遍历应尽可能与DFS一样多,并从给定节点开始。

3 个解决方案

#1

What you can do is use Dijkstra's algorithm: start with a graph containing only the FIXED edges. Then apply an adaptation of the algorithm starting with the graph you already have:

你可以做的是使用Dijkstra算法:从仅包含FIXED边的图开始。然后应用从您已有的图表开始的算法改编:

Start with the starting node, and all FIXED edges in the component of the starting node. Assume this is a tree.

从起始节点开始,以及起始节点组件中的所有FIXED边。假设这是一棵树。

Add the node closest to the tree.

添加最接近树的节点。

Also add any FIXED edges in the component of the node you just added.

还要在刚刚添加的节点的组件中添加任何FIXED边。

If all nodes are in the tree, end. Otherwise, go to step 4.

如果所有节点都在树中,则结束。否则,请转到步骤4。

This, of course, assumes that the graph consisting only of the FIXED edges does not contain cycles. If it does, there is no solution (that is, a subgraph without edges, but containing all FIXED edges).

当然,这假设仅由FIXED边组成的图不包含循环。如果是,则没有解决方案(即没有边的子图,但包含所有FIXED边)。

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

对于有向图,它有点复杂。在这种情况下,FIXED边的图的任何组件都应该是树。在类似Dijkstra的算法中,只有这些节点的根应该是要添加到树中的候选者。

#2

the problem is understated because you haven't specified e.g. if the graph needs to remain connected, or if you want to remove a "small" number of non-FIXED edges to break all cycles, or if you really need the globally minimum number of non-FIXED edges to be removed.

问题是低估的,因为你没有指定例如如果图形需要保持连接,或者如果要删除“小”数量的非FIXED边缘以打破所有周期,或者如果您确实需要删除全局最小数量的非FIXED边缘。

If the graph does not need to remain connected, just traverse all the edges and remove all non-FIXED ones. That removes all cycles which you can remove without removing FIXED edges.

如果图形不需要保持连接,只需遍历所有边缘并删除所有未固定的边缘。这将删除所有可以删除的循环而不删除FIXED边。

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

如果你想要一个简单的贪婪算法去除纯DFS的边缘,你可以使用这样的东西如果图形在你移除一些非FIXED边缘时仍保持连接:

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]

#3

I used the following algorithm to solve my problem:

我使用以下算法来解决我的问题:

Start with a graph of all fixed edges marked as confirmed

从标记为已确认的所有固定边的图表开始

From a start node, recurse through all confirmed edges as well as the not-yet-confirmed ones. But when you're about to recurse down a not-yet-confirmed edge first check if the node that the edge goes to has a path, by following confirmed edges, to a node in the current search tree (i.e. a node with a visiting flag set). This check must be done recursively by following all confirmed edges but this is too slow for me so I will settle here to just check if the node is visiting or if any of the nodes it is confirmed connected to are visiting. This will cover most of my cases but occationally leave cycles in the graph.

从起始节点开始,递归所有已确认的边缘以及尚未确认的边缘。但是,当您即将递归尚未确认的边缘时,首先检查边缘所到达的节点是否有路径,通过跟踪已确认的边缘,到当前搜索树中的节点(即访问的节点)国旗集)。这个检查必须通过跟踪所有已确认的边缘递归完成,但这对我来说太慢了,所以我将在这里解决,只是检查节点是否正在访问,或者是否有任何已确认连接的节点正在访问。这将覆盖我的大多数情况,但在图中会出现循环。

After the above step I use Tarjan's algorithm for finding the strongly connected components left in the graph (this can be done in O(V + E) time). The number of strongly connected components will be very small in my cases so I just go through each strongly connected component and remove one removable edge each. Then I do this step again until no more cycles remain in the graph.

在上述步骤之后,我使用Tarjan的算法来查找图中剩余的强连通分量(这可以在O(V + E)时间内完成)。在我的情况下,强连接组件的数量将非常小,所以我只是浏览每个强连接组件并删除每个可移动边缘。然后我再次执行此步骤,直到图表中不再有循环。

This works fine and is fast enough.

这很好,而且足够快。

#1