застосування теорії графів в прикладних програмах

[BogdanM]

Доброго дня усім! Будь-ласка читайте цей допис, якщо у вас відпустка і не знаєте чим зайнятись під час обідньої спеки, поглинаючи черговий кілограмчик кавуну  

Трапилася така історія: заходить до мене друг і каже: "Три тижні до захисту, в мене нічого нема. Допоможеш?"  
Подумали трохи та й вигадали щось практичне, що можна здати в якості дипломної роботи (дописивши трохи теорії і "води").
Це програма для автоматичного розрахунку кільцевої гідравлічної мережі методом Лобачова-Кросса.
Взяли графічний (Qt4) редактор графів GESloth by zifter @ github, прив'язали туди алгоритм розрахунку гідр. систем та взялись писати алгоритм пошуку контурів в неорієнтованому графі і це, як виявилось, стало найбільшою проблемою.

Про пошук замкнених контурів в графах:
існуючі алгоритми(Hawick, Tiersen) працюють тільки на диграфах, в яких стрілочки розташовані так, що пройшовши через кожну ділянку 1 раз, ви повернетесь до початку. Проте в гідравлічних системах це не так. Також наявні алгоритми взагалі не застосовні до неорієнтованих графів(де нема значення як ставити стрілочки).

Що ж тоді робити? Написали код, який розпізнає елементарні контури (3-4 вершини), він також виділяє контури-контейнери(що містять в собі біль елементарні контури), якщо запустити рекурсивно, то має спрацювати (спробую найближчим часом). Це було досягнуто за допомогою використання алгоритму Крускала(hydro/kruskal.cpp) для побудови кістяку(остову) дерева, проводиться порівнювання кістяку із оригінальним графом.
Цікаво, що шаблонні бібліотеки C++ Boost мають майже все для графів, але їхні хідери читати просто неможливо, не кажучи про код. Якщо нормальні люди позначають графи цілими числами, то вони -- абстрактними типами 3го рівня namespace. Надіюсь, інші модулі не такі жахливчики.

Інші проблеми: визначення орієнтації гілок відносно вибраного напрямку замкненого контуру.
 Як розпізнати які гілки позначити "+" (за годинниковою стрілкою), а які "-"?
 Ця проблема була вирішена порівнянням вхідного графу(це пари чисел, які позначають з'єднані вузли) із знайденими контурами, але контури мають бути знайдені правильно.

код @ github.com
шматок дипломної роботи(той, що без води) та скріншот знаходяться в директорії tiny_documentation/
В додатку roz5_1.pdf трохи теорії щодо графів та як воно в роботі використовувалось, також стислий список функцій програми, зображення (трохи кривої) форми програми на Qt5(C++).

Що з дипломом? Друг захистився на 4-ку, програму навіть ніхто не дивився, бо в роботі нарисували купу "розумних" на перший погляд діаграм.
Мораль історії така: пишу це, щоб виговоритись, бо результат роботи нікому не треба але хтозна, може якогось студента на linux.org.ua врятує?
 Мені було цікаво взятись за нову задачу (з графами діла ніколи не мав, я фізик) і закодувати її в C++ (в майбутньому планую перехід на Go lang.).

Майбутнім студентам: будь-ласка, обирайте спеціальність, яка вас зацікавить і має застосування в Україні, бо будете страждати ви і ваші друзі. Хороший електрик більш цінний (і менш безробітний) за випускника вишу, який нічого не навчився.

Дякую за увагу.

[xuser13]

Можна передерти трохи змінивши і видати як за своє. Тільки погано що немає посилання на власне саму дипломну роботу.
Мене більше цікавить чому в README на github викорастоно слово redactor а не editor. І в яких випадках одне слово має перевагу над іншим.

[BogdanM]

Не виклав роботу повністю, оскільки цього не побажав друг, я б це зробив.
Але, чесно кажучи, всі попередні розділи роботи -- ще більше непотрібної теорії і "води".
Наприклад, там розповідається про прототип БД для зберігання параметрів гідравлічних мереж.
Але саму БД ніхто не робив, так в тому виші заведено -- можна розказати про "високі матерії", але нічого не робити.
Я лише виклав приклад застосування графів і програму(в якій цінність являють лише деякі шматки коду), це є власне те, що ми з другом дійсно зробили. В коді також всюди використовується QList<T>, лише іноді gsl_vector, бо після роботи гратися з контролем розміру масивів не було часу.

Про слово "redactor". Як я казав раніше, редактор графів я взяв у іншого автора -- zifter'a. Це з його Readme залишилось
Швидше за все правильно буде "editor", а "redactor" -- це видимо була транслітерація, зроблена автором.
До речі GESloth -- єдиний графічний редактор графів на Qt4, я всюди шукав.
Якщо комусь цікаво, як з нього діставати власне граф, то напишу тут нижче, бо внаслідок складної моделі ООП автора GESloth, це вимагатиме деяких зусиль:

Код: [Вибрати]

/*якимось чином отримуємо вказівник на таб-віджет, це редагуються графи,
краще додати до головного класу метод GESTabWidget * GESloth ::GetTabPtr() const;
*/
const GESTabWidget *TabWidgetPtr = GESloth->mTabWidget;
GESScene *current_scene = TabWidgetPtr->getCurrentPage()->getScene();
Graph *curr_graph = current_scene->getGraph();

QList<Node*> nodes_list = curr_graph->nodes();
QList<Edge*> edges_list = curr_graph->edges();
В свою чергу всі об'єкти класів Node та Edge мають списки приєднаних вузлів/ділянок графу,
їх я і передаю алгоритму для гідравлічних мереж.

Бажаю гарного дня!
[/font]

[yurchor]

Цікава річ. Щодо відсутності редакторів, є Rocs, для нього все це можна реалізувати (принаймні мені так здається). Виглядає він краще і можливостей там наче більше.

[BogdanM]

Дякую. Цікава штука. Я шукав щось примітивне, щоб легко можна модифікувати код, тому зупинився на GESloth, навіть сам автор пише в повідомленні git commit -m "old sht left for history" .

Мене в розробці 100%-робочого алгоритму зупинила та проблема пошуку кілець, поки-що там тільки є обробка часткового випадку.

Просто не вірилось, що такий чудовий і найшвидший на сьогодні алгоритм пошуку замкнених контурів Хавіка (paper, code @ github) не працює для неорієнтованого графу, або для диграфу із ділянками контуру різного напрямку. Компілював D-код автора і досліджував.

Перепрошую за те, що стільки уваги користувачів приділив пошуку контурів, але це розділ "Розробка" і якщо хтось колись надумає писати свій симулятор електричних або ще яких-небудь ланцюгів, то ці проблеми з графами чекатимуть на вас.