SciPy Graphs

<< مبحث قبلی مبحث بعدی >>

کار کردن با گراف‌ها

گراف یک ساختار داده اساسی است.

SciPy مدول scipy.sparse.csgraph را جهت کار با گراف‌ها فراهم کرده است.

ماتریس مجاورت

ماتریس مجاورت (Adjacency Matrix) یک ماتریس n❌n است که n تعداد عناصر در گراف می‌باشد.

مقادیر این ماتریس نمایش دهنده نحوه اتصال میان عناصر است.

برای مثال شکل زیر را در نظر بگیرید.

برای چنین گرافی با عناصر B ،A و C ارتباط به این صورت است که:

  • A & B با وزن یک به هم متصل هستند.
  • A & C با وزن دو به هم متصل هستند.
  • B & C به هم متصل نیستند.

ماتریس مجاورت آن به صورت زیر خواهد بود.

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

تابع شیء ()connected_components

با استفاده از این تابع شیء همه مؤلفه‌های متصل به هم را می‌توانید پیدا کنید.


import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

خروجی:

تابع شیء ()dijkstra

از این تابع شیء جهت پیدا کردن کوتاه‌ترین مسیر از یک عنصر به عنصر دیگر استفاده می‌شود.

آرگومان‌های زیر را نیاز دارد:

  • return_predecessors - بولین (اگر می‌خواهید کل مسیر پیمایش را نشان دهد True در غیر اینصورت False)
  • indices - ایندکس عنصری که می‌خواهید همه مسیرها از آن عنصر برگردانده شوند.
  • limit - حداکثر وزن مسیر

در کد زیر کوتاه‌ترین مسیر از عنصر 1 به 2 را پیدا می‌کنیم.


import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

خروجی:

تابع ()floyd_warshall

کوتاه‌ترین مسیر بین هر دو جفت عنصر را پیدا می‌کند.


import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

خروجی:

تابع شیء ()bellman_ford

این تابع شیء هم کوتاه‌ترین مسیر بین هر دو جفت عنصر را پیدا می‌کند با این تفاوت که می‌تواند با وزن‌های منفی نیز کار کند.


import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

خروجی:

تابع شیء ()depth_first_order

پیمایش اولین عمق (depth first traversal) را از یک گره محاسبه می‌کند.

به آرگومان‌های زیر نیاز دارد:

  • گراف
  • عنصر آغازین جهت شروع پیمایش از آن

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

خروجی:

تابع شیء ()breadth_first_order

یا استفاده از این تابع شیء می‌توان مرتبه اولین پهنا را از یک گره محاسبه کرد.


import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))

خروجی:

<< مبحث قبلی مبحث بعدی >>