Topo sort

Topo sort starts from end node

This is used in autodiff graph build algorithm

def find_topo_sort(node_list):
    """Given a list of nodes, return a topo ordering of nodes ending in them.

    A simple algorithm is to do a post-order DFS traversal on the given nodes,
    going backwards based on input edges. Since a node is added to the ordering
    after all its predecessors are traversed due to post-order DFS, we get a
    topological sort.

    """
    visited = set()
    topo_order = []
    for node in node_list:
        topo_sort_dfs(node, visited, topo_order)
    return topo_order


def topo_sort_dfs(node, visited, topo_order):
    """Post-order DFS"""
    if node in visited:
        return
    visited.add(node)
    for n in node.inputs:
        topo_sort_dfs(n, visited, topo_order)
    topo_order.append(node)

Topo sort given graph

This is used in leetcode problem.

Given a graph we use in_degree to track in degree for each node.

Each node whose in degree is 0 is put to output array which means that this node depends on no other nodes.

This node is also put to queue to get adjacent nodes to this in_degree=0 node.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int num_node;
    int edge_count;
    cin >> num_node >> edge_count;
    vector<vector<int>> graph(num_node);
    vector<int> in_degree(num_node, 0);
    for(int i=0; i < edge_count; i++) {
        int in, out;
        cin >> in >> out;
        int node_idx = in - 1;
        int out_node_idx = out-1;
        graph[node_idx].push_back(out_node_idx);
        in_degree[out_node_idx]++;
    }

    queue<int> node_q;
    for(int i=0; i < num_node; i++) {
        if(in_degree[i] == 0) {
            node_q.push(i);
        }
    }
    vector<int> topo_sort;
    while(!node_q.empty())  {
        int front_node = node_q.front();
        node_q.pop();
        topo_sort.push_back(front_node);
        for(int out_node:graph[front_node]) {
            in_degree[out_node]--;
            if(in_degree[out_node] == 0) {
                node_q.push(out_node);
            }
        }
    }

    if(topo_sort.size() == num_node) {
        for(int i=0; i < num_node-1; i++) {
            cout << topo_sort[i]+1 << " ";
        }
        cout << topo_sort.back()+1 << endl;
    } else {
        cout << -1 << endl;
    }



}
// 64 位输出请用 printf("%lld")

Topo sort starts from end node

Topo sort given graph

Difference between tensorflow and pytorch?

Enjoy Reading This Article?