import { Equatable } from "@siteimprove/alfa-equatable" ; import { Hashable , Hash } from "@siteimprove/alfa-hash" ; import { Iterable } from "@siteimprove/alfa-iterable" ; import { Serializable } from "@siteimprove/alfa-json" ; import { Map } from "@siteimprove/alfa-map" ; import { Sequence } from "@siteimprove/alfa-sequence" ; import { Set } from "@siteimprove/alfa-set" ; public export class Graph < T > implements Iterable < [ T , Iterable < T > ] > , Equatable , Hashable , Serializable < Graph . JSON < T > > { public static of < T > ( nodes ) { return new Graph ( nodes ) ; } private static _empty = new Graph < never > ( Map . empty ( ) ) ; public static empty < T > ( ) { return this . _empty ; } private readonly _nodes : Map < T , Set < T > > ; private constructor ( nodes ) { this . _nodes = nodes ; } public get size ( ) : number { return this . _nodes . size ; } public isEmpty ( ) { return this . _nodes . isEmpty ( ) ; } public nodes ( ) { return this . _nodes . keys ( ) ; } public neighbors ( node ) { return this . _nodes . get ( node ) . getOr ( [ ] ) ; } public has ( node ) { return this . _nodes . has ( node ) ; } public add ( node ) { if ( this . has ( node ) ) { return this ; } return new Graph ( this . _nodes . set ( node , Set . empty ( ) ) ) ; } public delete ( node ) { let nodes = this . _nodes ; if ( ! nodes . has ( node ) ) { return this ; } return new Graph ( nodes . delete ( node ) . map ( ( neighbors ) => neighbors . delete ( node ) ) ) ; } public connect ( from , to ) { let nodes = this . _nodes ; if ( ! nodes . has ( from ) ) { nodes = nodes . set ( from , Set . empty ( ) ) ; } if ( ! nodes . has ( to ) ) { nodes = nodes . set ( to , Set . empty ( ) ) ; } return new Graph ( nodes . set ( from , nodes . get ( from ) . map ( ( from ) => from . add ( to ) ) . get ( ) ) ) ; } public disconnect ( from , to ) { if ( ! this . has ( from ) || ! this . has ( to ) ) { return this ; } const nodes = this . _nodes ; return new Graph ( nodes . set ( from , nodes . get ( from ) . map ( ( from ) => from . delete ( to ) ) . get ( ) ) ) ; } public traverse ( root , traversal = Graph . DepthFirst ) { return Sequence . from ( traversal ( this , root ) ) ; } public path ( from , to , traversal = Graph . BreadthFirst ) { const parents = Map . from ( traversal ( this , from ) ) ; const path = [ ] ; while ( parents . has ( to ) ) { const parent = parents . get ( to ) . get ( ) ; path . unshift ( to ) ; to = parent ; } return Sequence . from ( path ) ; } public hasPath ( from , to ) { if ( ! this . has ( from ) || ! this . has ( to ) ) { return false ; } return this . traverse ( from ) . map ( ( [ node ] ) => node ) . includes ( to ) ; } public reverse ( ) { let reversed = Graph . empty < T > ( ) ; for ( const [ node , neighbors ] of this . _nodes ) { reversed = reversed . add ( node ) ; for ( const neighbor of neighbors ) { reversed = reversed . connect ( neighbor , node ) ; } } return reversed ; } public * sort ( ) { let incoming = this . reverse ( ) ; const queue = incoming . toArray ( ) . filter ( ( [ , edges ] ) => edges . length === 0 ) . map ( ( [ node ] ) => node ) ; while ( queue . length > 0 ) { const next = queue . shift ( ) ! ; yield next ; for ( const neighbor of this . neighbors ( next ) ) { incoming = incoming . disconnect ( neighbor , next ) ; if ( Iterable . isEmpty ( incoming . neighbors ( neighbor ) ) ) { queue . push ( neighbor ) ; } } } } public equals < T > ( value ) ; public equals ( value ) ; public equals ( value ) { return value instanceof Graph && value . _nodes . equals ( this . _nodes ) ; } public hash ( hash ) { hash . writeHashable ( this . _nodes ) ; } public * iterator ( ) { yield * this . _nodes ; } public [ Symbol . iterator ] ( ) { return this . iterator ( ) ; } public toArray ( ) { return [ ... this ] . map ( ( [ node , neighbors ] ) => [ node , [ ... neighbors ] ] ) ; } public toJSON ( ) { return this . toArray ( ) . map ( ( [ node , neighbors ] ) => [ Serializable . toJSON ( node ) , neighbors . map ( ( node ) => Serializable . toJSON ( node ) ) , ] ) ; } public toString ( ) { const entries = this . toArray ( ) . map ( ( [ node , edges ] ) => { const entries = edges . join ( ", " ) ; return `${ node }${ entries === "" ? "" : ` => [ ${ entries } ]` }` ; } ) . join ( ", " ) ; return `Graph {${ entries === "" ? "" : ` ${ entries } ` }}` ; } } public export namespace Graph { export type JSON < T > = Array < [ Serializable . ToJSON < T > , Array < Serializable . ToJSON < T > > ] > ; export function isGraph < T > ( value ) ; export function isGraph < T > ( value ) ; export function isGraph < T > ( value ) { return value instanceof Graph ; } export function from < T > ( iterable ) { if ( isGraph ( iterable ) ) { return iterable ; } return Graph . of ( Map . from ( Iterable . map ( iterable , ( [ node , neighbours ] ) => [ node , Set . from ( neighbours ) , ] ) ) ) ; } export interface Traversal { < T > ( graph , root ) : Iterable < [ node : T , parent : T ] > ; } /**
     *  https export const DepthFirst = function * < T > ( graph , root ) { const stack = [ ... graph . neighbors ( root ) , ] . map ( ( node ) => [ node , root ] ) ; let seen = Set . of ( root ) ; while ( stack . length > 0 ) { const next = stack . pop ( ) ! ; if ( seen . has ( next [ 0 ] ) ) { continue ; } yield next ; seen = seen . add ( next [ 0 ] ) ; for ( const neighbor of graph . neighbors ( next [ 0 ] ) ) { stack . push ( [ neighbor , next [ 0 ] ] ) ; } } } ; /**
     *  https export const BreadthFirst = function * < T > ( graph , root ) { const queue = [ ... graph . neighbors ( root ) , ] . map ( ( node ) => [ node , root ] ) ; let seen = Set . of ( root , ... graph . neighbors ( root ) ) ; while ( queue . length > 0 ) { const next = queue . shift ( ) ! ; yield next ; for ( const neighbor of graph . neighbors ( next [ 0 ] ) ) { if ( seen . has ( neighbor ) ) { continue ; } seen = seen . add ( neighbor ) ; queue . push ( [ neighbor , next [ 0 ] ] ) ; } } } ; }