Топологічне сортування вершин орієнтованого графа
Нехай розглядається деякий орієнтований граф 
який не містить циклів. Під топологічним сортуванням даного графа розуміють процес лінійного впорядковування його вершин таким чином, що якщо в графі існує ребро 
, то, в упорядкованому списку вершин графа , вершина 
передує вершині 
. Якщо в орієнтованому графі є цикли, то упорядкованого таким чином списку для нього не існує.
Орієнтований граф та один з варіантів топологічного сортування його вершин
Відмітимо, що задачу про топологічне сортування можна переформулювати наступним чином: розмістити вершини орієнтованого графа на горизонтальній прямій таким чином, щоб всі його ребра йшли зліва направо. У житті це відповідає, наприклад, наступним проблемам: в якому порядку слід здійснювати розв'язок задачі, якщо вона розпадається на підзадачі і виконання деяких підзадач, зазвичай, починається слідом за закінченням інших; в якому порядку слід розташовувати теми в шкільному курсі математики, якщо для кожної теми відомо, знання яких інших тем необхідні для її вивчення; в якому порядку необхідно розподілити опис процедур в програмі, якщо деякі процедури можуть містити звернення до інших процедур.
Растеризація кола використовуючи алгоритм Брезенхема
У параграфі растеризація відрізка за алгоритмом Брезенхема було розглянуто один з найвідоміших і найбільш викокористовуваних алгоритмів комп'ютерної графіки, призначених для розкладання відрізка в растр. Сьогодні розглянемо найбільш ефективний і простий для розуміння алгоритм генерації більш складної геометричної фігури, а саме кола, який також належить Брезенхему. Для початку зауважимо, що згідно з цим алгоритмом, достатньо згенерувати тільки одну четверту чи навіть одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на насутпному малюнку.
Генерація повного кола з дуги в першому октанті
Тобто, якщо згенерований перший октант (від 
до 
проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої 
, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої 
для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої 
для завершення побудови. Відмітимо, що на рисунку наведені двовимірні матриці відповідних перетворень.
Перевірка орієнтованого графа на наявність циклів
Розглядаючи алгоритм обходу орієнтованого графа в глибину ми звертали увагу на те, що більшість задач, що стосуються графів такого типу, вирішуються з використанням даного алгоритму. Сьогодні розглянемо задачу, яка полягає у визначенні того, чи являється орієнтований граф ациклічним (нагадаємо, що орієнтований граф називають ациклічним, якщо в ньому немає циклів; циклом в орієнтованому графі називається шлях, що веде з вершини в саму себе), і покажемо, яким чином дана задача вирішується з допомогою глибинного обходу графа.
Отже, розглянемо деякий орієнтований граф 
. Для того, щоб перевірити даний граф на наявність циклів, виконуємо глибинний обхід всіх його вершин. В результаті, отримаємо дерево обходу в глибину. Якщо в побудованому дереві зустрінеться хоча б одне зворотне ребро, то ясно, що орієнтований граф має цикл. Справедливе і обернене твердження, тобто, якщо в орієнтованому графі є цикл, тоді зворотне ребро обов'язково зустрінеться при його обході методом пошуку в глибину. Щоб довести це, припустимо, що орієнтований граф має цикл.
Перевірка орієнтованого графа на наявність циклів
Нехай при обході даного графа методом пошуку в глибину вершині 
присвоєно найменшу глибину обходу серед усіх вершин, що становлять цикл. Розглянемо ребро 
, що належить цьому циклу. Оскільки вершина 
входить в цикл, то вона повинна бути нащадком вершини в побудованому дереві обходу в глибину. Тому ребро не може бути поперечним. Але, виходячи з того, що глибина обходу вершини більша за глибину обходу вершини то ребро також не може бути ні ребром дерева ні прямим ребром. Звідси, ребро є зворотним, як показано на малюнку, що міститься вище.
Відображення та редагування даних булевого типу використовуючи компонент TDBCheckBox
Компонент TDBCheckBox — пов'язаний з даними аналог звичайного індикатора TCheckBox. Він дозволяє відображати і редагувати дані поля булевого, а також символьного та числового типу. Якщо при виведенні даних булеве поле приймає значення True, то пов'язаний з ним індикатор являється включеним. Якщо ж в процесі редагування користувач включить або вимкне індикатор, то відповідно значення True або False запишеться у відповідному полі таблиці бази даних. Це один із способів забезпечити користувачеві безпомилкове введення значень в поле таблиці бази даних.
Зв'язок компонента типу TDBCheckBox з полем набору даних здійснюється за допомогою його властивостей DataSource типу TDataSource і DataField типу TDataField. Перше з властивостей вказує на ім'я компонента джерела даних, через який здійснюється зв'язок з набором даних. І властивість DataField для пов'язаного набору даних вказує ім'я поля.
Якщо ж delphi-компонент TDBCheckBox пов'язаний з полем символьного або числового типу, то у властивості ValueChecked типу String даного компонента заноситься рядок, який перераховує значення поля, при яких індикатор включається, а у властивості ValueUnchecked (також типу String) перераховуються значення, при яких індикатор вимикається (окремі значення розділяються крапкою з комою). При значеннях, що не перераховані ні у ValueChecked, ні у ValueUnchecked, індикатор TDBCheckBox переходить у невизначений стан, відображаючи сірий прапорець (навіть у тому випадку коли властивість AllowGrayed (відповідає за заборону переводу індикатора в невизначений стан) приймає значення False).
Відображення та редагування багаторядкових текстових даних використовуючи компонент TDBMemo
Delphi-компонент TDBMemo являє собою багаторядковий текстовий редактор, який, зазвичай, зв'язується з текстовими полями великих розмірів або з BLOB-полями, що спеціалізуються на збереженні текстових даних. Такі поля іноді називають MEMO-полями і вони реалізовані в таблицях формату dBase і Paradox. Нагадаємо, що при проектуванні таблиці за допомогою утиліти Database Desktop поле такого типу позначається символом «M».
Зауваження: у компоненті можна використовувати буфер обміну за допомогою стандартних засобів операційної системи або успадкованими від предка TCustomMemo методами CopyToClipBoard, CutToClipBoard і PasteFromClipBoard.
Як уже зазначалося, при розгляді основних характеристик візуальних компонентів призначених для роботи з базами даних, серед властивостей компонентів такого типу, і зокрема компонента TDBMemo, виділяють дві, що забезпечують зв'язок з даними. Це властивість DataSource типу TDataSource (вказує на джерело даних, з яким пов'язаний компонент TDBMemo) і властивість DataField типу TDataField (вказує на поле набору даних, з яким пов'язаний компонент TDBMemo). Скориставшись даними властивостями пов'яжемо компонент TDBMemo з полем description таблиці cars («Автомобілі») бази даних autobazar («Автобазар»). Для цього, відкриємо delphi-проект, який ми створювали при розгляді однорядкового текстового редактора TDBEdit та доповнимо головну форму одним компонентом DBMemo1 типу TDBMemo та ще одним компонентом типу TLabel (містяться на закладках Data Controls та Standard палітри компонентів Delphi відповідно).
Виведення записів набору даних в табличному вигляді використовуючи компонент TDBGrid
Для виведення записів набору даних в табличному вигляді зручно використовувати сітку, представлену delphi-компонентом типу TDBGrid. Зовнішній вигляд сітки відповідає внутрішній структурі таблиці бази даних і набору даних. При цьому, рядкам сітки відповідають записи, а стовпцям — поля.
Об'єкт TDBGrid зв'язується з джерелом даних через свою властивість DataSource, яке, в свою чергу, посилається на набір даних. Тобто, якщо на форму, де вже відповідним чином налаштовані невізуальні компоненти, наприклад, Table1 та DataSource1 помістити таблицю DBGrid1, і у властивості DataSource даної таблиці вказати значення DataSource1, то ми відразу ж побачимо вміст таблиці бази даних, що пов'язується з набором даних Table1. В нашому випадку це таблиця cars («Автомобілі») бази даних dbautobazar («Автобазар»).
Вивід вмісту таблиці cars в компоненті DBGrid1
Зауваження: у процесі виконання програми значення властивості DataSource можна змінювати, і таким чином, використовуючи одну таблицю TDBGrid, здійснювати відображення даних від декількох джерел.
Побудова дерева обходу в глибину для орієнтованого графа в середовищі програмування delphi
Розглядуваний в даному параграфі delphi-проект реалізує процес побудови дерева обходу в глибину для орієнтованого графа. Головна форма проекту, як і у випадку з глибинним обходом неорієнтованого графа, ділиться на дві частини і складається з панелі інструментів та графічного редактора.
Головне вікно проекту "Побудова дерева обходу в глибину для орієнтованого графа"
- Панель інструментів (компонент типу TPanel): містить чотири кнопки: «Додати вершину» (типу TSpeedButton), «Додати ребро» (типу TSpeedButton), «Видалити граф» (типу TButton) та «Побудувати дерево обходу в гибину» (типу TButton). Відмітимо, що три кнопки з даного списук призначенні для побудови та видалення орієнтованого графа і четверта — реалізує його глибинний обхід.
- Графічний редактор (компонент типу TImage): призначений для побудови і візуалізації орієнтованого графа, а також візуалізації відповідного йому дерева обходу в глибину. Для того, щоб намалювати вершини графа потрібно, на першому кроці, активізувати кнопку панелі задач «Додати вершину». На наступному кроці, з допомогою лівої кнопки мишки, розставити їх у відповідній області форми. Після того, як вершини створено потрібно пов'язати їх відповідним орієнтованим ребром. Орієнтоване ребро в даній програмі створюється наступним чином: активізувавши кнопоку «Додати ребро» лівою кнопокою миші поєднюємо необхідні вершини. Для видалення графа чи побудови його дерева обходу в глибину необхідно скористатися однойменними кнопками що містяться на панелі задач.
В якості демонстрації можливостей роботи програми, наведемо приклад рішення задачі, яка полягає у побудові дерева обходу в глибину для орієнтованого графа, що міститься на настуному малюнку:
Загрузка ...