topological_sorting.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e0decf14",
   "metadata": {},
   "outputs": [],
   "source": [
    "import tkinter as tk\n",
    "from tkinter import messagebox\n",
    "from tkinter import filedialog"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f8282708",
   "metadata": {},
   "outputs": [],
   "source": [
    "# store the task’s name, index, and prerequisite list\n",
    "class Task:\n",
    "    def __init__(self, name, index, prereq_numbers):\n",
    "        self.name = name\n",
    "        self.index = index\n",
    "        self.prereq_numbers = prereq_numbers\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.name\n",
    "    \n",
    "    def numbers_to_tasks(self, tasks):\n",
    "        self.prereq_tasks = []\n",
    "        for number in self.prereq_numbers:\n",
    "            self.prereq_tasks.append(tasks[number])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6b8876dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class PoSorter:\n",
    "    def __init__(self):\n",
    "        self.tasks = []\n",
    "        \n",
    "    def topo_sort(self):\n",
    "        for task in self.tasks:\n",
    "            task.followers = []\n",
    "\n",
    "        for task in self.tasks:\n",
    "            for prereq in task.prereq_tasks:\n",
    "                prereq.followers.append(task)\n",
    "            task.prereq_count = len(task.prereq_tasks)\n",
    "\n",
    "        # Move tasks with no prerequisites onto the ready list.\n",
    "        ready_tasks = []\n",
    "        for task in self.tasks:\n",
    "            if task.prereq_count == 0:\n",
    "                ready_tasks.append(task)\n",
    "\n",
    "        # sorted task list\n",
    "        self.sorted_tasks = []\n",
    "\n",
    "        while len(ready_tasks) > 0:\n",
    "            ready_task = ready_tasks.pop(0)\n",
    "            self.sorted_tasks.append(ready_task)\n",
    "\n",
    "            for follower in ready_task.followers:\n",
    "                follower.prereq_count -= 1\n",
    "                if follower.prereq_count == 0:\n",
    "                    ready_tasks.append(follower) # no prereqs, add it to the ready list\n",
    "        \n",
    "    def verify_sort(self):\n",
    "        #verify the sort is valid\n",
    "        for i in range(len(self.sorted_tasks)):\n",
    "            task = self.sorted_tasks[i]\n",
    "            for prereq in task.prereq_tasks:\n",
    "                if self.sorted_tasks.index(prereq) >= i:\n",
    "                    return f'Task [{prereq}] does not come before [{task}]'\n",
    "        return f'Successfully sorted {len(self.sorted_tasks)} out of {len(self.tasks)} tasks.'\n",
    "    \n",
    "    def read_task(self, file):\n",
    "        # read a task from the file\n",
    "        # return a task or none if we reach the end of the file\n",
    "        result = ''\n",
    "        while len(result) == 0:\n",
    "            line = file.readline()\n",
    "            if len(line) == 0:\n",
    "                return None\n",
    "            line = line.strip()\n",
    "            \n",
    "            if len(line) > 0:\n",
    "                fields = line.split(',', 2)\n",
    "                index = int(fields[0])\n",
    "                name = fields[1].strip()\n",
    "                prereq_text = fields[2].replace('[', '').replace(']', '').strip()\n",
    "                if len(prereq_text) == 0:\n",
    "                    prereq_numbers = []\n",
    "                else:\n",
    "                    prereq_numbers = list(map(int, prereq_text.split(',')))\n",
    "                return Task(name, index, prereq_numbers)\n",
    "    \n",
    "    def load_po_file(self, filename):\n",
    "        self.tasks = []\n",
    "        file = open(filename, 'r')\n",
    "        try:\n",
    "            while True:\n",
    "                new_task = self.read_task(file)\n",
    "                if new_task == None:\n",
    "                    break\n",
    "                self.tasks.append(new_task)\n",
    "        \n",
    "        except Exception as e:\n",
    "            messagebox.showinfo('Load Error', f'Error loading file {filename}.\\n{e}')\n",
    "        \n",
    "        finally:\n",
    "            file.close()\n",
    "            \n",
    "        for task in self.tasks:\n",
    "            task.numbers_to_tasks(self.tasks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4a80c5cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "class App:\n",
    "    def __init__(self):\n",
    "        self.sorter = PoSorter()\n",
    "\n",
    "        # Make the main interface.\n",
    "        self.window = tk.Tk()\n",
    "        self.window.title('topological_sorting')\n",
    "        self.window.protocol('WM_DELETE_WINDOW', self.kill_callback)\n",
    "        self.window.geometry('400x300')\n",
    "\n",
    "        # Build the menu.\n",
    "        self.menubar = tk.Menu(self.window)\n",
    "        self.menu_file = tk.Menu(self.menubar, tearoff=False)\n",
    "        self.menu_file.add_command(label='Open...', command=self.open_po, accelerator='Ctrl+O')\n",
    "        self.menu_file.add_separator()\n",
    "        self.menu_file.add_command(label='Exit', command=self.kill_callback)\n",
    "        self.menubar.add_cascade(label='File', menu=self.menu_file)\n",
    "        self.window.config(menu=self.menubar)\n",
    "\n",
    "        # Build the item lists.\n",
    "        frame = tk.Frame(self.window)\n",
    "        frame.pack(padx=10, pady=(0, 10), side=tk.BOTTOM, fill=tk.BOTH, expand=True)\n",
    "        frame.columnconfigure(1, weight=1)\n",
    "        frame.columnconfigure(3, weight=1)\n",
    "        frame.rowconfigure(1, weight=1)\n",
    "\n",
    "        # Unsorted list.\n",
    "        inner_frame = tk.Frame(frame)\n",
    "        inner_frame.grid(row=1, column=1, padx=3, pady=3, sticky='nsew')\n",
    "        inner_frame.columnconfigure(1, weight=1)\n",
    "        inner_frame.rowconfigure(1, weight=1)\n",
    "        self.unordered_list = tk.Listbox(inner_frame)\n",
    "        self.unordered_list.grid(row=1, column=1, sticky='nsew')\n",
    "        scrollbar = tk.Scrollbar(inner_frame)\n",
    "        scrollbar.grid(row=1, column=2, sticky='nse')\n",
    "        self.unordered_list.config(yscrollcommand = scrollbar.set)\n",
    "        scrollbar.config(command = self.unordered_list.yview)\n",
    "\n",
    "        # Sort button.\n",
    "        sort_button = tk.Button(frame, text='Sort', width=6, command=self.sort)\n",
    "        sort_button.grid(row=1, column=2, padx=3)\n",
    "\n",
    "        # Sorted list.\n",
    "        inner_frame = tk.Frame(frame)\n",
    "        inner_frame.grid(row=1, column=3, padx=3, pady=3, sticky='nsew')\n",
    "        inner_frame.columnconfigure(1, weight=1)\n",
    "        inner_frame.rowconfigure(1, weight=1)\n",
    "        self.ordered_list = tk.Listbox(inner_frame)\n",
    "        self.ordered_list.grid(row=1, column=1, sticky='nsew')\n",
    "        scrollbar = tk.Scrollbar(inner_frame)\n",
    "        scrollbar.grid(row=1, column=2, sticky='nse')\n",
    "        self.ordered_list.config(yscrollcommand = scrollbar.set)\n",
    "        scrollbar.config(command = self.ordered_list.yview)\n",
    "\n",
    "        self.window.bind('<Control-o>', self.ctrl_o_pressed)\n",
    "\n",
    "        # Display the window.\n",
    "        self.window.focus_force()\n",
    "        self.window.mainloop()\n",
    "\n",
    "    def kill_callback(self):\n",
    "        self.window.destroy()\n",
    "\n",
    "    def ctrl_o_pressed(self, event):\n",
    "        self.open_po()\n",
    "        \n",
    "    def open_po(self):\n",
    "        file_types = [('Partial Ordering', '*.po')]\n",
    "        filename = filedialog.askopenfilename(\n",
    "            defaultextension='.po', filetypes=file_types,\n",
    "            initialdir='.', title='Open Partial Ordering')\n",
    "        if not filename: return\n",
    "\n",
    "        self.unordered_list.delete(0,'end')\n",
    "        self.ordered_list.delete(0,'end')\n",
    "        self.sorter.load_po_file(filename)\n",
    "        self.unordered_list.insert('end', *self.sorter.tasks)\n",
    "\n",
    "    def sort(self):\n",
    "        self.sorter.topo_sort()\n",
    "        self.ordered_list.insert('end', *self.sorter.sorted_tasks)\n",
    "        messagebox.showinfo('Sort Result',\n",
    "            self.sorter.verify_sort())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e1327531",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.App at 0x21fa240fcd0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "App()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df2ced62",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "scheduling-tool",
   "language": "python",
   "name": "scheduling-tool"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}