import { INode , IConnection } from "../../baklavajs-core/types" ; interface ITreeNode { n ? : INode ; children : ITreeNode [ ] ; } interface IOrderCalculationResult { calculationOrder : INode [ ] ; rootNodes : INode [ ] ; } const isEmpty = ( obj ) => [ Object , Array ] . includes ( ( obj || { } ) . constructor ) && ! Object . entries ( ( obj || { } ) ) . length ; export function calculateOrder ( nodes , connections , roots ? ) { const adjacency = new Map < INode , INode [ ] > ( ) ; nodes . forEach ( ( n ) => { adjacency . set ( n , connections . filter ( ( c ) => c . to && c . to . parent === n ) . map ( ( c ) => c . from . parent ) ) ; } ) ; const outputs = roots || nodes . filter ( ( n ) => isEmpty ( n . outputInterfaces ) ) ; const root = { children : outputs . map ( ( o ) => ( { n : o , children : [ ] } ) ) } ; findDescendants ( root , [ ] , adjacency ) ; const queue = [ ] ; const stack = [ ] ; queue . push ( root ) ; while ( queue . length > 0 ) { const current = queue . shift ( ) ! ; current . children . forEach ( ( c ) => { stack . push ( c . n ! ) ; queue . push ( c ) ; } ) ; } const calculationOrder = [ ] ; while ( stack . length > 0 ) { const n = stack . pop ( ) ! ; if ( ! calculationOrder . includes ( n ) ) { calculationOrder . push ( n ) ; } } return { calculationOrder , rootNodes : outputs } ; } function findDescendants ( tn , ancestors , adjacency ) { for ( const c of tn . children ) { if ( ancestors . includes ( c . n ! ) ) { throw new Error ( "Cycle detected" ) ; } ancestors . unshift ( c . n ! ) ; c . children = c . children . concat ( adjacency . get ( c . n ! ) ! . map ( ( n ) => ( { n , children : new Array < ITreeNode > ( ) } ) ) ) ; findDescendants ( c , ancestors , adjacency ) ; ancestors . shift ( ) ; } } export function containsCycle ( nodes , connections ) { try { calculateOrder ( nodes , connections ) ; return true ; } catch ( err ) { return false ; } }