Над проєктом працювали: Юрій Фітьо, Катерина Сучок, Дарина Ничипорук, Юліан-Володимир Заєць, Оксана Москв'як.
Дана бібліотека опрацьовує отримані на вхід графи з файлів з розширенням .dot, які
мають більше ніж 1 вершину, застосовує до них Гамільтоновий цикл, цикл Ейлера,
перевіряє на двочастковість, перевіряє на ізоморфність
та розфарбовує зв'язний граф у 3 кольори.
Детальніше кожну із функцій розглянуто нижче:
Функція приймає на ввід назву файлу для зчитування. Файл з розширенням .dot, у якому записаний орієнтований чи неорієнтований граф, чиї вершини можуть бути описаними як числами, так і словами. Декілька зв'язків можуть бути записані в один рядок, при чому для орієнтованого вершини зв'язок описується, як "->", а для неорієнтованого "--". Граф описується списком кортежів, якщо граф був неорієнтованим, то цей список перетворюється на список множин. Кожна знайдена вершина записується як множина, що перетворюється на список, щоб уникнути повторів, а далі списки кортежів чи множин змінюються так, щоб змінити назву вершини на її порядковий номер у попередньому списку. Таким чином можна називати вершини словами, а працювати з числами, що полегшить роботу наступних функцій. Для того щоб не втрачати інформацію про назви вершин, у функцію передається необов'язковий булівський елемент extra_list, якщо обрати його значення True, то функція повертатиме список, у яком перший елемент - шуканий список кортежів/масивів, а другий - список вершин, за яким можна відновити назви. Ми не вважаємо одну вершину повноцінним графом.
Ця функція не перевіряє чи цей граф є зв'язним, вона зразу намагається знайти цикл ейлера. Якщо він присутній значить граф зв'язний.
Спершу йде перевірка на те, чи граф порожній чи ні. Тут же визначається кількість ребер графа.
Далі йде перевірка чи граф неорієнтований(тобто чи містить він множини). Якщо він такий, то його перетворюються на орієнтований, замінююми кожне ребро неорієнтованого графа двома ребрами, що мають напрямок.
В основі цієї функції лежить принцип повного перебору, в якому для кожного шляху перевіряється чи є він циклом ейлера.
У функцію передається поточне місцезнаходження та шлях, який вона пройшла щоб дібратись до цієї точки. Далі функція розглядає варіанти по яких ребрах вона може далі піти. Коли вона пройшлась раз по ребру, то це ребро, видаляється з можливих подальших напрямків для цього шляху(якщо початковий граф був неорієнтованим, то ще видаляється дзеркальна копія цього ребра). Так вона генерує до моменту коли не буде куди далі рухатись. Коли шлях попадає у вершину, звідки й виходив, то відбувається перевірка чи довжина цього шляху така сама, як кількість ребер в початковому графі(тобто перевіряється чи містить він всі ребра). Якщо він містить всі ребра, то цей шлях записується до загального списку всіх можливих циклів ейлера.
Тож ця функція перебирає всі можливі шляхи і перевіряє чи є вони циклом Ейлера.
Далі перебирається список всіх можливих циклів Ейлера і відсіюються всі зайві цикли, що або повторються, або якщо вже існує їхня дзеркальна копія(оскільки це той самий цикл, просто в протилежному напрямку обходу). І вже цей оброблений список повертається функцією.
Ця програма перевіряє, чи має граф Гамільтоновий цикл, і відображає результати у вікні Tkinter, дозволяючи вводити графи у вигляді множин або кортежів, також і працює в терміналі, виводячи правильний шлях для гамільтонового циклу, або що його не існує.
permute(nodes) Генерує всі перестановки списку вершин.
check_for_ham(graph) Перевіряє наявністі гамільтонового циклу в графі, працює як і нан орієнтований так і на не орієнтований граф.
parse_input(text) Перетворює рядок вводу стрінга на пайтон список або кортеж.
display_results(permutations, correct_path, indx=0) Виводить результати перевірки у прокручуваний текст бокс в ткінтері
on_enter(event) Обробляє натискання клавіші Enter для запуску перевірки циклу
в ткінтерному форматі
tkinter_window() Головну функція Ткінтера, викликаючи її запустить візуалізацію ткінтера
На початку програми користувач вносить всі вершини як список. Програма це записує у словник для збереження з'єднань між ними. Потім програма генерує всі можливі перестановки множини вершин графа. Потім, для кожної перестановки перевіряє,чи відповідає вона збереженим з'єднанням у словнику. Якщо хоча б одна перестановка проходить перевірку, це означає, що знайдена правильна послідовність вершин для Гамільтонового циклу, який проходить через усі вершини графа і повертається до початкової. Якщо жодна перестановка не підходить, повертається повідомлення, яке свідчить про це.
Приклад візуалізації пошуку Гамільтонового циклу
Відношення може бути заданим як у вигляді списку кортежів, так і у вигляді списку множин, тому для початку функція зводить все до першого варіанту. Якщо ж відношення задане у вигляді списку кортежів, легко створити заповнену нулями матрицю розміром максимального знайденого елементу у кортежі списку, а потім присвоїти кожному елементу матриці значення 1(True) або 0(False) виразу, що перевіряє, чи існує кортеж з такими координатами в початковому списку. Матриця - список списків.
Кожному елементу матриці присвоюється результат побітового або його із симетричним елементом.
На вхід отримуються номер вершини, матриця, список кольорів усіх вершин (за кольори сприймаються натуральні числа) та пропонований колір вершини (номер). Якщо жодна із сусідніх вершин не має цього кольору, то повертається 1 інакше 0. Сусідніми вершинами вважаються ті, що у матриці мають одинички у одному рядку чи стовпцю із опитуваною вершиною.
Функція спрацьовуватиме при кожному підборі кольору. Вона перезаписує вихідний файл із частотою в 0.89 с., використовуючи бібліотеку time, щоб зміни були помітні. Перезапис полягає в додаванні нового рядка, який міститиме нову інформацію про колір певної вершини. вихідний файл завчасно сформований і містить усю ту інформацію, що була у вхідному файлі.Для цього на вхід передаються такі параметри: назва вихідного файлу в номер вершини, що записуватиметься, номер її кольору, список кольорів та вершин, щоб можна було відновити інформацію про колір та вершину.
На вхід функція отримує матрицю, її розмір, чисельний список присвоєних кольорів вершинам, список назв кольорів, номер вершини, що буде зафарбовуватися, параметр, що відповідає за те, чи потрібна візуалізація та список назв вершин. Ця функція рекурсивна і закінчуватиметься, коли ми дійдемо до останньої вершини, тому на початку відбувається перевірка на те, чи поточна вершина остання, якщо це правда по повертається True. Колір вершини визначаємо підбором, використовуючи для цього цикл. Всередині викликається approp, якщо колір підходить, він записується у чисельний список. Далі ми викликаємо нашу функцію і перевіряємо чи вона повертає значення True. По суті, в цьому моменті реалізовується рекурсія, яка закінчиться, коли ми дійдемо до останнього елементу. Коли це станеться, функція поверне заповнений чисельний список. Якщо ж у якісь вершині цикл дійде до кінця і не зможе підібрати жодного кольору, то функція поверне False. Також при кожній ітерації, якщо візуалізація потрібна, викликається функція visualizing.
Функція get_colour_seq об'єднує усі роботу усіх попередніх функцій та повертає стрічку з набором кольорів, або стрічку з повідомленням про неможливість розмальовування.
На вхід функція отримує назву файлу з графом із розширенням .dot, список кольорів, що ми можемо використовувати для розмальовування, параметр, що відповідає за необхідність візуалізації та назву вихідного файлу. Всередині функція створює симетричну матрицю, знаходить її розмір, формує заповнений нулями чисельний список для розмальовування розміром в кількість вершин, викликає функцію colouring та перевіряє чи вона не повертає нуль, тобто чи можна розмалювати граф таким чином. Якщо не можна, то у результат записується повідомлення: "The colouring is impossible.", інакше результат виклику функції зберігається та формується стрічка із списком кольорів через пробіл, яку функція повертатиме.
На вхід отримуються назви вхідного та вихідного файлу, список назв кольорів та параметр, що передається за замовчуванням, що відповідає за візуалізацію. Якщо останній параметр передається, як True, то завчасно створюється вихідний файл, як копія вхідного. Спочатку зберігається результат виклику функції get_color_seq. Якщо ми отримали повідомлення про неможливість розмалювання, воно виводиться на екран, інакше відкриваються файли для читання та запису. Із вхідного у вихідний переписується все окрім останнього рядку, в якому записаний знак "}". Далі знаходиться їхня кількість і прописується опис кожної вершини, де вказується колір, який береться по порядку із отриманої стрічки.
Приклад візуалізації розфарбування зв'язного графа
Основною ідеєю реалізації даної функції є використання алгоритму пошуку в ширину (BFS) та розфарбовування вершин графа у два кольори (тобто реалізація розділення вершин графа на 2 множини, у яких не повторюються вершини - основна умова двочастковості графа).
Допоміжна функція convert_to_directed перетворює граф з неорієнтованого в орієнтований для подальшої роботи.
Допоміжна функція get_neighbouring_values знаходить для кожної вершини суміжні та повертає словник, де ключ це вершина, а значення - множина суміжних вершин.
На початку функція створює “чергу” not_visited_vertices для зафарбовування вершин із цієї черги та словник, який зберігає колір вершин. Імплементовано цикл while, який працює поки черга не буде пустою. Для подальшої перевірки дістаємо першу вершину з черги, для якої відбувається перевірка чи не є ця вершина в відвіданих, далі відбувається перевірка суміжних до початкової вершин. Якщо поточна вершина та суміжна їй вершини однакового кольору - то цей граф не двочастковий, функція повертає значення - False
Якщо всі вершини було зафарбовано без збігів, то граф двочастковий. Функція повертає значення - True
Допоміжні функції if_graph_is_directed і if_graph_is_undirected перевіряють чи графи є орієнтованими, чи є неорієнтованими.
Допоміжна функція directed_isomorphism перевіряє ізоморфність двох орієнтованих графів.
Алгоритм базується на порівнянні структур графів шляхом перебору всіх можливих перестановок вершин.
Спершу визначають списки вершин обох графів. Якщо кількість вершин у графах відрізняється, вони не можуть бути ізоморфними. Далі для кожної перестановки вершин перевіряється, чи відповідає структура одного графа структурі іншого, шляхом порівняння матриць суміжності або списків суміжності, враховуючи напрямки ребер.
Алгоритм завершується та повертає True, якщо знайдена відповідність, або повертає False після перевірки всіх можливих перестановок.
Допоміжна функція undirected_isomorphism перевіряє ізоморфність двох неорієнтованих графів.
Алгоритм порівнює кількість ребер у графах, конвертує ребра в впорядковані кортежі для зручності порівняння, збирає множини вершин для кожного графа і перевіряє, чи збігаються ці множини. Якщо множини вершин однакові, то графи можуть бути ізоморфними, і алгоритм повертає True; інакше — False.
- Склонуйте цей репозиторій
git clone https://github.com/okqsna/computer-project.git
- Перевірте чи встановлений у вас
Python 3.12та такі модулі:tkinter,ast,argparse. - Для інтерактивного виводу з
argparseвведіть у термінал такі команди, де:
- example.dot / example_1.dot / --add-file example_2.dot - приклади файлів, у яких містяться графи
- --file-out example_out.dot - файл, у який записується результат після виклику функції
write_colour - --colors red,yellow,blue - кольори, у які повинен зафарбуватись зв'язний граф
- --visualization-for-coloring - параметр, який може набувати значення True або False, необхідний для функції
write_colour
python3 result.py example.dot euler-cycle
python3 result.py example.dot hamiltonian-cycle
python3 result.py example.dot hamiltonian-visualization
python3 result.py example.dot coloring-graphs --file-out example_out.dot --colors red,yellow,blue --visualization-for-coloring True # False для запису без візуалізації
python3 result.py example.dot bipartite-graph
python3 result.py example_1.dot isomorphic-graphs --add-file example_2.dot
Під час роботи над цим комп'ютерним проєктом ми розприділили функції по одній для кожного, проте ми допомогали один одному, підказували, як можна покращити нашу бібліотеку та постійно вели комунікацію про це в команді.
Під час роботи над цим комп'ютерним проєктом ми отримали нові знання з розділу дискретної математики - графи, познайомились з різноманітними алгоритмами для безпосередньої роботи з графами та покращили навики роботи з різноманітними бібліотеками мови програмування Python.
Даний проєкт став для нас відкриттям, оскільки ми працювали над алгоритмами, які можна застосувати не лише для теоретичної роботи з графами, але й для вирішення завдань у реальному житті.
Він також подарував нам цікавий досвід роботи в команді та показав, що працюючи спільно можна знайти ефективні та неочевидні вирішення поставлених завдань, і найважливіше - створити ефективну та корисну програму.