This project implements a distributed computing algorithm for rank-based graph coloring using the MPI (Message Passing Interface) library. The algorithm is designed to color nodes in a distributed graph while efficiently communicating with neighboring nodes.
- rank_based_coloring.py: The main Python script implementing the rank-based coloring algorithm using MPI.
- Ensure you have MPI installed on your system.
- Execute the script using the following command:
mpiexec -n <num_processes> python rank_based_coloring.py
Each round is initiated by the root node, and the node with the highest local degree colors itself
This algorithm assumes that the root node is the lowest ranked node, thus terminates when the root node is colored.
The input graph is represented as an adjacency matrix (G), and the tree structure is defined by parent-child relationships to construct a MST.
The script outputs the termination details, including the rank of the node and its assigned color, to an "output.log" file.
The script utilizes a custom logging module (MPILogFile) to log output details.
This script is configured for a specific input graph and tree structure. Modify the G, children, and parents arrays according to your specific use case.