پیاده سازی ساده گراف در پایتون و چند الگوریتم

یکی از مهترین ابزارهای مدل سازی ریاضی که استفاده های متنوعی در علم روز پیدا کرده است گراف می باشد. اگر می خواهید نحوه پیاده سازی گراف در زبان برنامه نویسی پایتون و الگوریتم های مسیر یابی ساده مرتبط با آن را فرابگیرید، این نوشته به شما کمک خواهد کرد. در این نوشته بعد از ساخت گراف با استفاده از شی dictionary به پیاده سازی الگوریتم مسیریابی و کوتاه ترین مسیر پرداخته شده است.

بسم الله الرحمن الرحیم

هر گراف مجموعه ای از گره ها و یالها می باشد که یالها وظیفه اتصال گره ها به هم را بر عهده دارند. ارتباط بین گره ها توسط یالها در یک گراف می تواند تک جهته یا دو جهته باشد که در این نوشته حالت تک جهته مورد بحث قرار می گیرد. گراف نوع داده ای است که معمولا بطور پیشفرض توسط زبانهای برنامه نویسی مورد پشتیبانی قرار نمی گیرد. پایتون هم از این قضیه مستثنا نیست. برای ساخت گراف در پایتون می توان از چند روش استفاده کرد که تقریبا سرراست ترین آنها استفاده از dictionary است. در این نوشته نیز به آن پرداخته خواهد شد.

در مرحله اول فرض کنیم اتصال گرافها به شکل زیر تعریف شود:

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

همانطور که مشخص است گراف دارای شش گره و هشت یال می‌باشد. کد پایتون زیر گره ها و یالهای گراف را با استفاده از dictionary مدل می‌نماید:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

خب تا این قسمت ما توانستیم یک گراف را با امکانات عادی پایتون مدل کنیم. حال تابعی می نویسیم که مسیری بین دو گره از گراف را برای ما پیدا کند. به قطعه کد زیر توجه نمایید:

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

همانطور که خودتان هم از شمایل کد کتوجه شده اید این تابع با استفاده از تکنیک backtracking اقدام به پیدا کردن مسیری از گره شروع تا گره انتهایی می نماید. حال این کد را برای گرافی که ساخته ایم اجرا نماییم:

>>> find_path(graph, 'A', 'D')
['A', 'B', 'C', 'D']
>>>

مسیر رسیدن از گره A به گره B اینطور بدست می آید که مشاهده می نمایید. اما اگر بخواهیم تمام مسیرهای ممکن را از یک گره به گره دیگر بدست بیاوریم می توانیم از قطعه کد زیر استفاده نماییم:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

همانطور که می بینید تفاوت زیادی با تابع بالایی ندارد، تنها پروسه را برای تمامی حالات ادامه می دهد (بجای اینکه با پیدا کردن اولین مسیر از تابع خارج گردد) که در نتیجه آن تمام مسیرهای ممکن استخراج می گردند. خروجی تابع را برای حالت قبلی می توانید در زیر مشاهده نمایید:

>>> find_all_paths(graph, 'A', 'D')
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]
>>>

تابع زیر یک حالت دیگر از همین تابع که در دو کد قبلی دیدیم نشان می دهد که به منظور پیدا کردن کوتاه ترین مسیر ویرایش گردیده است. با پیدا کردن هر مسیر آن را با مسیر قبلی پیدا شده مقایسه می کند و درصورتی که کوتاه تر باشد آن را بجای قبلی نگه می دارد:

def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

که نتیجه اجرای آن بر روی گرافی که تعریف کرده ایم به شکل زیر خواهد بود:

>>> find_shortest_path(graph, 'A', 'D')
['A', 'C', 'D']
>>>

در نوشته های دیگر به بیان الگوریتم ها متداول و کارامدتر پیدا کردن کوتاه ترین مسیر پرداخته خواهد شد.

منتظر باشید …