Implementation - 2024.1 English

Vitis Libraries

Release Date
2024.1 English

The algorithm implementation is shown in the following figure:

Figure 1 Breadth-first Search design

There are four functional blocks as shown in the figure:

  1. GetVertex is responsible to load the next vertex in the queue and pass it to the ReadGraph.
  2. ReadGraph collects all next hop vertices and pass them to the next module.
  3. ReadColor checks each next hop vertex whether it has already been discovered in the earlier stages of the BFS. This module only passes first discovered vertices to the next block.
  4. When the third functional block ends, WriteRes update the discovery, finish, level, and parent value accordingly. Also, this block pushes all the vertices collected from block three into Queue.

This system starts from pushing the source vertex into the queue and iterate until the queue is empty.