Finding cyclic product relations with TypeORM/SQL/NestJS

Question

Currently I have a Product class like so:

@Entity()
export class Product {
  @PrimaryGeneratedColumn()
  id: number;

  @ManyToMany(() => Product, (product) => product.id, {
    onDelete: 'RESTRICT',
    onUpdate: 'CASCADE',
  })
  @JoinTable({ joinColumn: { name: 'product_id_1' } })
  sub_products: Product[];

  ...
}

When a user wants to create/update a Product, I'll need to check if there's a cyclic relation between them.

For example:

1. Product A with id: 1 { sub_products: [B] }
2. Product B with id: 2 { sub_products: [C] }
3. User tries to update Product C with id: 3 with { sub_products: [A] } // should prevent this
   

What I have in mind is:

1. Construct a graph recursively by querying the database to fetch the next children. Where vertices are products, and edges represent a parent relation (from: parent, to: child)
2. Run DFS cycle detection algorithm from https://stackoverflow.com/a/53995651/13142405
   

My question is:

• In order to do (1), would it suffice if I only construct the vertex/edges of unvisited nodes before? Meaning to say I'll keep a set of visited products, and if the next product I see is in this set, I can skip construction of its vertex/edge.
• Would it suffice to prove its correctness with the following tests?
  

Tests:

1. No Cycle
   

2. Trivial Cycle
   

3. Tree (Notice how 4 is visited twice but there's no cycle)
   

4. Non-Trivial Cycle
   

Answer 1

Solved this by:

1. Constructing the vertex/edges of unvisited nodes.
2. running the algorithm as referred to in the question with a slight tweak https://stackoverflow.com/a/53995651/13142405

export interface Edge<T> {
  from: T;
  to: T;
}

export class Graph<T> {
  adjLists: Map<T, Set<T>> = new Map<T, Set<T>>();

  copy(): Graph<T> {
    const g = new Graph<T>();
    g.adjLists = new Map([...this.adjLists]);
    return g;
  }

  // immutable
  merge(other: Graph<T>): Graph<T> {
    const copy = this.copy();
    for (const [key, value] of other.adjLists) {
      if (!copy.adjLists.has(key)) {
        copy.adjLists.set(key, value);
      } else {
        // handle collision
        const cAdjList = copy.adjLists.get(key);
        copy.adjLists.set(key, new Set([...cAdjList, ...value]));
      }
    }
    return copy;
  }

  addEdge({ from, to }: Edge<T>): Graph<T> {
    if (!this.adjLists.has(from)) this.adjLists.set(from, new Set<T>());
    this.adjLists.get(from).add(to);
    return this;
  }

  getCycles(): Edge<T>[] {
    const discovered: Set<T> = new Set();
    const finished: Set<T> = new Set();
    let cycles: Edge<T>[] = [];
    for (const u of [...this.adjLists.keys()]) {
      if (!discovered.has(u) && !finished.has(u)) {
        for (const cycle of getCyclesHelper<T>({
          G: this,
          u,
          discovered,
          finished,
        })) {
          cycles.push(cycle);
        }
      }
    }

    return cycles;
  }
}

function getCyclesHelper<T>({
  G,
  u,
  discovered,
  finished,
}: {
  G: Graph<T>;
  u: T;
  discovered: Set<T>;
  finished: Set<T>;
}): Edge<T>[] {
  discovered.add(u);
  let cycles: Edge<T>[] = [];
  for (const v of G.adjLists.get(u) ?? []) {
    if (discovered.has(v)) {
      const cycle: Edge<T> = {
        from: u,
        to: v,
      };
      cycles.push(cycle);
      break;
    }

    if (!finished.has(v)) {
      for (const cycle of getCyclesHelper<T>({
        G,
        u: v,
        discovered,
        finished,
      })) {
        cycles.push(cycle);
      }
    }
  }

  discovered.delete(u);
  finished.add(u);
  return cycles;
}