import { AbstractGraph } from './abstractGraph' ; import { Node , Edge } from '../lib/NodeDefs' ; export abstract class DepthFirstSearch { protected readonly graph : AbstractGraph ; private readonly state : Set < Node > ; constructor ( g ) { this . graph = g ; this . state = new Set < Node > ( ) ; } public run ( ) { for ( const node of this . graph . nodes ) { if ( this . state . has ( node ) ) { return ; } this . dfs ( node ) ; } } public abstract visit ( node ) ; public abstract explore ( src , dst ) ; public abstract finish ( node ) ; protected dfs ( node ) { this . visit ( node ) ; for ( const dst of this . graph . getEdges ( node ) ) { this . explore ( node , dst ) ; if ( this . state . has ( dst ) ) { continue ; } this . state . add ( dst ) ; this . dfs ( dst ) ; } this . finish ( node ) ; } } export class FindAllDependencies extends DepthFirstSearch { public visited : Map < string , Node > = new Map < string , Node > ( ) ; public finished : Set < Node > = new Set < Node > ( ) ; public visitedNames : Set < String > = new Set < String > ( ) ; public visitedEdges : Set < Edge > = new Set < Edge > ( ) ; public visit ( node ) { this . visited . set ( node . name , node ) ; this . visitedNames . add ( node . name ) ; } public finish ( node ) { this . finished . add ( node ) ; } public runNode ( node ) { if ( ! this . visited . has ( node . name ) ) { this . dfs ( node ) ; } } public explore ( src , dst ) { this . visitedEdges . add ( { from : src . name , to : dst . name } ) ; } } export class FindCycles extends DepthFirstSearch { public visited : Set < Node > = new Set < Node > ( ) ; public finished : Set < Node > = new Set < Node > ( ) ; public cycles : Node [ ] [ ] = new Array < Node [ ] > ( ) ; public visit ( node ) { this . visited . add ( node ) ; } public finish ( node ) { this . finished . add ( node ) ; } public explore ( src , dst ) { if ( src === dst ) { return ; } if ( this . visited . has ( dst ) && ! this . finished . has ( dst ) ) { this . cycles . push ( [ src , dst ] ) ; } } }