Министерство науки и образования Российской Федерации
Государственное образовательное учреждение высшего профессионального
Образования Московской области
Международный университет природы, общества и человека “Дубна”
Филиал «Протвино»
Дневник прохождения практики
| 1.ФИО студента: Михалевский Евгений Александрович 2.Курс, группа: 3 курс, группа ПС082 3.ФИО руководителя: доц. Кульман Никита Юрьевич 4.Место прохождения практики: ООО «Систел» 5.ФИО руководителя на предприятии (с указанием подразделения и должности): Кульман Никита Юрьевич, зам. генерального директора по АСДУ |
Задание по практике
(заполняется руководителем практики от кафедры)
| 1. | Изучить и освоить организацию существующего на предприятии программного обеспечения, с которым проводилась работа |
| 2. | Изучить и освоить основные принципы работы в среде программирования Microsoft Visual C++ 2010 |
| 3. | Изучить и освоить библиотеку компонентов Boost Graph Library |
| 4. | Изучить и освоить применяемое прикладное программное обеспечение |
| 5. | На основе используемого на предприятии программного обеспечения создать приложение для работы с графами |
| 6. | Составить отчет о проделанной работе |
Задание по практике согласовано с руководителем от предприятия:
_____________ Кульман Никита Юрьевич ____________ 2011г.
подпись ФИО дата
Проверка выполнения задания
| № п/п | Выполненные работы | Дата | Подпись |
| 1. | Изучил и освоил организацию существующего на предприятии программного обеспечения, с которым проводилась работа | 1.07.2011 - 4.07.2011 | |
| 2. | Изучил и освоил основные принципы работы в среде программирования Microsoft Visual C++ 2010 | 5.07.2011 -7.07.2011 | |
| 3. | Изучил и освоил библиотеку компонентов Boost Graph Library | 8.07.2011 - 14.07.2011 | |
| 4. | Изучил и освоил применяемое прикладное программное обеспечение | 15.07.2011-18.07.2011 | |
| 5. | На основе используемого на предприятии программного обеспечения создал приложение для работы с графами | 19.07.2011-27.07.2011 | |
| 6. | Составил отчет о проделанной работе | 28.08.2011 |
Заключение о прохождении практики
| Рецензия руководителя практики от предприятия (степень выполнения задания) | Рецензия руководителя практики от кафедры (степень выполнения задания) |
| Рекомендуемая оценка: | Рекомендуемая оценка: |
| Замечания или предложения по внедрению результатов конкретной работы студента | Замечания или предложения по внедрению результатов конкретной работы студента |
| Дата, подпись: | Дата, подпись: |
«Международный университет природы, общества и человека «Дубна»
Филиал «Протвино»
Кафедра Информационных технологий
ОТЧЕТ ПО УЧЕБНОЙ ПРАКТИКЕ
Тема: «Создание приложения для работы с графами»
Выполнил:
студент группы ПС082
Михалевский Е.А.
Проверил:
доц., к.ф.-м.н. Кульман Н.Ю.
оценка ___________________
дата _____________________
подпись __________________
Протвино – 2011 г.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………………………………………3
1 ОПИСАНИЕ СРЕДЫРАЗРАБОТКИ………………………………………………………...5
1.1 Среда программирования Microsoft Visual C++ 2010………………………………….. 5
1.2 Библиотека компонентов Boost Graph Library……………………….…………………..5
2 ПОСТАНОВКА ЗАДАЧИ……………………………………………………………………..7
3 ОПИСАНИЕ ПРИЛОЖЕНИЯ………………………………………………………………...8
3.1 Основные классы…………………………………………………………………………..8
3.2 Работа с приложением…………………………………………………………………….9
ЗАКЛЮЧЕНИЕ…………………………………………………………………………………13
СПИСОК ЛИТЕРАТУРЫ……………………………………………………………………...14
ВВЕДЕНИЕ
ООО «Систел» занимается разработкой, проектированием и внедрением комплексных автоматизированных систем и интеграционных решений для промышленных предприятий, поставкой программно-технических комплексов, внедрением автоматизированных систем диспетчерского и технологического управления и учета электроэнергии для электроэнергетических и промышленных предприятий различного масштаба.
Любые предприятия имеют в своем составе те или иные инженерные сети: системы электроснабжения, средства связи, системы управления и другие. При разработке программного обеспечения удобно представлять их с использованием инструментов теории графов.
В математической теории графов и информатике граф является совокупностью непустого множества вершин и множества ребер, соединяющих эти вершины. Теория графов находит применение в различных областях: в информатике, программировании, логистике, экономике, коммуникационных и транспортных системах. Применение различных вычислений, производимых на графе, позволяет, например, найти кратчайший маршрут между двумя точками, максимальное количество некоторой сущности, способное пройти через сеть одновременно, и многое другое.
Графы могут быть неориентированными, в которых не имеет значение направление ребер, и ориентированными, в которых направление ребер важно.
При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.
Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
Задание множеств вершин и ребер графа возможно несколькими способами:
1) матрицей смежности. Представляет собой таблицу, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот);
2) матрицей инцидентности. Каждая строка соответствует определённой вершине графа, а столбцы соответствуют ребрам. В ячейку на пересечении i -ой строки с j -м столбцом матрицы записывается 1, если ребро j «выходит» из вершины i, −1, если ребро «входит» в вершину, и 0, если ребро не инцидентно вершине;
3) списком ребер. Подразумевает, что каждое ребро представляется двумя числами – номерами вершин этого ребра.
ОПИСАНИЕ СРЕДЫРАЗРАБОТКИ
1.1 Среда программирования Microsoft Visual C++ 2010
Microsoft Visual C++ (MSVC) – интегрированная среда разработки приложений на языке C++, разработанная фирмой Microsoft и поставляемая либо как часть комплекта Microsoft Visual Studio, либо отдельно в виде бесплатного функционально ограниченного комплекта Visual C++ Express Edition. Является одной из наиболее удобных и популярных во всем мире для создания различных приложений.
Visual С++ включает в себя редактор исходного кода с поддержкой технологии IntelliSense и возможностью простейшего рефакторинга кода. Встроенный отладчик может работать как отладчик уровня исходного кода, так и как отладчик машинного уровня. Остальные встраиваемые инструменты включают в себя редактор форм для упрощения создания графического интерфейса приложения, веб-редактор, дизайнер классов и дизайнер схемы базы данных. Visual Studio позволяет создавать и подключать сторонние дополнения (плагины) для расширения функциональности, добавление новых наборов инструментов (например, для редактирования и визуального проектирования кода на предметно-ориентированных языках программирования или инструментов для прочих аспектов цикла разработки программного обеспечения).
1.2 Библиотека компонентов Boost Graph Library
Библиотека компонентов Boost Graph Library (BGL) является частью коллекции Boost, содержащей в себе набор библиотек, хорошо совместимых со стандартной библиотекой C++.
BGL по своей организации сходна со стандартной библиотекой шаблонов C++ (STL).
Каждый BGL-алгоритм может работать с широким набором последовательных структур данных: связные списки, массивы, множества и т. п. Абстракция итератора обеспечивает интерфейс между контейнерами и алгоритмами, а шаблонный механизм C++ предоставляет нужную гибкость в реализации без потери эффективности. Каждый алгоритм в BGL является шаблоном функции, параметризованным по типам итераторов, с которыми он работает. Любой итератор, который удовлетворяет минимальному набору требований, может быть использован независимо от структуры данных, обходимой итератором. Системный подход, использованный в BGL для построения абстракций и взаимозаменяемых компонентов, называется обобщенным программированием. Таким образом, BGL применяет понятия обобщенного программирования при создании алгоритмов на графах.
Обобщенное программирование хорошо зарекомендовало себя при решении проблемы повторного использования кода для библиотек алгоритмов на графах. В рамках обобщенного программирования алгоритмы на графах могут быть сделаны более гибкими и легко используемыми в большом наборе приложений. Каждый графовый алгоритм пишется не в терминах специфической структуры данных, а для графовой абстракции, которая может быть реализована многими различными структурами данных. Написание обобщенных графовых алгоритмов имеет дополнительное преимущество, являясь более естественным. Абстракция, свойственная псевдокоду описания алгоритма, сохраняется в обобщенной функции.
2 ПОСТАНОВКА ЗАДАЧИ
В рамках данной учебной практики требуется создать приложение для работы с графами. Средством создания приложения является среда программирования Microsoft Visual C++ 2010 с использованием библиотеки компонентов BGL. Графической основой для создания приложения является используемое на предприятии приложение DrawClient, позволяющее создавать изображения, состоящие из основных геометрических фигур. Требуется отредактировать программный код приложения DrawClient и адаптировать его для возможности работы с графами.
Создаваемое приложение должно отвечать следующим требованиям:
– иметь удобный и интуитивно понятный интерфейс;
– обладать свойствами надежности;
– обладать необходимыми функциональными возможностями
Приложение должно иметь следующие функциональные возможности:
– выбор вида графа (ориентированный или неориентированный);
– добавление вершин и ребер;
– удаление вершин и ребер;
– использование алгоритмов работы с графами.
Приложение должно поддерживать следующие алгоритмы работы с графами:
– вывод списка смежных вершин для каждой вершины;
– нахождение расстояния до вершин от данной вершины;
– поиск в ширину;
– поиск в глубину;
– топологическая сортировка (для ориентированного графа).
3 ОПИСАНИЕ ПРИЛОЖЕНИЯ
3.1 Основные классы
Приложение содержит следующие основные классы:
1) CMainFrame – класс основного окна приложения. Содержит функции для отображения элементов окна приложения;
2) CDrawDoc – класс документа. Каждому документу соответствует один граф. Класс содержит объявление графа и функции, вызываемые при работе с документом (например, функция OnNewDocument выполняется при создании нового документа, устанавливает параметры документа (такие, как заголовок) и вызывает диалоговое окно для выбора вида графа). Также класс содержит переменную перечисляемого типа GraphType, которая может принимать значения GRAPH_UNDIR_TYPE и GRAPH_BIDIR_TYPE (неориентированный и неориентированный граф соответственно). Значение переменной устанавливается в результате выбора вида графа в диалоговом окне класса DialogGraph и определяет, с каким из графов будет производиться дальнейшая работа в рамках данного документа;
3) CDrawView – класс представления документа. Содержит функции, вызываемые для отображения действий с объектами в документе (вершинами и ребрами графа), такие как выбор объекта, его добавление и удаление из представления документа (в том числе, добавление ребер между выбранными вершинами), а также вспомогательные функции, например, для пересчета координат из физических в логические и обратно;
4) CDrawTool – класс инструментов представления. Является связующим звеном между классами CDrawView и CDrawObj. Содержит функции, обрабатывающие действия пользователя, такие как клик мышью и перетаскивание объекта. Содержит два дочерних класса: CSelectTool (при совершении действий с выбранном объектом) и CRectTool (при совершении действий вне конкретного объекта, в том числе, при клике мышью в документе для добавления вершины).
5) CDrawObj – класс объекта. Содержит информацию об объекте и функции для работы с ним, в том числе для непосредственной прорисовки объекта на экране;
6) COutputViewBar – класс панели Output. Содержит функции для работы с панелью для вывода результатов работы алгоритмов обработки графа;
7) COutputList – класс списка. Содержит функции для работы с информацией в панели класса COutputViewBar;
8) CDrawApp – класс приложения. Содержит функции для обработки процессов запуска и закрытия приложения;
9) CRibbonListButton – класс ленты меню основного окна приложения. Содержит функции для работы с самой лентой, ее панелями и кнопками;
10) DialogGraph – класс диалога для выбора вида графа. Содержит функции для обработки действий по выбору вида графа.
3.2 Работа с приложением
При запуске приложения, а также при создании нового документа (каждый из которых соответствует одному графу) на экран выводится диалоговое окно для выбора типа графа (ориентированный или неориентированный). После выбора и нажатия кнопки ОК создается новый документ, в заголовке которого указан тип графа.
Внешний вид приложения после запуска представлен на рисунке 1.
Рисунок 1 – Внешний вид окна приложения
В верхней части окна приложения находится лента меню Graphs, содержащая две панели: Draw и Algorithms. Панель Draw содержит инструменты: Vertex – для рисования вершин, Select – для выбора объекта. Панель Algorithms содержит алгоритмы для обработки графа.
Ниже меню находится вкладка документа (их может быть несколько, по количеству созданных документов), содержащая изображение графа текущего документа.
В самом низу находится панель статуса, содержащая информацию о количестве вершин, количестве ребер и количестве выделенных в данный момент объектов.
Также на экране присутствует перемещаемая панель Output для вывода результатов работы алгоритмов обработки графа.
Для добавления вершины в граф необходимо выбрать инструмент Vertex в панели Draw, а затем кликнуть мышью в поле документа. Вершина появится на изображении и ей будет присвоен порядковый номер. Если среди уже существующих вершин отсутствует какой-то номер (вследствие удаления вершины), то вновь созданной вершине будет присвоен этот номер, если таких номеров несколько, то наименьший из них.
Для добавления ребра необходимо выделить две вершины (для чего нужно кликнуть сначала на одну из них, а затем, с зажатой клавишей Shift, на другую), потом щелкнуть правой клавишей мыши, нажать «Add Edge», и ребро появится на изображении. Ребру будет присвоено название в формате «[исходящая вершина] – [входящая вершина]». Для ориентированного графа вместо «–» будет изображено «->». В случае добавления в ориентированном графе ребра, обратного уже существующему, в названии на изображении стрелка будет изменена на двунаправленную («<->»).
Положение вершин на изображении можно менять перетаскиванием, вместе с ними будут менять свое положение инцидентные им ребра.
Для удаления вершины или ребра нужно выделить его и нажать клавишу Delete. Если удаляется одно из двух взаимообратных ребер ориентированного графа, то перед удалением будет выведено сообщение с вопросом о том, какое именно из двух ребер желает удалить пользователь.
Пример внешнего вида документа с изображенным ориентированным графом представлен на рисунке 2.
Рисунок 2 – Пример внешнего вида документа с ориентированным графом
Для работы с алгоритмами обработки графа необходимо после создания графа нажать кнопку соответствующего алгоритма на панели Algorithms. Результат обработки будет выведен на панель Output. Доступны следующие алгоритмы обработки графов:
1) список смежных вершин. Выводит для каждой вершины список вершин, соединенных с ней ребрами. Для ориентированного графа выводит список вершин, в которые существует ребро из данной вершины;
2) поиск в ширину. Осуществляет вывод вершин графа в порядке, соответствующем поиску в ширину. Предварительно необходимо задать стартовую вершину;
3) расстояние до вершин. Выводит для каждой вершины количество вершин, находящихся на кратчайшем пути между стартовой и данной вершиной. Предварительно необходимо задать стартовую вершину;
4) поиск в глубину. Осуществляет вывод вершин графа в порядке, соответствующем поиску в глубину. Предварительно необходимо задать стартовую вершину;
5) топологическая сортировка. Осуществляет вывод вершин графа в порядке топологической сортировки. Данный алгоритм доступен только для ориентированных графов, не содержащих циклов.
Пример изображения ориентированного графа с выведенным результатом работы различных алгоритмов представлен на рисунке 3.
Рисунок 3 – Пример изображения ориентированного графа с выведенным результатом работы различных алгоритмов
ЗАКЛЮЧЕНИЕ
Конечной целью выполнения задания в рамках прохождения данной практики явилось написание приложения для работы с графами. В рамках написания приложения изучены основные принципы работы в среде программирования Microsoft Visual C++ 2010 и библиотека компонентов Boost Graph Library.
Созданное приложение отвечает предъявленным к нему требованиям: имеет удобный интерфейс, обладает необходимыми свойствами надежности, в частности, проверкой на некорректные действия пользователя, а также отвечает функциональным требованиям. В рамках дальнейшего расширения функциональных возможностей приложения целесообразно добавить больше алгоритмов обработки графов, добавить наглядные средства отображения результатов работы алгоритмов, а также возможно сохранения информации в файл и чтения из файла.
В целом требования, предъявленные к создаваемому приложению, можно считать достигнутыми, а задание по учебной практике – выполненным.
СПИСОК ЛИТЕРАТУРЫ
1. Шеферд Дж. Программирование на Microsoft Visual Studio C++.NET: [пер. с англ.] / Дж. Шеферд. – М.: Издательство «Русская редакция»; СПб.: Питер, 2007. – 928 с.
2. Сик Дж., Ли Л., Ламсдэйн Э. С++ Boost Graph Library: [пер. с англ.] / Р. Сузи. –СПб.: Питер, 2006. – 304 с.