📋 Table of Contents

English Version:

• Overview
• Algorithms
• Project Structure
• Installation
• Usage
• Input Format
• Output Format
• Algorithm Details

نسخه فارسی:

• معرفی
• الگوریتم‌ها
• ساختار پروژه
• نصب
• استفاده
• فرمت ورودی
• فرمت خروجی
• توضیحات الگوریتم

---

🌐 English Version

Overview

This project implements two approaches to the Graph Coloring Problem:

1. Sequential Algorithm: Traditional greedy coloring approach
2. Parallel Algorithm: Using NetworkX library with optimized strategy

The Graph Coloring Problem is a classic NP-complete problem where the goal is to assign colors to vertices of a graph such that no two adjacent vertices share the same color, using the minimum number of colors possible.

Algorithms

Sequential Coloring

• File: sequential.py
• Strategy: Greedy approach processing nodes in sorted order
• Time Complexity: O(V + E) where V is vertices and E is edges
• Approach: Colors each node with the smallest available color that doesn't conflict with neighbors

Parallel Coloring

• File: parallel.py
• Library: NetworkX (with greedy_color using "largest_first" strategy)
• Strategy: Processes nodes in order of degree (largest first)
• Advantage: Often produces better results in fewer colors

Project Structure

graph-coloring/
│
├── input.txt              # Sample input file with edges
├── output_sequential.txt   # Output from sequential algorithm
├── output_parallel.txt     # Output from parallel algorithm
├── sequential.py          # Sequential implementation
├── parallel.py            # Parallel implementation (using NetworkX)
└── README.md             # This file

Installation

Requirements

python >= 3.7
networkx >= 2.5

Setup

# Install required packages
pip install networkx

Usage

Run Sequential Algorithm

python sequential.py

Run Parallel Algorithm

python parallel.py

Both scripts read from input.txt and save results to their respective output files.

Input Format

The input file should contain edges, one per line, in the format:

node1-node2

Example (input.txt):

1-2
2-3
4-5
5-6
3-4
2-4
1-5

Output Format

The output files contain:

1. First line: Total number of colors used
2. Second line: Color assignment for each node (space-separated)

Example (output_sequential.txt):

Number of color 3
Node color 1 2 1 2 3 2

Algorithm Details

Sequential Algorithm Explanation

The sequential algorithm works as follows:

1. Initialization: Create an empty dictionary to store node colors

2. Helper Functions:

   • get_neighbors(node): Returns all neighbors of a given node
   • get_available_color(node): Finds the smallest color not used by any neighbor

3. Main Process:

   • Sort all nodes
   • For each node in order:
     • Get colors used by its neighbors
     • Assign the smallest available color (starting from 1)
   • Count total colors and return color assignments

4. Time Complexity Analysis:

   • Sorting nodes: O(V log V) where V = number of vertices
   • Main loop: O(V) iterations
   • For each node:
     • get_neighbors(): O(E) - scans all edges in worst case
     • get_available_color(): O(degree of node) - at most O(V)
   • Total: O(V × E) in worst case, O(V²) for dense graphs
   • Space Complexity: O(V) for storing colors dictionary

5. Why This Works:

   • By processing in sorted order, we ensure consistency
   • Greedy approach guarantees a valid coloring (not necessarily optimal)
   • Practical efficiency despite theoretical complexity due to sparse graphs

Parallel Algorithm Explanation

The parallel algorithm leverages NetworkX library:

1. Graph Construction: Build a NetworkX Graph from edges

   • Time: O(E) where E = number of edges

2. Coloring Strategy - "largest_first":

   • Processes nodes in descending order of their degree (number of connections)
   • Rationale: Nodes with more connections have fewer color options, so color them first
   • This strategy often uses fewer colors than random ordering

3. Color Assignment:

   • Returns a dictionary mapping each node to its color
   • Extract total color count and create ordered list

4. Time Complexity Analysis:

   • Graph construction: O(E)
   • Sorting by degree: O(V log V)
   • Coloring process: O(V + E) - visits each vertex and edge once
   • Total: O(V log V + E) - significantly better than sequential in most cases
   • Space Complexity: O(V + E) for graph storage

5. Why This Works:

   • More efficient for complex graphs
   • The "largest_first" heuristic generally produces better solutions
   • Leverages well-tested library code optimized for performance# Graph Coloring Project

---

🔵 نسخه فارسی

معرفی

این پروژه دو روش برای حل مسئله رنگ‌امیزی گراف را پیاده‌سازی می‌کند:

1. الگوریتم ترتیبی: روش سبز‌چین سنتی
2. الگوریتم موازی: استفاده از کتابخانه NetworkX

مسئله رنگ‌امیزی گراف یک مسئله کلاسیک NP-complete است که هدف آن تخصیص رنگ‌ها به رئوس گراف به‌گونه‌ای است که هیچ دو راس مجاور رنگ یکسانی نداشته باشند و از کمترین تعداد رنگ استفاده شود.

الگوریتم‌ها

رنگ‌امیزی ترتیبی

• فایل: sequential.py
• روش: رویکرد سبز‌چین با پردازش گره‌ها به ترتیب مرتب
• پیچیدگی زمانی: O(V + E) که V تعداد رئوس و E تعداد یال‌ها است
• نحوه کار: هر گره را با کوچک‌ترین رنگ موجود که با همسایگان تضاد ندارد رنگ می‌کند

رنگ‌امیزی موازی

• فایل: parallel.py
• کتابخانه: NetworkX (با greedy_color و استراتژی "largest_first")
• روش: پردازش گره‌ها بر اساس درجه (بزرگ‌ترین اول)
• مزیت: معمولاً از رنگ‌های کمتری استفاده می‌کند

ساختار پروژه

graph-coloring/
│
├── input.txt              # فایل نمونه حاوی یال‌ها
├── output_sequential.txt   # خروجی الگوریتم ترتیبی
├── output_parallel.txt     # خروجی الگوریتم موازی
├── sequential.py          # پیاده‌سازی ترتیبی
├── parallel.py            # پیاده‌سازی موازی (با NetworkX)
└── README.md             # این فایل

نصب

نیازمندی‌ها

python >= 3.7
networkx >= 2.5

راه‌اندازی

# نصب بسته‌های مورد نیاز
pip install networkx

استفاده

اجرای الگوریتم ترتیبی

python sequential.py

اجرای الگوریتم موازی

python parallel.py

هر دو اسکریپت از فایل input.txt می‌خوانند و نتایج را در فایل‌های خروجی مربوطه ذخیره می‌کنند.

فرمت ورودی

فایل ورودی باید حاوی یال‌ها باشد، هر یال در یک خط به‌صورت زیر:

node1-node2

مثال (input.txt):

1-2
2-3
4-5
5-6
3-4
2-4
1-5

فرمت خروجی

فایل‌های خروجی حاوی موارد زیر هستند:

1. خط اول: تعداد کل رنگ‌های استفاده‌شده
2. خط دوم: تخصیص رنگ برای هر گره (جدا‌شده با فاصله)

مثال (output_sequential.txt):

Number of color 3
Node color 1 2 1 2 3 2

توضیحات الگوریتم

توضیح الگوریتم ترتیبی

الگوریتم ترتیبی به‌صورت زیر کار می‌کند:

1. مقدار‌دهی اولیه: یک دیکشنری خالی برای ذخیره رنگ‌های گره‌ها ایجاد کنید

2. توابع کمکی:

   • get_neighbors(node): تمام همسایگان یک گره را برمی‌گرداند
   • get_available_color(node): کوچک‌ترین رنگی را پیدا می‌کند که توسط هیچ همسایه استفاده نشده‌است

3. فرایند اصلی:

   • تمام گره‌ها را مرتب کنید
   • برای هر گره به‌ترتیب:
     • رنگ‌های استفاده‌شده توسط همسایگان را بدست آورید
     • کوچک‌ترین رنگ موجود (شروع از 1) را تخصیص دهید
   • تعداد کل رنگ‌ها و تخصیص رنگ‌ها را برگردانید

4. تحلیل پیچیدگی زمانی:

   • مرتب‌سازی گره‌ها: O(V log V) که V = تعداد رئوس
   • حلقه اصلی: O(V) تکرار
   • برای هر گره:
     • get_neighbors(): O(E) - در بدترین حالت تمام یال‌ها را اسکن می‌کند
     • get_available_color(): O(درجه گره) - حداکثر O(V)
   • کل: O(V × E) در بدترین حالت، O(V²) برای گراف‌های متراکم
   • پیچیدگی فضایی: O(V) برای ذخیره دیکشنری رنگ‌ها

5. چرا این روش کار می‌کند:

   • با پردازش به‌ترتیب، ثبات را تضمین می‌کنیم
   • رویکرد سبز‌چین یک رنگ‌امیزی معتبر را تضمین می‌کند (نه‌لزوماً بهینه)
   • کارایی عملی علیرغم پیچیدگی تئوری‌ای به دلیل گراف‌های کم‌تراکم

توضیح الگوریتم موازی

الگوریتم موازی از کتابخانه NetworkX استفاده می‌کند:

1. ساخت گراف: یک گراف NetworkX از یال‌ها بسازید

   • زمان: O(E) که E = تعداد یال‌ها

2. استراتژی رنگ‌امیزی - "largest_first":

   • گره‌ها را به ترتیب نزولی درجه‌شان پردازش می‌کند (تعداد اتصالات)
   • منطق: گره‌های با اتصالات بیشتر گزینه‌های رنگی کمتری دارند، بنابراین ابتدا آن‌ها را رنگ کنید
   • این استراتژی معمولاً رنگ‌های کمتری نسبت به ترتیب تصادفی استفاده می‌کند

3. تخصیص رنگ:

   • یک دیکشنری برمی‌گرداند که هر گره را به رنگ‌اش نگاشت می‌کند
   • تعداد رنگ کل و یک لیست مرتب‌شده را استخراج کنید

4. تحلیل پیچیدگی زمانی:

   • ساخت گراف: O(E)
   • مرتب‌سازی بر اساس درجه: O(V log V)
   • فرایند رنگ‌امیزی: O(V + E) - هر راس و یال را یک‌بار بازدید می‌کند
   • کل: O(V log V + E) - بسیار بهتر از الگوریتم ترتیبی در اکثر موارد
   • پیچیدگی فضایی: O(V + E) برای ذخیره‌سازی گراف

5. چرا این روش کار می‌کند:

   • برای گراف‌های پیچیده کارایی بیشتر
   • الگوریتم ابتکاری "largest_first" معمولاً راه‌حل‌های بهتری تولید می‌کند
   • از کد کتابخانه آزمایش‌شده استفاده می‌کند که برای عملکرد بهینه شده‌است

---

📄 License

Open Source