گراف در پایتون یکی از مهم‌ترین ساختارهای داده «Data structures» در علوم کامپیوتر «Computer Science» هستند که برای نمایش روابط بین اشیا «Objects» به کار می‌روند. گراف ددر پایتون، با استفاده از دیکشنری‌ها «Dictionary»، لیست‌های مجاورت «Proximity lists» یا ماتریس‌های مجاورت «Adjacency matrices» پیاده‌سازی می‌شوند. همچنین، کتابخانه‌هایی مانند NetworkX و igraph ابزارهای قدرتمندی برای ایجاد، تحلیل و تجسم گراف‌ها ارائه می‌دهند. این کتابخانه‌ها امکان اجرای الگوریتم‌هایی مانند کوتاه‌ترین مسیر، پیمایش گراف و شناسایی اجزای همبند را فراهم می‌کنند.
مقدمه
استفاده از گراف در پایتون در زمینه‌های مختلفی مانند تحلیل شبکه‌های اجتماعی، مسیریابی در سیستم‌های حمل‌ونقل، مدل‌سازی روابط بیولوژیکی «Biological relationships» و بهینه‌سازی داده‌ها «Data optimization» کاربرد دارد. به کمک پایتون، می‌توان به‌راحتی گراف‌ها را ایجاد کرده و الگوریتم‌های مختلف را برای استخراج اطلاعات مفید از آن‌ها پیاده‌سازی کرد. بهینه‌سازی گراف و کار با داده‌های حجیم نیز از ویژگی‌های مهمی است که پایتون به کمک کتابخانه‌های خود به آن پرداخته است. در این مقاله از سری مقاله های مجله پی استور به تعریف و روش‌های پیاده‌سازی گراف در پایتونب ه زبان ساده پرداختیم.
گراف در پایتون چیست؟
گراف در پایتون از ساختارهای داده‌ای اساسی در علوم کامپیوتر هستند که برای نمایش و مدل‌سازی روابط پیچیده بین موجودیت‌ها به کار می‌روند. کاربردهای آن‌ها دامنه گستردهای از جمله تحلیل شبکه‌های اجتماعی، سیستم‌های حمل‌ونقل و بیوانفورماتیک «Bioinformatics» را در بر می‌گیرد. همچنین، پایتون به‌عنوان زبانی قدرتمند و پرکاربرد، روش‌های متعددی را برای پیاده‌سازی و مدیریت گراف‌ها «Graph management» ارائه می‌دهد.
انواع گراف در پایتون
گراف در پایتون را می‌توان به روش‌های مختلفی بر اساس ویژگی‌هایشان دسته‌بندی و پیاده‌سازی کرد. برخی از انواع رایج گراف در پایتون عبارت‌اند از:
- گراف بدون جهت «Undirected Graph»: در این گراف، یال‌ها بدون جهت هستند و ارتباط بین راس‌ها دوطرفه است.
- گراف جهت‌دار «Directed Graph یا Digraph»: در این نوع گراف، یال‌ها دارای جهت مشخصی هستند و ارتباط بین گره‌ها یک‌طرفه است.
- گراف وزن‌دار «Weighted Graph»: یال‌های این گراف دارای وزن هستند که می‌تواند نشان‌دهنده هزینه، فاصله یا شدت ارتباط باشد.
- گراف همبند «Connected Graph»: در این گراف، بین هر دو راس حداقل یک مسیر وجود دارد.
- گراف ناهمبند «Disconnected Graph»: شامل چندین مؤلفه جدا از هم است که هیچ مسیری بین برخی از راس‌ها وجود ندارد.
- گراف دو بخشی «Bipartite Graph»: مجموعه راس‌ها به دو گروه تقسیم می‌شوند به‌طوری‌که یال‌ها فقط بین این دو گروه وجود دارند.
- درخت «Tree»: یک نوع خاص از گراف بدون جهت است که هیچ دوری ندارد و بین هر دو راس تنها یک مسیر وجود دارد.
برای پیاده‌سازی گراف در پایتون می‌توان از روش‌های مختلفی مانند لیست مجاورت «Adjacency List»، ماتریس مجاورت «Adjacency Matrix» یا کتابخانه‌های پیشرفته‌ای مانند NetworkX و igraph استفاده کرد.
پیاده سازی گراف در پایتون
برای پیاده‌سازی گراف در پایتون بدون کدنویسی، می‌توان گراف را به شکل‌های مختلفی در ذهن یا بر روی کاغذ مدل‌سازی کرد. در ادامه توضیحی از نحوه‌ی مدل‌سازی گراف در پایتون آمده است:
ماتریس های مجاورت در پایتون
ماتریس مجاورت یکی از روش‌های رایج برای نمایندگی گراف‌ها است که از یک ماتریس دوبعدی برای نمایش ارتباطات بین راس‌ها استفاده می‌کند. در این ماتریس، هر سطر و ستون نمایانگر یک راس از گراف است و در صورتی که بین دو راس یالی وجود داشته باشد، در آن خانه از ماتریس مقدار ۱ (یا وزن یال در گراف‌های وزن‌دار) قرار می‌گیرد، در غیر این صورت مقدار ۰ قرار می‌گیرد.
در اینجا کد مربوط به ایجاد ماتریس مجاورت نمایش داده شده است. در این مثال، عناصر داخل ماتریس به صورت فرضی مقداردهی شده‌اند:
# Create a graph with 4 vertices and 5 edges
graph = [[0, 1, 1, 0],
[۱, ۰, ۱, ۱],
[۱, ۱, ۰, ۱],
[۰, ۱, ۱, ۰]]
# Print the graph
for row in graph:
print(row)
خروجی:
[۰, ۱, ۱, ۰] [۱, ۰, ۱, ۱] [۱, ۱, ۰, ۱] [۰, ۱, ۱, ۰]
لیست مجاورت در پایتون
لیست مجاورت یکی از روش‌های معمول برای نمایش گراف‌ها است که در آن برای هر راس یک لیست از رأس‌های مجاورش ذخیره می‌شود. این روش به خصوص برای گراف‌های کم‌پیوند (گراف‌هایی با تعداد کمی یال نسبت به راس‌ها) بسیار مناسب است. در پایتون، می‌توان از دیکشنری‌ها یا لیست‌ها برای پیاده‌سازی لیست مجاورت استفاده کرد.
# Create a graph with 4 vertices and 5 edges
graph = {0: [1, 2],
۱: [۰, ۲, ۳],
۲: [۰, ۱, ۳],
۳: [۱, ۲]}
# Print the graph
for vertex in graph:
print(vertex, ":", graph[vertex])
خروجی:
۰ : [۱, ۲] ۱ : [۰, ۲, ۳] ۲ : [۰, ۱, ۳] ۳ : [۱, ۲]
نمایش شی گرایانه در پایتون
نمایش شی‌گرایانه گراف در پایتون به معنای استفاده از مفاهیم شی‌گرایی برای مدل‌سازی گراف‌ها است. در این رویکرد، گراف به صورت یک شی با ویژگی‌ها و متدهای مربوط به خود پیاده‌سازی می‌شود. این روش به ما این امکان را می‌دهد که رفتار و ویژگی‌های مختلف گراف را به صورت جداگانه و قابل استفاده مجدد در برنامه‌های مختلف تعریف کنیم.
class Vertex:
def __init__(self, vertex_id):
self.id = vertex_id
self.neighbors = []
def add_neighbor(self, neighbor):
if neighbor not in self.neighbors:
self.neighbors.append(neighbor)
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, vertex):
if isinstance(vertex, Vertex) and vertex.id not in self.vertices:
self.vertices[vertex.id] = vertex
return True
else:
return False
def add_edge(self, v1, v2):
if v1 in self.vertices and v2 in self.vertices:
self.vertices[v1].add_neighbor(v2)
self.vertices[v2].add_neighbor(v1)
return True
else:
return False
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
# Create a graph with 4 vertices and 5 edges
graph = Graph()
for i in range(4):
graph.add_vertex(Vertex(i))
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
استفاده از دیکشنری برای نمایش راس و یال در پایتون
استفاده از دیکشنری برای نمایش راس‌ها و یال‌های گراف در پایتون یک روش ساده و موثر است. در این روش، گراف به‌عنوان یک دیکشنری از دیکشنری‌ها یا لیست‌ها پیاده‌سازی می‌شود. در این ساختار، کلیدهای دیکشنری نمایانگر راس‌های گراف و مقادیر آن‌ها نمایانگر یال‌ها و راس‌های مجاور هستند.
برای نمایش گراف با استفاده از دیکشنری، از یک گراف ساده و بدون جهت با چهار راس و چهار یال استفاده می‌کنیم. در این مثال، قصد داریم نشان دهیم که دیکشنری‌ها چگونه می‌توانند یال‌ها و راس‌های گراف را به‌طور مؤثر نمایش دهند.
۰
/ \
۱---۲
\ /
۳
گراف بالا را با استفاده از هر دو دیکشنری یال‌ها و راس‌ها نمایش می‌دهیم.
vertices = {
۰: [۱, ۲],
۱: [۰, ۲, ۳],
۲: [۰, ۱, ۳],
۳: [۱, ۲]
}
edges = {
۰: {۱, ۲},
۱: {۰, ۲, ۳},
۲: {۰, ۱, ۳},
۳: {۱, ۲}
}
پیاده سازی گراف در پایتون با استفاده از کتابخانه NetworkX
کتابخانه NetworkX یکی از قدرتمندترین ابزارها برای پیاده‌سازی، تجزیه و تحلیل گراف‌ها در پایتون است. این کتابخانه قابلیت‌های گستردهای برای کار با گراف‌های جهت‌دار و بدون جهت، گراف‌های وزن‌دار، گراف‌های چندگانه و انواع مختلف دیگر گراف‌ها فراهم می‌کند. استفاده از NetworkX بسیار ساده است و به شما این امکان را می‌دهد که گراف‌ها را به راحتی ایجاد، مدیریت و تحلیل کنید.
گراف کامل در پایتون چیست؟
گراف کامل «Complete Graph» گرافی است که در آن هر راس به‌طور مستقیم به تمام راس‌های دیگر متصل است. در واقع، در گراف کامل، هر دو راس به‌هم متصل هستند و هیچ‌یک از راس‌ها از ارتباط با دیگر راس‌ها محروم نیستند.
- در گراف کامل، درجه هر راس برابر با \(n-1\) است.
- تعداد کل یال‌ها در این گراف به صورت n(n-1)/2 محاسبه می‌شود.
- تمامی یال‌های ممکن که در یک گراف ساده وجود دارند، در گراف کامل نیز وجود دارند.
- این نوع گراف به‌عنوان گراف‌های چرخشی یا دوری «Cyclic Graph» شناخته می‌شود.
- در گراف کامل، کمترین فاصله بین هر دو راس برابر با ۱ است.
- از آنجا که هر راس در این گراف به تمام رئوس دیگر متصل است، عدد فامی «Chromatic Number» برابر با \(n\) خواهد بود.
- همچنین، مکمل گراف کامل یک گراف خالی است.
سینتکس رسم گراف در پایتون
برای رسم گراف در پایتون، با استفاده از NetworkX می‌توان گراف را ایجاد کرده و با استفاده از تابع ()nx.draw آن را رسم کرد. سپس با استفاده از ()plt.showگراف رسم شده را نمایش می‌دهیم.
networkx.complete_graph(n)
در سینتکس بالا، تنها پارامتر استفاده شده n است. پارامتر n تعداد گره‌های گراف را مشخص می‌کند. این گراف در خروجی یک شی گراف کامل با n گره را برمی‌گرداند. تمام گره‌ها در گراف از شماره ۰ تا n-1 شماره‌گذاری شده‌اند. برای نمایش گراف به‌منظور مشاهده توسط کاربر، باید شی ایجاد شده را به تابع ()networkx.draw ارسال کرد. سینتکس پایه این تابع را در کادر زیر مشاهده می‌کنید.
networkx.draw(G, node_size, node_color)
در بالا مشاهده می‌شود که این تابع سه پارامتر جداگانه می‌پذیرد. توضیحات هرکدام از این پارامترها در فهرست زیر آمده است:
- G: این پارامتر به شی گراف کامل ایجاد شده اشاره دارد.
- node_size: این پارامتر اندازه گره‌ها را مشخص می‌کند.
- node_color: این پارامتر رنگ گره‌ها را تعیین می‌کند که باید با آن رسم شوند.
کاربرد گراف در پایتون
گراف در پایتون کاربردهای گستردهای دارند و می‌توانند برای حل مسائل مختلف در حوزه‌های مختلف استفاده شوند. برخی از کاربردهای گراف در پایتون عبارتند از:
- شبکه‌های اجتماعی: گراف‌ها برای مدل‌سازی روابط بین کاربران در شبکه‌های اجتماعی مانند فیسبوک یا توییتر استفاده می‌شوند. در اینجا راس‌ها نمایانگر کاربران و یال‌ها نمایانگر ارتباطات بین آن‌ها هستند.
- مسائل کوتاه‌ترین مسیر: الگوریتم‌هایی مانند دیکسترا «Dykstra» و فلوید-وارشال «Floyd-Warshall» برای یافتن کوتاه‌ترین مسیر بین راس‌های در گراف‌های وزن‌دار استفاده می‌شوند. این الگوریتم‌ها در مسیریابی شبکه‌ها و برنامه‌ریزی مسیرها کاربرد دارند.
- سیستم‌های حمل‌ونقل: گراف‌ها برای مدل‌سازی شبکه‌های حمل‌ونقل مانند سیستم‌های مترو، اتوبوس‌رانی و مسیرهای هوایی استفاده می‌شوند. رئوس نمایانگر ایستگاه‌ها و یال‌ها نمایانگر مسیرها هستند.
- تحلیل شبکه‌های ارتباطی: در تحلیل شبکه‌های ارتباطی مانند اینترنت، گراف‌ها برای مدل‌سازی اتصال‌ها بین سرورها و تجهیزات مختلف استفاده می‌شوند.
- پازل‌ها و مسائل ترکیبیاتی: بسیاری از مسائل ترکیبیاتی مانند رنگ‌آمیزی گراف‌ها، تعیین مولفه‌های هم‌توصیف و مسائل جریان شبکه به کمک گراف‌ها حل می‌شوند.
- مدل‌سازی روابط پیچیده: گراف‌ها برای نمایش و تحلیل روابط پیچیده بین موجودیت‌ها در علوم مختلف از جمله بیوانفورماتیک و زیست‌شناسی استفاده می‌شوند.
- مدیریت داده‌ها: گراف‌ها در پایگاه‌های داده گرافی مانند Neo4j برای مدل‌سازی روابط پیچیده و داده‌های غیرساختاریافته به‌کار می‌روند.
این کاربردها نشان‌دهنده توانایی گراف‌ها در حل مسائل مختلف در دنیای واقعی هستند و استفاده از پایتون برای پیاده‌سازی این مسائل بسیار متداول است.
نتیجه گیری
گراف در پایتون ابزار قدرتمندی برای مدل‌سازی و تحلیل روابط پیچیده بین داده‌ها هستند. با استفاده از کتابخانه‌هایی مانند NetworkX و امکانات مختلف پایتون، می‌توان گراف‌ها را به‌راحتی ایجاد، مدیریت و تحلیل کرد. کاربردهای گراف در پایتون در زمینه‌های مختلفی از جمله شبکه‌های اجتماعی، مسیریابی، تحلیل داده‌ها و علوم مختلف گسترده است. این انعطاف‌پذیری و قدرت در ترکیب با سادگی استفاده از پایتون، گراف‌ها را به ابزاری حیاتی برای حل مسائل پیچیده و کاربردی در دنیای مدرن تبدیل کرده است.
