/**
 * TypeScript program to print all topological sorts of a graph
 * Original C++ source code from http://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
 */ export class DirectedAcyclicGraph { private numVertices : number ; constructor ( numVertices ) { this . numVertices = numVertices ; for ( let curr = 0 ; curr < numVertices ; curr = curr + 1 ) { this . inDegree . push ( 0 ) ; this . adj . push ( [ ] ) ; } } private adj : number [ ] [ ] = [ ] ; private inDegree : number [ ] = [ ] ; public alltopologicalSort ( ) { const { numVertices } = this ; const visited = [ ] ; for ( let curr = 0 ; curr < numVertices ; curr = curr + 1 ) { visited . push ( false ) ; } const res = [ ] ; return this . alltopologicalSortUtil ( res , visited ) ; } private alltopologicalSortUtil ( res , visited ) { const { numVertices , inDegree , adj } = this ; let flag = false ; const allSorts = [ ] ; const floor = inDegree . reduce ( ( result , val , index ) => { if ( visited [ index ] === false ) { return Math . min ( result , val ) ; } return result ; } , Infinity ) ; for ( let vertex = 0 ; vertex < numVertices ; vertex ++ ) { if ( inDegree [ vertex ] === floor && ! visited [ vertex ] ) { let adjIndex ; for ( adjIndex = 0 ; adjIndex < adj [ vertex ] . length ; adjIndex ++ ) { const jv = adj [ vertex ] [ adjIndex ] ; inDegree [ jv ] -- ; } visited [ vertex ] = true ; allSorts . push ( ... this . alltopologicalSortUtil ( res . concat ( vertex ) , visited ) ) ; visited [ vertex ] = false ; for ( adjIndex = 0 ; adjIndex < adj [ vertex ] . length ; adjIndex ++ ) { const jv = adj [ vertex ] [ adjIndex ] ; inDegree [ jv ] ++ ; } flag = true ; } } if ( ! flag ) { allSorts . push ( res ) ; } return allSorts ; } public addEdge ( src , dest ) { this . adj [ src ] . push ( dest ) ; this . inDegree [ dest ] ++ ; } }