Is there a way to implement depth-first retrieval in rxjs using the expand method?

Question

Is there a way to implement depth-first retrieval in rxjs using the expand method?

Currently, I am engaged in a project utilizing Angular 7, Typescript, and RxJS 6.3.3. In this project, I am working with RxJS Observables and relevant operators to handle hierarchical collections of objects obtained from an http server that interfaces with a database.

In order to create a depth-first search algorithm, I initially attempted to utilize the expand operator while employing concatMap to maintain order. Unfortunately, this approach proved ineffective.

You can find a simplified example here: https://stackblitz.com/edit/rxjs-vf4zem

The console output generated by this example is as follows:

dfs no delay: [1,8,9,22,23,24,2,4,7,3]
dfs with delay: [1,2,3,4,7,8,9,22,23,24]

(The sequence of the second output line may vary depending on the extent of the simulated data retrieval delay meant to mimic fetching data from the http server.)

With reference to the dataset provided in the example, my intention is to consistently obtain the first line of output: a representation following a depth-first order. The crucial function featured in the example is:

const dfs = (getter: Getter) => rootIds.pipe(
  concatMap(ids => from(ids)),
  expand(id =>
    getter(id).pipe(
      concatMap(children => from(children))
    )
  ),
  toArray()
);

Is there an effective method to enforce depth-first processing? Can the use of expand guarantee such an outcome, or is it simply an inadequate strategy for transforming hierarchical data into a flattened, depth-first array?

angular typescript rxjs

Answer 1

Answer №1

I believe the question raises an interesting point about the need for an additional data structure for parallel fetch operations to compose results efficiently.

Although a recursive reconstruction using expand is intriguing, I have opted for a sequential approach:

sequentialDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
  return of(ids).pipe(
    expand(([head, ...rest]) =>
      // working with ids in left-to-right order
      getChildren(head).pipe(
        switchMap(subChildren => {
          const acc = [...subChildren, ...rest ];
          return acc.length
            ? of(acc)
            : EMPTY;
        })
      )
    ),

    // collecting the heads {{{
    map(([head])=>head),
    toArray()
    // }}}
  );
}

* The getChildren method has been slightly modified to return Observable<number[]> instead of Observable<number>.

https://stackblitz.com/edit/rxjs-rf8d1j

This solution does not address parallel fetching directly but rather presents a sequential alternative that I found enjoyable to implement.

Answer 2

I believe the question raises an interesting point about the need for an additional data structure for parallel fetch operations to compose results efficiently.

Although a recursive reconstruction using expand is intriguing, I have opted for a sequential approach:

sequentialDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
  return of(ids).pipe(
    expand(([head, ...rest]) =>
      // working with ids in left-to-right order
      getChildren(head).pipe(
        switchMap(subChildren => {
          const acc = [...subChildren, ...rest ];
          return acc.length
            ? of(acc)
            : EMPTY;
        })
      )
    ),

    // collecting the heads {{{
    map(([head])=>head),
    toArray()
    // }}}
  );
}

* The getChildren method has been slightly modified to return Observable<number[]> instead of Observable<number>.

https://stackblitz.com/edit/rxjs-rf8d1j

This solution does not address parallel fetching directly but rather presents a sequential alternative that I found enjoyable to implement.

Answer 3

Answer №2

After experimenting a bit and manually implementing recursion instead of relying on the expand method, I developed the following solution (also updated in the stackblitz link provided above):

class Test {
  // This approach does not maintain depth-first order; it may vary based on timing.
  brokenDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
    return of(ids).pipe(
      concatMap(ids => from(ids)),
      expand(id => getChildren(id)),
      toArray()
    );
  }

  workingDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
    return from(ids).pipe(
      concatMap(id => this.parentAndChildren(getChildren, id)),
      toArray()
    );
  }

  private parentAndChildren(getChildren: Getter, id: number): Observable<number> {
    return of(id).pipe(
      concat(
        getChildren(id).pipe(
          map(child => this.parentAndChildren(getChildren, child)),
          concatAll()
        )
      ),
    );
  }

}

const getter = getChildrenWithDelay;
const rootIds = [1, 17, 20];
const test = new Test();
test.brokenDFS(getter, rootIds).subscribe(data => console.log(`Broken: ${data}`));
test.workingDFS(getter, rootIds).subscribe(data => console.log(`Working: ${data}`));

The output results (noting that the "Broken" output can vary due to timing):

Broken: 1,17,20,21,2,6,18,7,13,14,3,4,19,15,16,5,8,9,10,11,12
Working: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21

(I also adjusted the tree values from the original post to ensure the correct DFS is an array ranging from 1 to 21).

Although the workingDFS function produces the desired result, it operates significantly slower than brokenDFS, as each HTTP request must wait for preceding ones to finish. On the other hand, the brokenDFS version allows multiple requests to run concurrently (albeit not in the correct order).

Considering potential alternatives using RxJS, I might need to modify my methods by including sorting information alongside the objects of interest, executing many or all requests simultaneously, and subsequently combining everything in the correct sequence.

Answer 4

After experimenting a bit and manually implementing recursion instead of relying on the expand method, I developed the following solution (also updated in the stackblitz link provided above):

class Test {
  // This approach does not maintain depth-first order; it may vary based on timing.
  brokenDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
    return of(ids).pipe(
      concatMap(ids => from(ids)),
      expand(id => getChildren(id)),
      toArray()
    );
  }

  workingDFS(getChildren: Getter, ids: number[]): Observable<number[]> {
    return from(ids).pipe(
      concatMap(id => this.parentAndChildren(getChildren, id)),
      toArray()
    );
  }

  private parentAndChildren(getChildren: Getter, id: number): Observable<number> {
    return of(id).pipe(
      concat(
        getChildren(id).pipe(
          map(child => this.parentAndChildren(getChildren, child)),
          concatAll()
        )
      ),
    );
  }

}

const getter = getChildrenWithDelay;
const rootIds = [1, 17, 20];
const test = new Test();
test.brokenDFS(getter, rootIds).subscribe(data => console.log(`Broken: ${data}`));
test.workingDFS(getter, rootIds).subscribe(data => console.log(`Working: ${data}`));

The output results (noting that the "Broken" output can vary due to timing):

Broken: 1,17,20,21,2,6,18,7,13,14,3,4,19,15,16,5,8,9,10,11,12
Working: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21

(I also adjusted the tree values from the original post to ensure the correct DFS is an array ranging from 1 to 21).

Although the workingDFS function produces the desired result, it operates significantly slower than brokenDFS, as each HTTP request must wait for preceding ones to finish. On the other hand, the brokenDFS version allows multiple requests to run concurrently (albeit not in the correct order).

Considering potential alternatives using RxJS, I might need to modify my methods by including sorting information alongside the objects of interest, executing many or all requests simultaneously, and subsequently combining everything in the correct sequence.

Is there a way to implement depth-first retrieval in rxjs using the expand method?

Answer №1

Answer №2

Similar questions

What purpose does the # symbol serve in Angular when interpolating values?

What are the various methods of specifying function types in TypeScript?

Connecting Multiple Relationships with Many-To-Many Matches

Resolving the name error: Importing definition files from node_modules/@types in Angular

Utilizing headers in apollo watchQuery results in undefined data

Callback for dispatching a union type

What causes BehaviorSubjects in Angular RXJS to emit multiple values?

What is the best way to incorporate node_module during the iOS build process in Ionic 2?

Issues with Angular Form Builder's Form Control not updating when invalid, causing errors with ngIf statements

The listener for @ok is not being activated when using jest-test-utils with b-modal in vue-bootstrap

The element is implicitly given an 'any' type due to the fact that a string expression cannot be used to index the following type: { "1" : { "key": string}; "2" : { "key": string};}

Angular Material Popup - Interactive Map from AGM

Unspecified OrbitControls Compatibility Issue between Angular2 and Three.js

Issue with updating state in child component preventing addition to state

Angular child component displaying of table data is not looping properly

Having trouble retrieving XML response using angular 8 HttpClient

Utilize @ngrx/store to merge various reducers from feature modules

Change the value of the material slide toggle according to the user's response to the JavaScript 'confirm' dialogue

What could be causing my NextJS application to not recognize the _document.tsx file?

Launching Nest.js application from Visual Studio Code