import { GraphAlgOutput , Pair } from '../../utils/types/graph-types/graph-results-types' ; import { Edges , Graph , GraphNode , ParentVectorType } from './graph' ; import { Heap } from 'ts-heap' ; import { MyDictionary } from '../../utils/types/app-types/dictionary' ; import { GraphState } from '../../store/graph/state' ; import { computeDistance , fromIndexToPair } from '../../utils/graph-utils-functions' ; export const aStar = ( source , destination , graphState ) : GraphAlgOutput => { const heapComparator = ( node1 , node2 ) : number => { if ( node1 . weight && node2 . weight ) { const p1 = fromIndexToPair ( parseInt ( node1 . id , 10 ) , graphState . width ) ; const p2 = fromIndexToPair ( parseInt ( node2 . id , 10 ) , graphState . width ) ; const dest = fromIndexToPair ( parseInt ( destination . id , 10 ) , graphState . width ) ; return node1 . weight + computeDistance ( p1 , dest ) - node2 . weight - computeDistance ( p2 , dest ) ; } return 0 ; } ; const pq = new Heap ( heapComparator ) ; const graph = { numberOfNodes : graphState . numberOfNodes , nodes : graphState . nodes , edges : graphState . edges , } ; graph . nodes = graph . nodes . map ( ( elem ) => { if ( elem . weight ) { return elem ; } return { id : elem . id , weight : 1 } ; } ) ; graph . edges = Object . keys ( graph . edges ) . reduce ( ( oldE , key ) => { oldE [ key ] = graph . edges [ key ] . map ( ( elem ) => { if ( elem . weight ) { return elem ; } return { id : elem . id , weight : 1 } ; } ) ; return oldE ; } , { } ) ; const dist = graph . nodes . reduce ( ( map , currentNode ) => { map [ currentNode . id ] = Infinity ; return map ; } , { } ) ; dist [ source . id ] = 0 ; pq . add ( { id : source . id , weight : dist [ source . id ] } ) ; const parent = { } ; const visitedNodes = [ ] ; while ( ! pq . isEmpty ) { const currentBest = pq . pop ( ) ; if ( ! currentBest ) continue ; if ( currentBest ?. weight !== dist [ currentBest . id ] ) { continue ; } visitedNodes . push ( { ... currentBest } ) ; if ( currentBest . id === destination . id ) { break ; } graph . edges [ currentBest . id ] . forEach ( ( adj ) => { if ( adj . weight && dist [ adj . id ] > dist [ currentBest . id ] + adj . weight ) { dist [ adj . id ] = dist [ currentBest . id ] + adj . weight ; pq . add ( { id : adj . id , weight : dist [ adj . id ] } ) ; parent [ adj . id ] = { ... currentBest } ; } } ) ; } if ( visitedNodes [ visitedNodes . length - 1 ] . id === destination . id ) { visitedNodes . pop ( ) ; } visitedNodes . shift ( ) ; return { visitedNodes : visitedNodes , parentVector : parent , } ; } ;