پیاده‌سازی الگوریتم Kosaraju با JavaScript و TypeScript

مقدمه

در مقاله قبلی دیدیم که الگوریتم Kosaraju برای پیدا کردن Strongly Connected Components یا SCCها در یک گراف جهت‌دار استفاده می‌شود.

حالا می‌خواهیم از سطح مفهوم عبور کنیم و این الگوریتم را به صورت واقعی با JavaScript و TypeScript پیاده‌سازی کنیم.

هدف فقط نوشتن چند خط کد نیست. در پایان مقاله باید بتوانیم پاسخ این سؤال‌ها را بدهیم:

• گراف را در JavaScript چگونه نمایش دهیم؟
• DFS اول دقیقاً چه چیزی ذخیره می‌کند؟
• Transpose Graph چگونه ساخته می‌شود؟
• چرا DFS دوم SCCها را جدا می‌کند؟
• چگونه نسخه TypeScript تمیز و type-safe بنویسیم؟
• پیچیدگی زمانی و حافظه چقدر است؟
• در پروژه‌های واقعی چه مشکلاتی ممکن است رخ دهد؟

مرور سریع Kosaraju

Kosaraju سه مرحله اصلی دارد:

1. DFS روی گراف اصلی
2. ساخت Transpose Graph
3. DFS روی Transpose بر اساس Finish Order

نمای کلی:

Original Graph
      ↓
First DFS
      ↓
Finish Order
      ↓
Transpose Graph
      ↓
Second DFS
      ↓
SCCs

اگر گراف زیر را داشته باشیم:

0 → 1
1 → 2
2 → 0
1 → 3
3 → 4
4 → 3

انتظار داریم دو SCC اصلی پیدا کنیم:

{0, 1, 2}
{3, 4}

مرحله اول: نمایش گراف در JavaScript

یکی از بهترین روش‌ها برای نمایش یک گراف sparse استفاده از Adjacency List است.

مثلاً:

const graph = new Map();

graph.set(0, [1]);
graph.set(1, [2, 3]);
graph.set(2, [0]);
graph.set(3, [4]);
graph.set(4, [3]);

ساختار بالا یعنی:

0 → 1
1 → 2, 3
2 → 0
3 → 4
4 → 3

می‌توانیم آن را به صورت شیء ساده هم بنویسیم:

const graph = {
  0: [1],
  1: [2, 3],
  2: [0],
  3: [4],
  4: [3]
};

اما Map برای پیاده‌سازی عمومی‌تر انتخاب بهتری است، چون کلیدهای آن الزاماً string نیستند.

چرا Adjacency List؟

فرض کنید گرافی با یک میلیون Vertex داشته باشیم اما هر Vertex فقط چند Edge داشته باشد.

استفاده از Adjacency Matrix می‌تواند حافظه بسیار زیادی مصرف کند.

Adjacency List فقط Edgeهایی را نگهداری می‌کند که واقعاً وجود دارند.

بنابراین برای Kosaraju معمولاً ساختار مناسبی است.

مرحله دوم: DFS اول و Finish Order

هدف DFS اول صرفاً Visit کردن Vertexها نیست.

ما باید Vertex را بعد از تمام همسایه‌هایش داخل Stack قرار دهیم.

کد:

function fillOrder(node, graph, visited, stack) {
  visited.add(node);

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      fillOrder(neighbor, graph, visited, stack);
    }
  }

  stack.push(node);
}

به این خط توجه کنید:

stack.push(node);

این دستور بعد از پردازش تمام Neighborها اجرا می‌شود.

یعنی Stack بر اساس Finish Time ساخته می‌شود.

چرا Push در انتهای DFS انجام می‌شود؟

اگر کد را این‌طور بنویسیم:

visited.add(node);
stack.push(node);

دیگر Finish Order نداریم؛ فقط Discovery Order را ذخیره کرده‌ایم.

اما Kosaraju به ترتیب پایان پردازش Vertexها نیاز دارد.

پس ساختار صحیح این است:

Visit node
   ↓
Visit all neighbors
   ↓
Finish node
   ↓
Push to stack

اجرای DFS روی تمام Vertexها

ممکن است گراف از ابتدا connected نباشد.

پس نمی‌توانیم فقط DFS را از Vertex شماره صفر اجرا کنیم.

باید تمام Vertexها را بررسی کنیم:

const visited = new Set();
const stack = [];

for (const node of graph.keys()) {
  if (!visited.has(node)) {
    fillOrder(node, graph, visited, stack);
  }
}

در پایان، stack ترتیب Finish شدن Vertexها را نگهداری می‌کند.

مرحله سوم: ساخت Transpose Graph

Transpose Graph یعنی جهت تمام Edgeها را معکوس کنیم.

اگر داشته باشیم:

A → B

در Transpose داریم:

A ← B

یا معادل:

B → A

تابع JavaScript:

function transposeGraph(graph) {
  const transpose = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor).push(node);
    }
  }

  return transpose;
}

مثلاً:

Original:
0 → 1
1 → 2
2 → 0

تبدیل می‌شود به:

Transpose:
1 → 0
2 → 1
0 → 2

نکته مهم این است که Transpose کردن گراف اعضای SCCها را تغییر نمی‌دهد.

مرحله چهارم: DFS دوم برای جمع‌آوری SCCها

حالا DFS دیگری می‌خواهیم که Vertexهای یک Component را جمع‌آوری کند.

function collectComponent(node, graph, visited, component) {
  visited.add(node);
  component.push(node);

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      collectComponent(neighbor, graph, visited, component);
    }
  }
}

این بار هدف Finish Time نیست.

فقط تمام Vertexهایی را که در DFS فعلی پیدا می‌کنیم داخل یک Array قرار می‌دهیم.

پیاده‌سازی کامل Kosaraju با JavaScript

حالا تمام قسمت‌ها را کنار هم قرار می‌دهیم:

function kosaraju(graph) {
  const visited = new Set();
  const stack = [];

  function fillOrder(node) {
    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        fillOrder(neighbor);
      }
    }

    stack.push(node);
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      fillOrder(node);
    }
  }

  const transpose = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor).push(node);
    }
  }

  visited.clear();

  const components = [];

  function collectComponent(node, component) {
    visited.add(node);
    component.push(node);

    for (const neighbor of transpose.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        collectComponent(neighbor, component);
      }
    }
  }

  while (stack.length > 0) {
    const node = stack.pop();

    if (!visited.has(node)) {
      const component = [];
      collectComponent(node, component);
      components.push(component);
    }
  }

  return components;
}

تست نسخه JavaScript

گراف نمونه:

const graph = new Map([
  [0, [1]],
  [1, [2, 3]],
  [2, [0]],
  [3, [4]],
  [4, [3]]
]);

console.log(kosaraju(graph));

خروجی ممکن است چیزی شبیه این باشد:

[
  [0, 2, 1],
  [3, 4]
]

ترتیب Vertexها داخل SCC مهم نیست.

بنابراین:

[0, 2, 1]

و:

[0, 1, 2]

از نظر منطقی همان Component هستند.

حالا نسخه TypeScript

در TypeScript می‌توانیم ساختار گراف را به شکل دقیق‌تری تعریف کنیم.

type Graph<T> = Map<T, T[]>;

این تعریف به ما اجازه می‌دهد Vertexها فقط number نباشند.

مثلاً می‌توانیم داشته باشیم:

Graph<string>

برای گرافی شامل نام Serviceها.

پیاده‌سازی Generic با TypeScript

type Graph<T> = Map<T, T[]>;

function kosaraju<T>(graph: Graph<T>): T[][] {
  const visited = new Set<T>();
  const stack: T[] = [];

  const fillOrder = (node: T): void => {
    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        fillOrder(neighbor);
      }
    }

    stack.push(node);
  };

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      fillOrder(node);
    }
  }

  const transpose: Graph<T> = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor)!.push(node);
    }
  }

  visited.clear();

  const components: T[][] = [];

  const collectComponent = (
    node: T,
    component: T[]
  ): void => {
    visited.add(node);
    component.push(node);

    for (const neighbor of transpose.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        collectComponent(neighbor, component);
      }
    }
  };

  while (stack.length > 0) {
    const node = stack.pop()!;

    if (!visited.has(node)) {
      const component: T[] = [];
      collectComponent(node, component);
      components.push(component);
    }
  }

  return components;
}

این نسخه برای number، string یا بسیاری از انواع دیگر قابل استفاده است.

مثال واقعی‌تر: وابستگی Microserviceها

فرض کنیم ساختار سیستم ما چنین باشد:

user → payment
payment → notification
notification → user

report → analytics
analytics → report

admin → user

می‌توانیم آن را در TypeScript این‌طور تعریف کنیم:

const services: Graph<string> = new Map([
  ["user", ["payment"]],
  ["payment", ["notification"]],
  ["notification", ["user"]],
  ["report", ["analytics"]],
  ["analytics", ["report"]],
  ["admin", ["user"]]
]);

console.log(kosaraju(services));

خروجی مفهومی:

[
  ["admin"],
  ["report", "analytics"],
  ["user", "payment", "notification"]
]

اینجا فوراً می‌توانیم دو dependency cycle مهم را ببینیم:

user
 ↓
payment
 ↓
notification
 ↓
user

و:

report ↔ analytics

اما admin به تنهایی یک SCC است.

این مثال نشان می‌دهد Kosaraju چگونه می‌تواند از یک الگوریتم دانشگاهی به یک ابزار تحلیل معماری تبدیل شود.

آیا SCC تک‌عضوی معتبر است؟

بله.

یک Vertex که عضو SCC بزرگ‌تری نیست، خودش یک SCC تک‌عضوی محسوب می‌شود.

مثلاً:

A → B

در صورتی که مسیر برگشت وجود نداشته باشد، داریم:

SCC 1 = {A}
SCC 2 = {B}

این نکته هنگام بررسی خروجی الگوریتم مهم است.

نسخه‌ای که فقط Cycleهای واقعی را برمی‌گرداند

گاهی در پروژه فقط SCCهایی برایمان مهم هستند که Circular Dependency ایجاد کرده‌اند.

می‌توانیم بعد از اجرای الگوریتم بنویسیم:

const cycles = kosaraju(services).filter(
  component => component.length > 1
);

حالا SCCهای تک‌عضوی حذف می‌شوند.

اما یک نکته وجود دارد.

Vertex می‌تواند Self Loop داشته باشد:

A → A

در این حالت Component فقط یک عضو دارد ولی همچنان Cycle وجود دارد.

پس در یک Circular Dependency Detector واقعی باید Self Loop را هم بررسی کنیم.

پیچیدگی زمانی

Kosaraju سه عملیات اصلی انجام می‌دهد.

DFS اول

O(V + E)

ساخت Transpose

O(V + E)

DFS دوم

O(V + E)

بنابراین:

O(V + E) + O(V + E) + O(V + E)

که در Big-O برابر است با:

O(V + E)

پیچیدگی حافظه

برای ذخیره موارد زیر حافظه نیاز داریم:

• Original Graph
• Transpose Graph
• Visited Set
• Finish Stack
• Components

در نمایش Adjacency List، مصرف حافظه کلی معمولاً:

O(V + E)

است.

یکی از تفاوت‌های Kosaraju با برخی روش‌های دیگر این است که معمولاً یک نسخه Transpose از گراف نیز نگهداری می‌شود.

مشکل Recursion در JavaScript

کدهای بالا برای آموزش بسیار خوانا هستند، اما یک مسئله عملی دارند.

DFS به صورت recursive نوشته شده است.

در یک Graph بسیار عمیق ممکن است با خطایی مانند این مواجه شویم:

RangeError: Maximum call stack size exceeded

مثلاً اگر گراف چیزی شبیه این باشد:

1 → 2 → 3 → 4 → ... → 500000

عمق Recursion بسیار زیاد می‌شود.

در سیستم‌های production بهتر است برای Graphهای بزرگ، DFS iterative را در نظر بگیریم.

DFS Iterative ساده

نسخه ساده DFS را می‌توان این‌طور نوشت:

function dfsIterative<T>(
  start: T,
  graph: Graph<T>
): Set<T> {
  const visited = new Set<T>();
  const stack: T[] = [start];

  while (stack.length > 0) {
    const node = stack.pop()!;

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }

  return visited;
}

اما دقت کنید که DFS اول Kosaraju به Finish Order نیاز دارد، بنابراین تبدیل آن به نسخه Iterative کمی پیچیده‌تر از DFS عادی است.

اشتباه رایج شماره 1: فراموش کردن Vertexهای بدون خروجی

فرض کنید:

A → B

اگر Graph را فقط هنگام اضافه کردن Edge بسازیم، ممکن است B هرگز به عنوان Key در Map قرار نگیرد.

مثلاً:

graph.set("A", ["B"]);

ولی:

graph.has("B")

برابر false باشد.

بهتر است تمام Vertexها در ساختار Graph ثبت شوند:

graph.set("A", ["B"]);
graph.set("B", []);

اشتباه رایج شماره 2: Reset نکردن visited

بعد از DFS اول، تمام Vertexها داخل visited قرار دارند.

قبل از DFS دوم باید بنویسیم:

visited.clear();

در غیر این صورت DFS دوم هیچ کاری انجام نمی‌دهد.

اشتباه رایج شماره 3: اشتباه گرفتن Finish Order با Visit Order

این اشتباه بسیار مهم است.

در DFS اول نباید Vertex را هنگام ورود داخل Stack نهایی قرار دهیم.

اشتباه:

visited.add(node);
stack.push(node);

صحیح:

visited.add(node);

for (...) {
  ...
}

stack.push(node);

Kosaraju به Post-order / Finish Order احتیاج دارد.

اشتباه رایج شماره 4: اجرای DFS دوم روی Graph اصلی

مرحله دوم DFS باید روی:

Transpose Graph

اجرا شود، نه Graph اصلی.

این اشتباه باعث می‌شود SCCها به درستی جدا نشوند.

اشتباه رایج شماره 5: استفاده از shift برای Stack

در JavaScript برای Stack بهتر است از:

push()
pop()

استفاده کنیم.

استفاده مکرر از:

shift()

می‌تواند هزینه بیشتری داشته باشد، زیرا عناصر Array باید جابه‌جا شوند.

ساخت یک کلاس Graph در TypeScript

برای پروژه بزرگ‌تر می‌توانیم Graph را داخل یک Class قرار دهیم:

class DirectedGraph<T> {
  private adjacency = new Map<T, T[]>();

  addVertex(vertex: T): void {
    if (!this.adjacency.has(vertex)) {
      this.adjacency.set(vertex, []);
    }
  }

  addEdge(from: T, to: T): void {
    this.addVertex(from);
    this.addVertex(to);

    this.adjacency.get(from)!.push(to);
  }

  getAdjacencyList(): Graph<T> {
    return this.adjacency;
  }
}

استفاده:

const graph = new DirectedGraph<string>();

graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");

graph.addEdge("C", "D");
graph.addEdge("D", "E");
graph.addEdge("E", "D");

const components = kosaraju(
  graph.getAdjacencyList()
);

console.log(components);

این ساختار برای پروژه واقعی خواناتر و قابل توسعه‌تر است.

نوشتن تست ساده

برای الگوریتم‌ها فقط دیدن console.log کافی نیست.

مثلاً می‌توانیم انتظار داشته باشیم:

const result = kosaraju(graph);

شامل دو Component باشد:

{A, B, C}
{D, E}

چون ترتیب عضوهای SCC الزاماً ثابت نیست، بهتر است قبل از مقایسه آن‌ها را normalize کنیم.

مثلاً:

const normalize = <T extends string | number>(
  components: T[][]
): string[] => {
  return components
    .map(component => [...component].sort().join(","))
    .sort();
};

سپس:

const actual = normalize(result);
const expected = normalize([
  ["A", "B", "C"],
  ["D", "E"]
]);

console.log(actual);
console.log(expected);

JavaScript یا TypeScript؟

هسته الگوریتم در هر دو زبان تقریباً یکسان است.

JavaScript برای آموزش سریع و Prototype مناسب است.

TypeScript در پروژه‌های بزرگ مزایای بیشتری دارد:

• type safety
• Generic Graphها
• تشخیص خطا هنگام توسعه
• API واضح‌تر
• refactoring امن‌تر

برای یک پروژه production که Graph بخشی از Domain اصلی سیستم است، نسخه TypeScript معمولاً انتخاب مناسب‌تری خواهد بود.

Kosaraju چه زمانی انتخاب خوبی است؟

Kosaraju زمانی گزینه خوبی است که:

• گراف جهت‌دار داریم.
• باید تمام SCCها را پیدا کنیم.
• سادگی پیاده‌سازی اهمیت دارد.
• ساخت Transpose Graph برای ما مشکل خاصی ایجاد نمی‌کند.
• O(V + E) عملکرد مناسبی برای مسئله است.

اگر محدودیت حافظه بسیار شدید باشد یا بخواهیم SCCها را با یک DFS اصلی پیدا کنیم، الگوریتم‌هایی مانند Tarjan نیز ارزش بررسی دارند.

نسخه ذهنی الگوریتم

اگر بخواهیم کل مقاله را در چند خط خلاصه کنیم:

First DFS:
Who finishes last?

        ↓

Reverse every edge

        ↓

Second DFS:
Process nodes in reverse finish order

        ↓

Every DFS tree = one SCC

این مدل ذهنی برای به خاطر سپردن Kosaraju بسیار مفید است.

جمع‌بندی

در این مقاله Kosaraju را با JavaScript و TypeScript پیاده‌سازی کردیم.

مراحل اصلی عبارت بودند از:

1. نمایش Graph با Adjacency List
2. DFS اول و ذخیره Finish Order
3. ساخت Transpose Graph
4. Reset کردن visited
5. DFS دوم بر اساس Stack
6. جمع‌آوری SCCها

پیچیدگی زمانی الگوریتم با Adjacency List برابر است با:

O(V + E)

و مصرف حافظه نیز در همان مرتبه قرار دارد.

اما نکته مهم‌تر این است که حالا می‌توانیم Kosaraju را از یک مفهوم تئوری به یک ابزار واقعی تبدیل کنیم؛ مثلاً برای پیدا کردن Circular Dependency بین Moduleها، Packageها یا Microserviceها.

اگر فقط یک نکته از پیاده‌سازی به خاطر بسپارید، این باشد:

DFS اول ترتیب درست پردازش را پیدا می‌کند، Transpose جهت روابط را برمی‌گرداند و DFS دوم مرز واقعی SCCها را آشکار می‌کند.

در ادامه این مجموعه می‌توانیم نسخه Production-ready و Iterative الگوریتم را بررسی کنیم یا Kosaraju را با Tarjan's Algorithm مقایسه کنیم.