package com.jiucaiyuan.net.algrithm.graph;



import java.util.*;



/**

 * 有向无环图拓扑排序（DAG：Direct Acyclic Graph）

 *

 * 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说

 *

 * @Author jiucaiyuan  2022/4/14 22:20

 * @mail services@jiucaiyuan.net

 */



public class TopologySort {

    /**

     * directed graph and no loop

     * 有向图图拓扑排序

     * 适用范围：有向无环图

     * 思路：从入度为0的节点触发，抹掉入度为0的节点，剩下的节点入度更新，再找到入度为0的节点，再次抹掉，再次更新

     * @param graph  有向图 & 存在入度为0的节点 & 无环

     * @return 拓扑排序结果

     */

    public static List<Node> sortedTopology(Graph graph){

        //<节点，该节点的剩余入度>   去除一个节点后，会把该节点的影响全部抹掉

        HashMap<Node,Integer> inMap = new HashMap<>();

        //入度为0的节点队列

        Queue<Node> zeroInQueue = new LinkedList<>();

        //初始化，图中所有节点都处理一遍，记录所有节点的入度以及入度为0的节点

        for(Node currNode : graph.nodes.values()){

            inMap.put(currNode,currNode.in);

            if(0 == currNode.in){

                zeroInQueue.add(currNode);

            }

        }

        //拓扑排序结果集

        List<Node> result = new ArrayList<>();

        //入度为0的节点开始处理，处理过程中有入度为0的节点都入队

        while (!zeroInQueue.isEmpty()){

            Node curr = zeroInQueue.poll();

            result.add(curr);

            //抹掉当前入度为0的节点，后续受影响的节点的入度更新，如果再次产生入度为0的节点进入队列

            for(Node next:curr.nexts){

                inMap.put(next,inMap.get(next) - 1);

                if(inMap.get(next) == 0){

                    zeroInQueue.add(next);

                }

            }

        }

        return result;

    }

}