# فصل ۰۸ — پروژه: یک شبکهٔ واقعی را پیمایش کن

<div dir="rtl">

# فصل ۰۸ — پروژه: یک شبکهٔ واقعی را پیمایش کن

## در این فصل چه یاد می‌گیری

هفت فصلِ این ترم را پشتِ سر گذاشتیم. **این فصل یکی از ساختارهایشان را انتخاب می‌کند و کارِ کامل را انجام می‌دهد:** یک شبکه با `4,000` گره و `11,994` یال، انتخابِ نمایش با عدد، پیمایش، تأییدِ `V + 2E`، و آخر از همه **اعلامِ صریحِ چیزی که حساب نکردیم.**

آخرین قسمت مهم‌ترینش است. قطرِ دقیقِ این شبکه `111,952,000` گام می‌خواهد؛ ما با `55,976` گام یک حدِ پایین می‌گیریم — **و در یکی از دو اندازه‌ای که جوابِ دقیق را داریم، آن حدِ پایین یک واحد کمتر از جوابِ درست درمی‌آید.** همان را هم گزارش می‌کنیم.

![شبکه‌ای با چند گرهِ بسیار پرارتباط که بقیهٔ گره‌ها دورشان حلقه زده‌اند](/lesson-assets/t5-s08-project-graph/prompt/01-image-hub-network.png)

آخر این فصل می‌توانی:

- یک شبکهٔ تکرارپذیر بسازی و توزیعِ درجه‌اش را نگاه کنی
- **نمایش را با عدد انتخاب کنی**، نه با عادت
- فاصله‌ها و مؤلفه‌ها را با `BFS` بگیری و هزینه‌اش را تأیید کنی
- **محدودیتِ گزارشت را با عدد بنویسی**، نه با «تقریباً»

## قبل از شروع

**از فصلِ ۵:** فهرستِ مجاورت در برابرِ ماتریس، `sys.getsizeof` و چگالی. **از فصلِ ۶:** `BFS`، مجموعهٔ دیده‌شده‌ها، مؤلفه‌ها و شمارندهٔ `V + 2E`. **از فصلِ ۷:** اینکه بعضی سؤال‌ها را نباید پرسید.

**دربارهٔ داده صادق باشیم:** شبکهٔ این فصل ساختگی است و با `SEED` ساخته می‌شود، ولی **شکلش** شبیهِ شبکه‌های واقعی است: هر گرهِ تازه به گره‌هایی وصل می‌شود که از قبل پرارتباط‌ترند، و نتیجه‌اش چند گرهِ خیلی پرترافیک است و انبوهی گرهِ کم‌ارتباط.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-08-project-graph.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. شبکه، و شکلش

</div>

```python
from collections import deque

LINKS = 3


def make_network(node_count, seed=SEED):
    """هر گرهِ تازه سه پیوند می‌سازد، و گرهی که از قبل پرپیوندتر است شانسِ بیشتری دارد."""
    rng = random.Random(seed)
    pool = []
    edges = set()
    for a in range(LINKS):
        for b in range(a + 1, LINKS):
            edges.add((a, b))
            pool.append(a)
            pool.append(b)
    for node in range(LINKS, node_count):
        chosen = set()
        while len(chosen) < LINKS:
            chosen.add(rng.choice(pool))
        for other in sorted(chosen):
            edges.add((other, node))
            pool.append(other)
            pool.append(node)
    graph = {node: [] for node in range(node_count)}
    for a, b in sorted(edges):
        graph[a].append(b)
        graph[b].append(a)
    for node in graph:
        graph[node].sort()          # ترتیبِ ثابت، تا هر اجرا همان جواب را بدهد
    return graph, sorted(edges)


network, links = make_network(4_000)
degrees = sorted((len(nbrs) for nbrs in network.values()), reverse=True)
print(f"V = {len(network):,}  ·  E = {len(links):,}")
print("پنج درجهٔ اول :", degrees[:5])
print("پنج درجهٔ آخر :", degrees[-5:])
print("میانگینِ درجه :", f"{2 * len(links) / len(network):.2f}")
print("گره‌هایی با درجهٔ ۳ یا کمتر:", f"{sum(1 for d in degrees if d <= 3):,}")
```

```text
V = 4,000  ·  E = 11,994
پنج درجهٔ اول : [229, 222, 145, 105, 101]
پنج درجهٔ آخر : [3, 3, 3, 3, 3]
میانگینِ درجه : 6.00
گره‌هایی با درجهٔ ۳ یا کمتر: 1,596
```

<div dir="rtl">

**میانگینِ درجه `6.00` است و هیچ چیزی دربارهٔ این شبکه نمی‌گوید.** پرارتباط‌ترین گره `229` همسایه دارد — بیش از سی و هشت برابرِ میانگین — و `1,596` گره، یعنی حدودِ چهار دهمِ کلِ شبکه، فقط سه همسایه دارند.

**این همان درسِ ترمِ ۳ فصلِ ۴ است، این بار روی یک گراف:** میانگین به‌تنهایی شکلِ توزیع را پنهان می‌کند. و این‌جا پنهان کردنش گران است، چون کلِ رفتارِ پیمایش به همان چند گرهِ پرترافیک بند است.

## ۲. انتخابِ نمایش، با عدد

</div>

```python
def list_bytes(graph):
    return sys.getsizeof(graph) + sum(sys.getsizeof(nbrs) for nbrs in graph.values())


def matrix_bytes(node_count):
    rows = [bytearray(node_count) for _ in range(node_count)]
    return sys.getsizeof(rows) + sum(sys.getsizeof(row) for row in rows)


chosen_bytes = list_bytes(network)
other_bytes = matrix_bytes(len(network))
print(f"فهرستِ مجاورت : {chosen_bytes:>12,} بایت")
print(f"ماتریسِ مجاورت: {other_bytes:>12,} بایت")
print(f"نسبت          : {other_bytes / chosen_bytes:>12.0f} برابر")
print(f"چگالیِ این شبکه: {len(links) / (len(network) * (len(network) - 1) / 2):.5f}")
```

```text
فهرستِ مجاورت :      613,624 بایت
ماتریسِ مجاورت:   16,261,048 بایت
نسبت          :           27 برابر
چگالیِ این شبکه: 0.00150
```

<div dir="rtl">

**تصمیم و دلیلش، در دو سطر:** چگالیِ این شبکه `0.00150` است و نقطهٔ سربه‌سرِ فصلِ ۵ روی `0.107` بود. **هفتاد برابر زیرِ آن آستانه‌ایم، پس فهرستِ مجاورت.** بیست و هفت برابر کم‌حافظه‌تر، و اگر گراف بزرگ‌تر شود این نسبت فقط بدتر می‌شود.

## ۳. پیمایش: مؤلفه‌ها و فاصله‌ها

</div>

```python
def bfs_distances(graph, start):
    dist = {start: 0}
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        for nbr in graph[node]:
            if nbr not in dist:
                dist[nbr] = dist[node] + 1
                waiting.append(nbr)
    return dist


def sweep(graph):
    """تعدادِ مؤلفه‌ها و کارِ شمرده‌شدهٔ یک پیمایشِ کامل."""
    seen = set()
    components = 0
    work = 0
    for start in sorted(graph):
        if start in seen:
            continue
        components += 1
        seen.add(start)
        waiting = deque([start])
        while waiting:
            node = waiting.popleft()
            work += 1
            for nbr in graph[node]:
                work += 1
                if nbr not in seen:
                    seen.add(nbr)
                    waiting.append(nbr)
    return components, work


hub = max(network, key=lambda node: (len(network[node]), -node))
dist = bfs_distances(network, hub)
print("پرپیوندترین گره:", hub, "با درجهٔ", len(network[hub]))
print("چند گره از آن دیده می‌شود؟", len(dist), "از", len(network))
print(f"\n{'فاصله':>8}{'تعدادِ گره':>14}")
for step in range(max(dist.values()) + 1):
    print(f"{step:>8}{sum(1 for d in dist.values() if d == step):>14,}")
```

```text
پرپیوندترین گره: 0 با درجهٔ 229
چند گره از آن دیده می‌شود؟ 4000 از 4000

   فاصله    تعدادِ گره
       0             1
       1           229
       2         1,654
       3         2,011
       4           105
```

<div dir="rtl">

**از پرترافیک‌ترین گره، هر چهار هزار گره در حداکثر چهار قدم دیده می‌شوند.** و ستونِ دوم شکلِ آشنایی دارد: تعدادِ گره‌ها تا فاصلهٔ ۳ بالا می‌رود و بعد یکهو می‌افتد — چون دیگر گرهِ ندیده‌ای باقی نمانده.

**این همان خاصیتی است که پیمایشِ شبکه‌های بزرگ را ممکن می‌کند:** با درجهٔ متوسطِ ۶، تعدادِ گره‌های قابلِ دسترس در هر قدم چند برابر می‌شود، پس **فاصله‌ها خیلی کندتر از تعدادِ گره‌ها بزرگ می‌شوند.** بخشِ ۵ همین را در دو اندازه نشان می‌دهد: قطرِ `V = 500` و `V = 1,000` هر دو `6` است.

## ۴. هزینه، دوباره تأییدشده

> 🤔 **اول حدس بزن:** این شبکه به‌ازای هر گره سه یالِ تازه می‌سازد. اگر تعدادِ گره‌ها را دو برابر کنیم، کارِ یک پیمایشِ کامل چند برابر می‌شود؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
parts, work = sweep(network)
print("مؤلفه‌ها:", parts, "· کارِ شمرده‌شده:", f"{work:,}")
print("برابرِ V + 2E است؟", work == len(network) + 2 * len(links))

SIZES4 = [500, 1_000, 2_000, 4_000]
table([(v, sweep(make_network(v)[0])[1]) for v in SIZES4], "کار", ",d")
```

```text
مؤلفه‌ها: 1 · کارِ شمرده‌شده: 27,988
برابرِ V + 2E است؟ True
         n               کار     نسبت به سطر قبل
       500             3,488                   —
     1,000             6,988                2.00
     2,000            13,988                2.00
     4,000            27,988                2.00
```

<div dir="rtl">

**یک مؤلفه، و `V + 2E` دقیق.** (ستونِ `n` این جدول تعدادِ گره‌هاست، یعنی همان `V`.)

یک مؤلفه بودن اتفاقی نیست: **هر گرهِ تازه در لحظهٔ ساخته شدن به شبکهٔ موجود وصل می‌شود**، پس هیچ‌وقت تکهٔ جدا نمی‌ماند. این با گرافِ تصادفیِ فصلِ ۶ فرق دارد که با همان نسبتِ یال، **پنج** مؤلفه داشت — و همین یک تفاوت نشان می‌دهد **شیوهٔ ساختِ داده به‌اندازهٔ اندازه‌اش مهم است.**

## ۵. چیزی که حساب نکردیم

**قطرِ یک شبکه**، یعنی بلندترین کوتاه‌ترین‌مسیرِ بینِ هر دو گره، جوابِ دقیقش یک `BFS` **از هر گره** می‌خواهد. راهِ ارزان‌تر «دو پیمایش» است: از یک گره `BFS` بزن و دورترین گره را پیدا کن، بعد از **آن** یکی `BFS` بزن. **جوابش یک حدِ پایین است، نه قطر.**

</div>

```python
def double_sweep(graph, start):
    """حدِ پایینِ قطر: دورترین گره از start، بعد دورترین گره از آن."""
    first = bfs_distances(graph, start)
    far = max(first, key=lambda node: (first[node], -node))
    second = bfs_distances(graph, far)
    end = max(second, key=lambda node: (second[node], -node))
    return second[end], far, end


guess, a, b = double_sweep(network, 0)
print(f"حدِ پایینِ قطر: {guess}  ·  بین گرهٔ {a} و گرهٔ {b}")

exact_from = [500, 1_000]
for v in exact_from:
    part = make_network(v)[0]
    worst = 0
    for node in sorted(part):
        worst = max(worst, max(bfs_distances(part, node).values()))
    approx = double_sweep(part, 0)[0]
    print(f"V = {v:>5,}  ·  قطرِ دقیق {worst}  ·  حدِ پایین {approx}"
          f"  ·  {v} بار BFS به‌جای ۲ بار")
```

```text
حدِ پایینِ قطر: 6  ·  بین گرهٔ 777 و گرهٔ 1622
V =   500  ·  قطرِ دقیق 6  ·  حدِ پایین 5  ·  500 بار BFS به‌جای ۲ بار
V = 1,000  ·  قطرِ دقیق 6  ·  حدِ پایین 6  ·  1000 بار BFS به‌جای ۲ بار
```

<div dir="rtl">

**در `V = 500` تقریب `5` داد و جوابِ درست `6` بود؛ در `V = 1,000` هر دو `6` شدند.** یعنی این روش گاهی درست است و گاهی یک واحد کم می‌آورد — **و ما هیچ راهی نداریم بفهمیم روی شبکهٔ ۴٬۰۰۰ گره‌ای کدامش اتفاق افتاده.**

</div>

```python
cost_one = len(network) + 2 * len(links)
print(f"یک BFS روی این شبکه: {cost_one:,} گام")
print(f"قطرِ دقیق ({len(network):,} بار BFS): {len(network) * cost_one:,} گام")
print(f"حدِ پایین (۲ بار BFS)          : {2 * cost_one:,} گام")
print(f"نسبت                           : {len(network) // 2:,} برابر")
```

```text
یک BFS روی این شبکه: 27,988 گام
قطرِ دقیق (4,000 بار BFS): 111,952,000 گام
حدِ پایین (۲ بار BFS)          : 55,976 گام
نسبت                           : 2,000 برابر
```

<div dir="rtl">

**دو هزار برابر، برای عددی که ممکن است یکی کمتر باشد.** این یک معاملهٔ آگاهانه است و **کلِ فرقش با یک اشتباه، این است که نوشته شده باشد.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک پیمایشِ کامل با شمارندهٔ دستی در برابرِ فرمولِ `V + 2E`، و قطرِ تقریبی در برابرِ قطرِ دقیق روی دو اندازه‌ای که دقیقش قابلِ محاسبه بود. **در کدام بازهٔ `n`؟** ۵۰۰ تا ۴٬۰۰۰ گره با `E ≈ 3V`. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ همه‌چیز شمارش است و با `SEED` ثابت قطعی. **هیچ عددِ ثانیه‌ای در این فصل نیست.**

**گزارشِ نهاییِ این پروژه، در چهار خط:**

- **نمایش:** فهرستِ مجاورت. دلیل: چگالی `0.00150`، هفتاد برابر زیرِ نقطهٔ سربه‌سرِ `0.107`؛ حافظه `613,624` بایت به‌جای `16,261,048`.
- **پیمایش:** یک `BFS` کامل، `27,988` گام، دقیقاً `V + 2E`، ستونِ نسبتِ `2.00` روی چهار اندازه.
- **یافته:** یک مؤلفه، درجهٔ بیشینه `229` در برابرِ میانگینِ `6.00`، همه‌چیز در حداکثر چهار قدم از پرترافیک‌ترین گره.
- **محدودیت:** قطر **اندازه‌گیری نشده**؛ فقط یک حدِ پایینِ `6` داریم که در یکی از دو آزمونِ کنترلی یک واحد کم آورد. جوابِ دقیق `111,952,000` گام می‌خواست.

> ✅ **چک کن:** `LINKS` را از `3` به `2` تغییر بده و بخش‌های ۱، ۳ و ۴ را دوباره بگیر. **تعدادِ مؤلفه‌ها باید `1` بماند** — چون هر گره باز هم به شبکه وصل می‌شود — **ولی `E` باید به `7,997` برسد، کارِ شمرده‌شده به `19,994`، و جدولِ فاصله‌ها یک سطر بلندتر شود (تا فاصلهٔ ۵ به‌جای ۴).** اگر مؤلفه‌ها بیشتر از یک شد، جای دیگری را دست زده‌ای. **و `LINKS = 1` را امتحان نکن:** آن حلقهٔ اولِ `make_network` هیچ یالی نمی‌سازد، `pool` خالی می‌ماند و `rng.choice` روی فهرستِ خالی `IndexError` می‌دهد.

> 🔧 **اگر کار نکرد:** پرتکرارترین خطای این پروژه پیدا کردنِ «پرترافیک‌ترین گره» است. `max` روی یک `dict` کلیدها را می‌دهد و روی `.values()` مقدارها را — و اگر اشتباهی دومی را بگیری، **یک `list` دستت می‌آید که فکر می‌کنی یک گره است:**

</div>

```python
try:
    busiest = max(network.values(), key=len)
    print(bfs_distances(network, busiest))
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
print("راهِ درست:", max(network, key=lambda node: (len(network[node]), -node)))
```

```text
TypeError: unhashable type: 'list'
راهِ درست: 0
```

<div dir="rtl">

**همان `TypeError` ترمِ ۳ فصلِ ۶، در یک لباسِ تازه.** `bfs_distances` می‌خواهد گره را کلیدِ یک `dict` کند و `list` نمی‌تواند کلید باشد. **و `key=lambda node: (len(network[node]), -node)` یک جزئیاتِ اضافه هم دارد که عمدی است:** آن `-node` گرهِ کوچک‌ترشماره را در حالتِ تساوی برنده می‌کند، تا **در هر اجرا همان گره انتخاب شود.**

> 🤖 **از دستیارت بپرس:** **گزارشِ چهارخطیِ بالا را جلویش بگذار و بپرس:** «چه چیزی در این گزارش کم است؟» — جوابِ خوب باید سراغِ چیزی برود که ما نگفته‌ایم، نه چیزی که گفته‌ایم. بعد این را هم بپرس: **«اگر بخواهم قطرِ دقیق را روی یک شبکهٔ یک‌میلیون‌گره‌ای بگیرم، چند گام می‌شود؟»** و جوابش را با جدولِ فصلِ ۷ بسنج.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| hub | هاب | گرهی که درجه‌اش خیلی بیشتر از میانگین است |
| degree distribution | دِگری دیستریبیوشن | توزیعِ درجه: اینکه چند گره چه تعداد همسایه دارند |
| diameter | دایامتر | قطر: بلندترین کوتاه‌ترین‌مسیرِ بینِ هر دو گره |
| lower bound | لوئر باند | حدِ پایین: عددی که جوابِ واقعی حتماً از آن کمتر نیست |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا میانگینِ درجه دربارهٔ این شبکه تقریباً هیچ چیزی نمی‌گوید؟

**تمرینِ اجباری:** پرارتباط‌ترین گره را از شبکه حذف کن — خودش و همهٔ یال‌هایش — و `sweep` را دوباره بگیر. **سؤالِ اصلی: تعدادِ مؤلفه‌ها چه می‌شود، و بزرگ‌ترین مؤلفه چند گره دارد؟** حالا همین کار را با حذفِ یک گرهِ **تصادفی** تکرار کن. **جوابت باید یک جدولِ دوسطری باشد و یک جملهٔ نتیجه.**

**تمرینِ ستاره‌دار ⭐:** `double_sweep` را طوری تغییر بده که از **ده** گرهِ شروعِ مختلف اجرا شود و بزرگ‌ترین نتیجه را بردارد. **قبل از اجرا پیش‌بینی کن** حدِ پایین بهتر می‌شود یا نه، و **هزینه‌اش چند برابر می‌شود**. حالا هر دو نسخه را روی `V = 500` و `V = 1,000` — جایی که قطرِ دقیق را داری — اندازه بگیر و بنویس آیا خطای یک‌واحدیِ `V = 500` برطرف شد. **و سؤالِ آخر: اگر برطرف شد، آیا حالا می‌توانی ادعا کنی که جوابِ `V = 4,000` هم دقیق است؟**

## در فصل بعد

ترمِ ۵ تمام شد. **برای هر ساختاری که این پنج ترم ساختی یک جدول داری** — و هنوز یک بار هم بینِ دو تای آن‌ها با نوشتنِ **شکلِ مسئله** انتخاب نکرده‌ای.

**ترمِ بعد دقیقاً همین است:** الگوی دسترسی، نسبتِ خواندن به نوشتن، بازهٔ واقعیِ `n` — و بعد یک جدولِ تصمیمِ یکپارچه که همهٔ اندازه‌گیری‌های این پنج ترم را کنارِ هم می‌گذارد و **خانه‌های خالی‌اش را هم نشان می‌دهد.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s08-project-graph (یادستان, Yaadestan)
