skypilot icon indicating copy to clipboard operation
skypilot copied to clipboard

Bug: `is_chain` function inaccurately detects chain structure

Open andylizf opened this issue 3 months ago • 1 comments

The is_chain function fails to accurately detect chain structures. The current logic only checks that there's one node with an out-degree of 0 and all other nodes have an out-degree of 1. However, this overlooks cases where multiple nodes converge (i.e., nodes with an in-degree > 1), which are not valid for a chain structure.

Example: Consider a graph with paths:

A → B → D
C → B

Here, D has an out-degree of 0, and all other nodes have an out-degree of 1, yet this is clearly not a single chain.

Suggested Fix: To correctly identify a chain, the function should:

  1. Verify there is exactly one start node (in-degree 0) and one end node (out-degree 0).
  2. Ensure all other nodes have in-degree and out-degree of 1.

This correction will prevent false positives and ensure accurate chain detection.

andylizf avatar Oct 26 '24 04:10 andylizf