import { GraphAlgOutput } from '../../utils/types/graph-types/graph-results-types' ; import { GraphNode , Graph , ParentVectorType , Edges } from './graph' ; export const bfs = ( startNode , destinationNode , graph ) : GraphAlgOutput => { startNode = { ... startNode , weight : 0 } ; destinationNode = { ... destinationNode , weight : 1 } ; graph . nodes = graph . nodes . map ( ( 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 queue = [ startNode ] ; const visitedNodes = [ startNode ] ; const visitedInOrder = [ ] ; const parent = { } ; while ( queue . length > 0 ) { const currentNode = { ... queue [ 0 ] } ; visitedInOrder . push ( currentNode ) ; queue . shift ( ) ; if ( currentNode . id === destinationNode . id ) { break ; } graph . edges [ currentNode . id ] . forEach ( ( elem ) => { let exists = false ; visitedNodes . forEach ( ( visitedNode ) => { if ( visitedNode . id === elem . id ) { exists = true ; } } ) ; if ( ! exists && currentNode . weight !== undefined ) { queue . push ( { ... elem , weight : 1 + currentNode . weight } ) ; parent [ elem . id ] = { ... currentNode } ; visitedNodes . push ( { ... elem } ) ; } } ) ; } visitedInOrder . shift ( ) ; if ( visitedInOrder [ visitedInOrder . length - 1 ] . id === destinationNode . id ) { visitedInOrder . pop ( ) ; } return { visitedNodes : visitedInOrder , parentVector : parent , } ; } ;