import { setMap } from "collection-utils" ; import { defined , repeated , assert , repeatedCall } from "./support/Support" ; function countComponentGraphNodes ( components ) { if ( components . length === 0 ) return 0 ; let largest = - 1 ; let count = 0 ; for ( const c of components ) { assert ( c . length > 0 , "Empty component not allowed" ) ; for ( const v of c ) { assert ( v >= 0 , "Negative vertex index is invalid" ) ; largest = Math . max ( largest , v ) ; count += 1 ; } } assert ( largest + 1 === count , "Vertex indexes and count don't match up" ) ; return count ; } function stronglyConnectedComponents ( successors ) { let index = 0 ; const stack = [ ] ; const numNodes = successors . length ; const indexes = repeated ( numNodes , - 1 ) ; const lowLinks = repeated ( numNodes , - 1 ) ; const onStack = repeated ( numNodes , false ) ; const sccs = [ ] ; function strongconnect ( v ) { indexes [ v ] = index ; lowLinks [ v ] = index ; index += 1 ; stack . push ( v ) ; onStack [ v ] = true ; for ( const w of successors [ v ] ) { if ( indexes [ w ] < 0 ) { strongconnect ( w ) ; lowLinks [ v ] = Math . min ( lowLinks [ v ] , lowLinks [ w ] ) ; } else if ( onStack [ w ] ) { lowLinks [ v ] = Math . min ( lowLinks [ v ] , indexes [ w ] ) ; } } if ( lowLinks [ v ] === indexes [ v ] ) { const scc = [ ] ; let w ; do { w = defined ( stack . pop ( ) ) ; onStack [ w ] = false ; scc . push ( w ) ; } while ( w !== v ) ; sccs . push ( scc ) ; } } for ( let v = 0 ; v < numNodes ; v ++ ) { if ( indexes [ v ] < 0 ) { strongconnect ( v ) ; } } assert ( countComponentGraphNodes ( sccs ) === numNodes , "We didn't put all the nodes into SCCs" ) ; return sccs ; } function buildComponentOfNodeMap ( successors , components ) { const numComponents = components . length ; const numNodes = successors . length ; assert ( numNodes === countComponentGraphNodes ( components ) , "Components don't match up with graph" ) ; const componentOfNode = repeated ( numNodes , - 1 ) ; for ( let c = 0 ; c < numComponents ; c ++ ) { for ( const n of components [ c ] ) { assert ( componentOfNode [ n ] < 0 , "We have a node that's in two components" ) ; componentOfNode [ n ] = c ; } } return componentOfNode ; } function buildMetaSuccessors ( successors , components ) { const numComponents = components . length ; const componentOfNode = buildComponentOfNodeMap ( successors , components ) ; const componentAdded = repeated ( numComponents , false ) ; const metaSuccessors = [ ] ; for ( let c = 0 ; c < numComponents ; c ++ ) { const succ = [ ] ; for ( const n of components [ c ] ) { for ( const s of successors [ n ] ) { const ms = componentOfNode [ s ] ; if ( ms === c || componentAdded [ ms ] ) continue ; succ . push ( ms ) ; componentAdded [ ms ] = true ; } } for ( const ms of succ ) { assert ( componentAdded [ ms ] ) ; componentAdded [ ms ] = false ; } metaSuccessors . push ( succ ) ; } return metaSuccessors ; } function invertEdges ( successors ) { const numNodes = successors . length ; const predecessors = repeatedCall ( numNodes , ( ) => [ ] ) ; for ( let s = 0 ; s < numNodes ; s ++ ) { for ( const v of successors [ s ] ) { predecessors [ v ] . push ( s ) ; } } return predecessors ; } function calculateInDegrees ( successors ) { const numNodes = successors . length ; const inDegrees = repeated ( numNodes , 0 ) ; for ( const s of successors ) { for ( const v of s ) { inDegrees [ v ] += 1 ; } } return inDegrees ; } function findRoots ( successors ) { const numNodes = successors . length ; const inDegrees = calculateInDegrees ( successors ) ; const roots = [ ] ; for ( let v = 0 ; v < numNodes ; v ++ ) { if ( inDegrees [ v ] === 0 ) { roots . push ( v ) ; } } return roots ; } export class Graph < T > { private readonly _nodes : ReadonlyArray < T > ; private readonly _indexByNode : ReadonlyMap < T , number > ; private readonly _successors : number [ ] [ ] ; constructor ( nodes , invertDirection , edges ) { this . _nodes = Array . from ( nodes ) ; this . _indexByNode = new Map ( this . _nodes . map ( ( n , i ) : [ T , number ] => [ n , i ] ) ) ; let edgesArray ; if ( Array . isArray ( edges ) ) { edgesArray = edges ; } else { edgesArray = this . _nodes . map ( n => Array . from ( edges ( n ) ) . map ( s => defined ( this . _indexByNode . get ( s ) ) ) ) ; } if ( invertDirection ) { edgesArray = invertEdges ( edgesArray ) ; } this . _successors = edgesArray ; } get size ( ) : number { return this . _nodes . length ; } get nodes ( ) : ReadonlyArray < T > { return this . _nodes ; } findRoots ( ) { const roots = findRoots ( this . _successors ) ; return new Set ( roots . map ( n => this . _nodes [ n ] ) ) ; } dfsTraversal ( root , preOrder , process ) { const visited = repeated ( this . size , false ) ; const visit = ( v ) : void => { if ( visited [ v ] ) return ; visited [ v ] = true ; if ( preOrder ) { process ( this . _nodes [ v ] ) ; } for ( const w of this . _successors [ v ] ) { visit ( w ) ; } if ( ! preOrder ) { process ( this . _nodes [ v ] ) ; } } ; visit ( defined ( this . _indexByNode . get ( root ) ) ) ; } stronglyConnectedComponents ( ) { const components = stronglyConnectedComponents ( this . _successors ) ; const componentSuccessors = buildMetaSuccessors ( this . _successors , components ) ; return new Graph ( components . map ( ns => setMap ( ns , n => this . _nodes [ n ] ) ) , false , componentSuccessors ) ; } makeDot ( includeNode , nodeLabel ) { const lines = [ ] ; lines . push ( "digraph G {" ) ; lines . push ( "    ordering = out;" ) ; lines . push ( "" ) ; for ( let i = 0 ; i < this . size ; i ++ ) { const n = this . _nodes [ i ] ; if ( ! includeNode ( n ) ) continue ; lines . push ( `    node${ i } [label="${ nodeLabel ( n ) }"];` ) ; } for ( let i = 0 ; i < this . size ; i ++ ) { if ( ! includeNode ( this . _nodes [ i ] ) ) continue ; for ( const j of this . _successors [ i ] ) { if ( ! includeNode ( this . _nodes [ j ] ) ) continue ; lines . push ( `    node${ i } -> node${ j };` ) ; } } lines . push ( "}" ) ; lines . push ( "" ) ; return lines . join ( "\n" ) ; } }