import networkx


def remove_cycle_by_dfs(dag: networkx.DiGraph, start_node_id):
    selected = set()

    def dfs(node_id):
        """
        说明：这里的 successors 表示所有以node_id为终点的故障传播关系。
          例如关系 A depends_on B 对应的故障传播为 B --> A ，则 A 节点的 successors 包括 B 节点；
          如果关系 A depends_on B 对应的故障传播为 A --> B ，则 B 节点的 successors 包括 A 节点。
        """
        successors = list(dag.successors(node_id))
        for succ_id in successors:
            if succ_id in selected:
                print("A cycle is detected, remove edge: {} --> {}".format(node_id, succ_id))
                dag.remove_edge(node_id, succ_id)
            else:
                selected.add(succ_id)
                dfs(succ_id)
                selected.remove(succ_id)

    selected.add(start_node_id)
    dfs(start_node_id)


if __name__ == '__main__':
    dag = networkx.DiGraph()
    dag.add_nodes_from(["prsa", "group1", "group2", "group3"])
    dag.add_edge("prsa", "group1")
    dag.add_edge("group1", "group1")    # 这里有一个环
    dag.add_edge("group1", "group2")
    dag.add_edge("group1", "group3")
    dag.add_edge("group2", "group3")
    dag.add_edge("group3", "group1")    # 这里也有一个环
    dag.add_edge("group3", "group2")    # 这里也有一个环
    # 去环
    remove_cycle_by_dfs(dag, "prsa")
    # 程序运行输出打印如下：
    # A cycle is detected, remove edge: group1 --> group1
    # A cycle is detected, remove edge: group3 --> group1
    # A cycle is detected, remove edge: group3 --> group2