Implementation:Risingwavelabs Risingwave Graph Algorithms

Property	Value
Module	Graph Algorithms (algo)
File	dashboard/lib/algo.ts
Language	TypeScript
Lines	126
Type	Utility Module
Dependencies	./util (newMatrix)

Overview

algo.ts implements graph traversal algorithms (BFS) and connected component detection for use in dashboard graph visualizations. The module exports three functions: treeBfs for breadth-first tree traversal, graphBfs for general graph BFS with visited-node tracking to handle cycles, and getConnectedComponent which builds an undirected shell graph from a directed acyclic graph (DAG), assigns group numbers via BFS, and returns arrays of nodes grouped by connected component. These utilities are used for organizing and grouping nodes in the streaming topology visualizations.

Code Reference

Source Location

dashboard/lib/algo.ts

Signature

export interface GraphNode {
  nextNodes: Array<GraphNode>
}

export type GraphTraverseStep = (node: GraphNode) => boolean

export function treeBfs(root: GraphNode, step: GraphTraverseStep): void

export function graphBfs(
  root: GraphNode,
  step: GraphTraverseStep,
  neighborListKey?: string
): void

export function getConnectedComponent(
  nodes: Array<GraphNode>
): Array<Array<GraphNode>>

Import

import { treeBfs, graphBfs, getConnectedComponent, GraphNode } from "../lib/algo"

I/O Contract

treeBfs

Parameter	Type	Description
root	GraphNode	The root node to start traversal from
step	GraphTraverseStep	Callback invoked for each visited node. Return true to stop traversing the node's children; return false to continue
Returns	void	Visits each node at most once via BFS (no cycle detection)

graphBfs

Parameter	Type	Description
root	GraphNode	The starting node for traversal
step	GraphTraverseStep	Callback invoked for each visited node. Return true to stop traversing neighbors; return false to continue
neighborListKey	string (optional)	Property name for the neighbor list. Defaults to "nextNodes"
Returns	void	Visits each node at most once via BFS with a visited set to handle cycles

getConnectedComponent

Parameter	Type	Description
nodes	Array<GraphNode>	All nodes in the graph
Returns	Array<Array<GraphNode>>	A list of groups, each containing nodes in the same connected component (using original references)

Usage Examples

Tree BFS Traversal

import { treeBfs, GraphNode } from "../lib/algo"

const root: GraphNode = { nextNodes: [child1, child2] }

treeBfs(root, (node) => {
  console.log("Visited node:", node)
  return false // continue traversal to children
})

Graph BFS with Cycle Detection

import { graphBfs, GraphNode } from "../lib/algo"

graphBfs(startNode, (node) => {
  // Process each node exactly once
  processNode(node)
  return false // continue to neighbors
}, "nextNodes")

Finding Connected Components

import { getConnectedComponent } from "../lib/algo"

const allNodes: GraphNode[] = buildGraphNodes()
const groups = getConnectedComponent(allNodes)

// groups[0] = [node1, node2, ...] - first connected component
// groups[1] = [node5, node6, ...] - second connected component
groups.forEach((group, index) => {
  console.log(`Component ${index}: ${group.length} nodes`)
})

Connected Component Algorithm Detail

The getConnectedComponent function works in three phases:

// 1. Build undirected shell graph from the original DAG
for (let node of nodes) {
  let shellNode = node2shellNodes.get(node)
  for (let nextNode of node.nextNodes) {
    let nextShellNode = node2shellNodes.get(nextNode)
    shellNode.nextNodes.push(nextShellNode)
    nextShellNode.nextNodes.push(shellNode) // add reverse edge
  }
}

// 2. BFS to assign group numbers
// 3. Group original nodes by their group numbers

Related Pages

• Risingwavelabs_Risingwave_FragmentDependencyGraph - Uses graph algorithms for rendering the fragment dependency DAG
• Risingwavelabs_Risingwave_Relation_Graph_Page - Relies on graph structure for building relation dependency edges
• Risingwavelabs_Risingwave_Streaming_API_Functions - Provides the data that forms graph nodes