import { MinAdjacencyListArray , MinAdjacencyListDict , NextArray , } from "../interfaces" ; import { IGraph } from "../base/BaseGraph" ; import { Logger } from "../../utils/Logger" ; import { IBaseNode } from "../base/BaseNode" ; const logger = new Logger ( ) ; const DEFAULT_WEIGHT = 1 ; export interface NumericHandler { tensor2d : Function ; matMul : Function ; } /**
 *
 */ export interface IComputeGraph { adjListW ( incoming ? , include_self ? , self_dist ? ) : MinAdjacencyListDict ; adjMatrix ( ) : MinAdjacencyListArray ; adjMatrixW ( incoming ? ) : MinAdjacencyListArray ; nextArray ( incoming ? ) : NextArray ; triadCount ( directed ? ) : number ; triangleCount ( directed ? ) : Promise < number > ; globalCC ( directed ? ) : Promise < number > ; localCC ( directed ? ) : Promise < { [ key ] : number ; } > ; } /**
 *
 */ class ComputeGraph implements IComputeGraph { private adj_list_uu : Uint32Array ; private adj_list_du : Uint32Array ; private adj_list_uw : Float32Array ; private adj_list_dw : Float32Array ; constructor ( private _g , private _numeric ? ) { } checkNumericHandler ( ) { if ( ! this . _numeric || ! this . _numeric . matMul ) { throw new Error ( "Tensorflow & TF matMul function must be present for fast numeric computations." ) ; } } param incoming todo nextArray ( incoming = false ) { let next = [ ] , node_keys = Object . keys ( this . _g . getNodes ( ) ) ; const adjDict = this . adjListW ( incoming , true , 0 ) ; for ( let i = 0 ; i < this . _g . nrNodes ( ) ; ++ i ) { next . push ( [ ] ) ; for ( let j = 0 ; j < this . _g . nrNodes ( ) ; ++ j ) { next [ i ] . push ( [ ] ) ; next [ i ] [ j ] . push ( i === j ? j : isFinite ( adjDict [ node_keys [ i ] ] [ node_keys [ j ] ] ) ? j : null ) ; } } return next ; } adjMatrix ( ) { let adjList = [ ] , node_keys = Object . keys ( this . _g . getNodes ( ) ) ; const adjDict = this . adjListW ( ) ; for ( let i = 0 ; i < this . _g . nrNodes ( ) ; ++ i ) { adjList . push ( [ ] ) ; for ( let j = 0 ; j < this . _g . nrNodes ( ) ; ++ j ) { adjList [ i ] . push ( i === j ? 0 : isFinite ( adjDict [ node_keys [ i ] ] [ node_keys [ j ] ] ) ? 1 : 0 ) ; } } return adjList ; } todo param incoming param include_self param self_dist adjMatrixW ( incoming = false , include_self = false , self_dist = 0 ) { let adjList = [ ] , node_keys = Object . keys ( this . _g . getNodes ( ) ) ; const adjDict = this . adjListW ( incoming , include_self , self_dist ) ; for ( let i = 0 ; i < this . _g . nrNodes ( ) ; ++ i ) { adjList . push ( [ ] ) ; for ( let j = 0 ; j < this . _g . nrNodes ( ) ; ++ j ) { adjList [ i ] . push ( i === j ? self_dist : isFinite ( adjDict [ node_keys [ i ] ] [ node_keys [ j ] ] ) ? adjDict [ node_keys [ i ] ] [ node_keys [ j ] ] : Number . POSITIVE_INFINITY ) ; } } return adjList ; } todo param incoming param include_self param self_dist adjListW ( incoming = false , include_self = false , self_dist = 0 ) { let adj_list_dict = { } , nodes = this . _g . getNodes ( ) , cur_dist , key , cur_edge_weight ; for ( key in nodes ) { adj_list_dict [ key ] = { } ; if ( include_self ) { adj_list_dict [ key ] [ key ] = self_dist ; } } for ( key in nodes ) { let neighbors = incoming ? nodes [ key ] . reachNodes ( ) . concat ( nodes [ key ] . prevNodes ( ) ) : nodes [ key ] . reachNodes ( ) ; neighbors . forEach ( ne => { cur_dist = adj_list_dict [ key ] [ ne . node . getID ( ) ] || Number . POSITIVE_INFINITY ; cur_edge_weight = isNaN ( ne . edge . getWeight ( ) ) ? DEFAULT_WEIGHT : ne . edge . getWeight ( ) ; if ( cur_edge_weight < cur_dist ) { adj_list_dict [ key ] [ ne . node . getID ( ) ] = cur_edge_weight ; if ( incoming ) { adj_list_dict [ ne . node . getID ( ) ] [ key ] = cur_edge_weight ; } } else { adj_list_dict [ key ] [ ne . node . getID ( ) ] = cur_dist ; if ( incoming ) { adj_list_dict [ ne . node . getID ( ) ] [ key ] = cur_dist ; } } } ) ; } return adj_list_dict ; } todo description description todo param directed triadCount ( directed = false ) { let triangle_count = 0 ; const nodes = Object . values ( this . _g . getNodes ( ) ) ; let deg ; for ( let n of nodes ) { if ( directed ) { triangle_count += ( n . in_deg - n . self_in_deg ) * ( n . out_deg - n . self_out_deg ) ; } else { deg = n . deg - n . self_deg ; triangle_count += ( deg * ( deg - 1 ) ) / 2 ; } } return triangle_count ; } description param directed async triangleCount ( directed = false ) { this . checkNumericHandler ( ) ; const adj_list = this . adjMatrix ( ) ; const a = this . _numeric . tensor2d ( adj_list ) ; const aux2 = await a . matMul ( a ) . array ( ) ; const aux3 = await a . matMul ( aux2 ) . array ( ) ; let trace = 0 ; for ( let i = 0 ; i < aux3 . length ; i ++ ) { trace += aux3 [ i ] [ i ] ; } return directed ? trace / 3 : trace / 6 ; } description description todo todo todo todo param directed async globalCC ( directed = false ) { const triangles = await this . triangleCount ( directed ) ; const triads = this . triadCount ( directed ) ; return ( 3 * triangles ) / triads ; } description param directed async localCC ( directed = false ) { this . checkNumericHandler ( ) ; const result = { } ; const adj_list = this . adjMatrix ( ) ; const a = this . _numeric . tensor2d ( adj_list ) ; const aux2 = await a . matMul ( a ) . array ( ) ; const aux3 = await a . matMul ( aux2 ) . array ( ) ; todo let deg ; let node ; let cc_i ; const keys = Object . keys ( this . _g . getNodes ( ) ) ; for ( let i in aux3 [ 0 ] ) { node = this . _g . getNodeById ( keys [ i ] ) ; deg = directed ? node . in_deg + node . out_deg : node . deg ; cc_i = aux3 [ i ] [ i ] / ( deg * ( deg - 1 ) ) || 0 ; result [ i ] = directed ? 2 * cc_i : cc_i ; } return result ; } } export { ComputeGraph } ;