Разработка модуля визуализации компьютерных структур с WEB-интерфейсом

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра вычислительных технологий

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Бакалавра

Разработка модуля визуализации компьютерных структур с WEB-интерфейсом

Работу выполнила

Я. И. Власова

Научный руководитель

к.ф.-м.н.

О. Н. Лапина

Краснодар 2014

РЕФЕРАТ

Дипломная работа 31 с., 8 рисунков. 7 источников.

Целью работы является разработка модуля визуализации компьютерных структур под Web-интерфейс. Первая часть работы заключается в создании приложения, которое на вход получает компьютерную структуру, обрабатывает ее и выводит на экран. Структура, которую на входе получает программа, уже полностью подготовлена к обработке. Вторая часть работы заключается в подключении этого приложение к Веб-странице.

В работе использовался язык программирования С++ и среда разработки Qt Creator с использованием графических библиотек Qt. Программа была написана под операционную систему Linux.

КЛЮЧЕВЫЕ СЛОВА ДАННОЙ РАБОТЫ:

Моделирование структур, визуализация графовых структур, C++, графы.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. Моделирование

1.1 Основы моделирования

1.2 Классификация моделей

1.3 Компьютерное имитационное моделирование

1.4 Моделирование компьютерных структур и систем

1.5 Этапы компьютерного моделирования структур и систем

2 Алгоритмы работы программного модуля

2.1 Представление графа

2.2 Краткое описание среды разработки Qt

2.3 Краткое описание используемых пространств имен и классов

3. Реализация программного модуля

3.1 Файлы программного модуля Beta

3.2 Пример работы программного модуля

3.3 Подключение программного модуля к Веб-странице

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ В

визуализация компьютерный интерфейс модуль

ВВЕДЕНИЕ

Основная цель работы состоит в создании программного модуля, который выводит изображение компьютерной структуры в виде графа на экран, и подключение этого модуля к веб-интерфейсу. Для реализации данного модуля используются языки С и С++ с использованием классов и методов Qt в среде разработке Qt Сreator.

Программный модуль в качестве входных данных получает ссылку на некоторый граф, представленный графом дескрипторов. Далее, программа анализирует граф, используя методы реализации данного графа, которые находятся в заголовочном файле (или подключаемом модуле). Для более «красивого» вывода изображения на экран компьютера необходимо разработать алгоритм и оптимизировать его для удобства пользователя. Когда программный модуль будет полностью разработан, необходимо реализовать его запуск через веб-интерфейс на стороне сервера, и последующий вывод результата на веб-страницу.

1.МОДЕЛИРОВАНИЕ

1.1 Основы моделирования

В процессе изучения окружающего мира субъекту познания противостоит исследуемая часть объективной реальности - объект познания. Ученый, используя эмпирические методы познания (наблюдение и эксперимент), устанавливает факты, характеризующие объект. Элементарные факты обобщаются и формулируются эмпирические законы. Следующий шаг состоит в развитии теории и построении теоретической модели, объясняющей поведение объекта и учитывающей наиболее существенные факторы, влияющие на изучаемое явление. Эта теоретическая модель должна быть логичной и соответствовать установленным фактам. Можно считать, что любая наука представляет собой теоретическую модель определенной части окружающей действительности.

Часто в процессе познания реальный объект заменяется некоторым другим идеальным, воображаемым или материальным объектом , несущим изучаемые черты исследуемого объекта , и называемым моделью. Эта модель подвергается исследованию: на нее оказывают различные воздействия, изменяют параметры и начальные условия, и выясняют, как изменяется ее поведение. Результаты исследования модели переносят на объект исследования , сопоставляют с имеющимися эмпирическими данными и т.д.

Таким образом, модель - это материальный или идеальный объект, замещающий исследуемую систему и адекватным образом отображающий ее существенные стороны. Модель должна в чем-то повторять исследуемый процесс или объект со степенью соответствия, позволяющей изучить объект-оригинал . Чтобы результаты моделирования можно было бы перенести на исследуемый объект, модель должна обладать свойством адекватности. Преимущество подмены исследуемого объекта его моделью в том, что часто модели проще, дешевле и безопаснее исследовать. Действительно, чтобы создать самолет, следует построить теоретическую модель, нарисовать чертеж, выполнить соответствующие расчеты, изготовить его уменьшенную копию, исследовать ее в аэродинамической трубе и т.д.

Модель объекта должна отражать его наиболее важные качества, пренебрегая второстепенными. Тут уместно вспомнить притчу о трех незрячих мудрецах, решивших узнать что такое слон. Один мудрец подержал слона за хобот, и заявил, что слон -- гибкий шланг. Другой потрогал слона за ногу и решил, что слон - это колонна. Третий мудрец подергал за хвост и пришел к мнению, что слон - это веревка. Ясно, что все мудрецы ошиблись: ни один из названных объектов (шланг, колонна, веревка) не отражают существенных сторон изучаемого объекта (слон), поэтому их ответы (предлагаемые модели) не являются правильными.

При моделировании могут преследоваться различные цели: 1) познание сущности изучаемого объекта, причин его поведения, “устройства” и механизма взаимодействия элементов; 2) объяснение уже известных результатов эмпирических исследований, верификация параметров модели по экспериментальным данным; 3) прогнозирование поведения систем в новых условиях при различных внешних воздействиях и способах управления; 4) оптимизация функционирования исследуемых систем, поиск правильного управления объектом в соответствии с выбранным критерием оптимальности.

1.2 Классификация моделей

Используемые модели чрезвычайно разнообразны. Системный анализ требует классификации и систематизации, то есть структурирование изначально неупорядоченного множества объектов и превращение его в систему. Известны различные способы классификации существующего многообразия моделей. Выделяют следующие виды моделей:

1) детерминированные и стохастические;

2) статические и динамические;

3) дискретные, непрерывные и дискретно-непрерывные;

4) мысленные и реальные.

Также модели классифицируют по следующим основаниям:

1) по характеру моделируемой стороны объекта;

2) по отношению ко времени;

3) по способу представления состояния системы;

4) по степени случайности моделируемого процесса;

5) по способу реализации.

При классификации по характеру моделируемой стороны объекта выделяют следующие виды моделей:

1) Кибернетические или функциональные модели; в них моделируемый объект рассматривается как “черный ящик”, внутреннее устройство которого неизвестно. Поведение такого “черного ящика” может описываться математическим уравнением, графиком или таблицей, которые связывают выходные сигналы (реакции) устройства с входными (стимулами). Структура и принципы действия такой модели не имеют ничего общего с исследуемым объектом, но функционирует она похожим образом. Например, компьютерная программа, моделирующая игру в шашки.

2) Структурные модели - это модели, структура которых соответствует структуре моделируемого объекта. Примерами являются командно-штабные учения, день самоуправления, модель электронной схемы в Electronics Workbench и т.д.

3) Информационные модели, представляющие собой совокупность специальным образом подобранных величин и их конкретных значений, которые характеризуют исследуемый объект. Выделяют вербальные (словесные), табличные, графические и математические информационные модели. Например, информационная модель студента может состоять из оценок за экзамены, контрольные и лабораторные работы. Или информационная модель некоторого производства представляет набор параметров, характеризующих потребности производства, его наиболее существенные характеристики, параметры выпускаемого товара.

По отношению ко времени выделяют:

1) Статические модели - модели, состояние которых не изменяется с течением времени: макет застройки квартала, модель кузова машины.

2) Динамические модели представляют собой функционирующие объекты, состояние которых непрерывно изменяется. К ним относятся действующие модели двигателя и генератора, компьютерная модель развития популяции, анимационная модель работы ЭВМ и т.д.

По способу представления состояния системы различают:

1) Дискретные модели - это автоматы, то есть реальные или воображаемые дискретные устройства с некоторым набором внутренних состояний, преобразующие входные сигналы в выходные в соответствии с заданными правилами.

2) Непрерывные модели - это модели, в которых протекают непрерывные процессы. Например, использование аналоговой ЭВМ для решения дифференциального уравнения, моделирования радиоактивного распада с помощью конденсатора, разряжающегося через резистор и т.д.

По степени случайности моделируемого процесса выделяют:

1) Детерминированные модели, которым свойственно переходить из одного состояния в другое в соответствии с жестким алгоритмом, то есть между внутренним состоянием, входными и выходными сигналами имеется однозначное соответствий (модель светофора).

2) Стохастические модели, функционирующие подобно вероятностным автоматам; сигнал на выходе и состояние в следующий момент времени задается матрицей вероятностей. Например, вероятностная модель ученика, компьютерная модель передачи сообщений по каналу связи с шумом и т.д.

По способу реализации различают:

1) Абстрактные модели, то есть мысленные модели, существующие только в нашем воображении. Например, структура алгоритма, которая может быть представлена с помощью блок-схемы, функциональная зависимость, дифференциальное уравнение, описывающее некоторый процесс. К абстрактным моделям также можно отнести различные графические модели, схемы, структуры, а также анимации.

2) Материальные (физические) модели представляют собой неподвижные макеты либо действующие устройства, функционирующие в чем-то подобно исследуемому объекту. Например, модель молекулы из шариков, макет атомной подводной лодки, действующая модель генератора переменного тока, двигателя и т.д. Реальное моделирование предусматривает построение материальной модели объекта и выполнение с ней серии экспериментов. Например, для изучения движения подводной лодки в воде строят ее уменьшенную копию и моделируют течение с помощью гидродинамической трубы.

Математические модели довольно разнообразны и тоже могут быть классифицированы по разным основаниям. По степени абстрагирования при описании свойств системы они делятся на мета-, макро- и микромодели. В зависимости от формы представления различают инвариантные, аналитические, алгоритмические и графические модели. По характеру отображаемых свойств объекта модели классифицируют на структурные, функциональные и технологические. По способу получения различают теоретические, эмпирические и комбинированные. В зависимости от характера математического аппарата модели бывают линейные и нелинейные, непрерывные и дискретные, детерминированные и вероятностные, статические и динамические. По способу реализации различают аналоговые, цифровые, гибридные, нейронечеткие модели, которые создаются на основе аналоговых, цифровых, гибридных вычислительных машин и нейросетей.

1.3 Компьютерное имитационное моделирование

Компьютерное моделирование основывается на:

1. Построении математических моделей для описания изучаемых процессов;

2. Использовании новейших вычислительных машин, обладающих высоким быстродействием и способных вести диалог с человеком.

Суть компьютерного моделирования состоит в следующем: на основе математической модели с помощью ЭВМ проводится серия вычислительных экспериментов, т.е. исследуются свойства объектов или процессов, находятся их оптимальные параметры и режимы работы, уточняется модель.

Имитационные модели - это проводимые на ЭВМ вычислительные эксперименты с математическими моделями, имитирующими поведение реальных объектов, процессов или систем.

Имитационное моделирование представляет собой численный метод проведения на ЭВМ вычислительных экспериментов с математическими моделями, имитирующими поведение реальных объектов, процессов и систем во времени в течение заданного периода.

Основное достоинство имитационного моделирования:

1. Возможность описания поведение элементов процессов или систем на высоком уровне детализации;

2. Возможность исследования динамики взаимодействия компонент во времени и пространстве параметров системы;

Эти достоинства обеспечивают имитационному методу широкое распространение.

Рекомендуется использовать имитационное моделирование в следующих случаях:

1. Если не существует законченной постановки задачи исследования и идет процесс познания объекта моделирования. Имитационная модель служит средством изучения явления.

2. Если аналитические методы имеются, но математические процессы сложны и трудоемки, и имитационное моделирование дает более простой способ решения задачи.

3. Когда кроме оценки влияния параметров (переменных) процесса или системы желательно осуществить наблюдение за поведением компонент (элементов) процесса или системы (ПС) в течение определенного периода.

4. Когда имитационное моделирование оказывается единственным способом исследования сложной системы из-за невозможности наблюдения явлений в реальных условиях (реакции термоядерного синтеза, исследования космического пространства).

5. Когда необходимо контролировать протекание процессов или поведение систем путем замедления или ускорения явлений в ходе имитации.

6. При подготовке специалистов для новой техники, когда на имитационных моделях обеспечивается возможность приобретения навыков в эксплуатации новой техники.

Однако имитационное моделирование наряду с достоинствами имеет и недостатки:

1. Разработка хорошей имитационной модели часто обходится дороже создания аналитической модели и требует больших временных затрат.

2. Может оказаться, что имитационная модель неточна (что бывает часто), и мы не в состоянии измерить степень этой неточности.

3. Зачастую исследователи обращаются к имитационной модели, не представляя тех трудностей, с которыми они встретятся и совершают при этом ряд ошибок методологического характера.

И, тем не менее, имитационная модель является одним из наиболее широко используемых методов при решении задач синтеза и анализа сложных процессов и систем.

1.4 Моделирование компьютерных структур и систем

Система - совокупность объектов (элементов), взаимодействующих между собой и образующих определенную целостность, единство. При этом связь между элементами системы должна быть гораздо более сильной, чем связь каждого из этих элементов с частями других систем.

Под элементом системы понимается ее часть, предназначенная для выполнения определенных функций и неделимая на составные части при заданном уровне рассмотрения. Элемент системы может в свою очередь рассматриваться в качестве системы, а система, взятая в целом, может быть элементом более общей системы.

Связями называются элементы систем, осуществляющие непосредственное взаимодействие между другими элементами. Понятие связь одновременно характеризует строение (статику) и функционирование (динамику) системы.

Структура системы - наиболее существенные взаимодействия (связи) между элементами системы, которые мало меняются при изменении состояния системы и обеспечивают существование системы и ее основных свойств. Следует отметить, что при удалении из системы одного или нескольких элементов структура может остаться неизменной, а система может сохранить свою качественную определенность (в частности, работоспособность). Например, если из автомобиля убрать все элементы, которые обеспечивают безопасность и комфорт водителя и пассажиров, то от этого он не потеряет работоспособность, то есть структура останется неизменной.

1.5 Этапы компьютерного моделирования структур и систем.

Первый этап: уяснение целей моделирования. Цель существенным образом определяет содержание остальных этапов моделирования.

Второй этап: построение концептуальной модели. Концептуальная модель - модель на уровне определяющего замысла, который формируется при изучении моделируемого объекта. На этом этапе исследуется объект, устанавливаются необходимые упрощения. Выявляются существенные аспекты, исключаются второстепенные. Устанавливаются единицы измерения и диапазоны изменения переменных модели.

Результатом второго этапа является обобщенная схема модели, полностью подготовленная для математического описания - построения математической модели.

Третий этап: выбор языка программирования или моделирования, разработка алгоритма и программы модели. Модель может быть аналитической или имитационной, или их сочетанием.

Результатом третьего этапа моделирования является программа, составленная на наиболее удобном для моделирования и исследования языке - универсальном или специальном.

Четвертый этап: планирование эксперимента. Математическая модель является объектом эксперимента. Эксперимент должен быть в максимально возможной степени информативным, удовлетворять ограничениям, обеспечивать получение данных с необходимой точностью и достоверностью.

Результат четвертого этапа - план эксперимента.

Пятый этап: выполнение эксперимента с моделью. Если модель аналитическая, то эксперимент сводится к выполнению расчетов при варьируемых исходных данных. При имитационном моделировании модель реализуется на ЭВМ с фиксацией и последующей обработкой получаемых данных. Эксперименты проводятся в соответствии с планом, который может быть включен в алгоритм модели.

Шестой этап: обработка, анализ и интерпретация данных эксперимента. В соответствии с целью моделирования применяются разнообразные методы обработки: определение разного рода характеристик случайных величин и процессов, выполнение анализов (дисперсионного, регрессионного, факторного и др.). В ходе анализа полученных результатов модель может быть уточнена, дополнена или даже полностью пересмотрена.

2. АЛГОРИТМЫ РАБОТЫ ПРОГРАММНОГО МОДУЛЯ

2.1 Представление графа

Граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, а связи -- как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Неориентированный граф G - это упорядоченная пара G=(V,E), для которой выполнены следующие условия:

V - это непустое множество вершин, или узлов,

E - это множество пар (в случае неориентированного графа - неупорядоченных) вершин, нарываемых рёбрами.

Ориентированный граф G - это упорядоченная пара G=(V,А), для которой выполнены следующие условия:

V - это непустое множество вершин или узлов,

А - это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными ребрами.

Граф в разработанном программном модуле представлен совокупностью дескрипторов: дескриптор графа, дескриптор вершины, дескриптор входа, дескриптор выхода и дескриптор дуги. Для его реализации было создано 8 структур, 5 из которых представляют собой дескрипторы графа, и еще 3 - вспомогательные элементы, которые служат для более оптимальной связи входов-выходов с дугами (рис.1). Признак указывает на вид дескриптора. Признак 4 - это граф, 5 - вершина, 6 - вход/выход, 7 - дуга.

Рисунок 1-дескрипторы графа, вершины, входа/выхода и дуги

Для реализации модуля реализации была создана дополнительная структура, которая представляет собой список вершин, их имена и номера, и координаты для прорисовки.

2.2 Краткое описание среды разработки Qt

Программный модуль написан в среде разработки QT, так как это наиболее оптимальная среда для разработки графических приложений под семейство операционных систем Unix. Qt -- кросс-платформенный инструментарий разработки ПО на языке программирования C++. Позволяет запускать написанное с его помощью ПО в большинстве современных операционных системах путём простой компиляции программы для каждой ОС без изменения исходного кода. Включает в себя все основные классы, которые могут потребоваться при разработке прикладного программного обеспечения, начиная от элементов графического интерфейса и заканчивая классами для работы с сетью, базами данных и XML. Qt является полностью объектно-ориентированным, легко расширяемым и поддерживающим технику компонентного программирования.

Qt предоставляет программисту не только удобный набор библиотек классов, но и определённую модель разработки приложений, определённый каркас их структуры. Следование принципам и правилам «хорошего стиля программирования на C++/Qt» существенно снижает частоту таких трудно отлавливаемых ошибок в приложениях, как утечки памяти (memory leaks), необработанные исключения, незакрытые файлы или неосвобождённые дескрипторы ресурсных объектов, чем нередко страдают программы, написанные «на голом C++» без использования

Важным преимуществом Qt является хорошо продуманный, логичный и стройный набор классов, предоставляющий программисту очень высокий уровень абстракции. Благодаря этому программистам, использующим Qt, приходится писать значительно меньше кода, чем это имеет место при использовании, например, библиотеки классов MFC. Сам же код выглядит стройнее и проще, логичнее и понятнее, чем аналогичный по функциональности код MFC или код, написанный с использованием «родного» для X11 тулкита Xt. Его легче поддерживать и развивать.

Кроме того, даже если программисту в данный конкретный момент не нужна кроссплатформенность для его библиотеки Qt.конкретного приложения (например, планируется версия только для Windows или только для Macintosh), никто не может знать, что понадобится завтра. Бизнес-планы могут поменяться, и может оказаться и нужным, и выгодным выпустить версию для другой операционной системы или другой аппаратной платформы. В случае использования Qt для этого понадобится всего лишь перекомпиляция исходного кода. В случае же использования, например, MFC или «родных» системных API понадобится много тяжёлой работы по портированию, адаптации и отладке, а то и переписыванию с нуля существующего исходного кода для другой ОС или аппаратной платформы.

Многие компании-разработчики приложений Windows используют Qt ещё по одной причине: даже если код пишется и в обозримом будущем будет писаться только для платформы Windows и тестируется только на ней, возможность откомпилировать один и тот же исходный код на одной и той же платформе Windows двумя разными компиляторами (Microsoft Visual C++ и GCC/Win32) гарантирует лучшее качество исходного кода и лучшую его совместимость со стандартом C++. Что немаловажно для кода, который планируется длительно поддерживать и развивать.

2.3 Краткое описание используемых пространств имен и классов

Класс QWidget - это базовый класс для всех объектов пользовательского интерфейса. Виджет - элементарный объект пользовательского интерфейса. Он получает события мыши, клавиатуры и другие события от оконной системы и рисует свое изображение на экране. Виджет имеет прямоугольную форму, и отрисовка происходит в порядке наложения.

Класс QMainWindow представляет собой главное оконное приложение. Главное окно предоставляет структуру для создания пользовательского интерфейса приложения. QMainWindow имеет собственный компоновщик. Компоновщик имеет центральную область, которая может быть занята любым виджетом.

Класс QPainter выполняет низкоуровневое рисование на виджетах и других устройствах рисования. QPainter содержит высокооптимизированные функции, позволяющие выполнить большинство рисунков, требуемых с GUI.

3.РЕАЛИЗАЦИЯ ПРОГРАММНОГО МОДУЛЯ

3.1 Файлы программного модуля Beta

Для реализации программного модуля используются заголовочные файлы “graph.h”, “MainWindow.h” и исходники “MainWindow.cpp”,”main.cpp”.

Заголовочный файл “graph.h”.

В этом заголовочном файле описаны структура представления графа и функции его обработки. Структура DescG представляет собой дескриптор графа. DescV - дескриптор вершины. DescIn и DescOut - дескрипторы входа и выхода. DescAr - дескриптор дуги. SupportInOutArc, SupportArcOut, SupportArcIn - это вспомогательные структуры для оптимизации связи вершин и дуг.

Класс “MainWindow”

В заголовочном файле “MainWindow.h” объявляется класс QMainWindow. В нем объъявляются методы, которые созданы в “MainWindow.cpp”. Также были объявлены 5 глобальных переменных: VCoor и VCoorL типа VertCoor, g1 и g1 типа descG, и логическая переменная f. Переменная VCoorL указывает на первую вершину списка VCoor. VCoor это список вершин графа, параметром которых являются их имя, номер и координаты. g1 и g2 это ссылки на графы, которые программа будет рисовать.

В исходнике “MainWindow.cpp” описан весь алгоритм работы программного модуля.

В методе PaintEvent описан алгоритм обработки и рисования графа.

QLinearGradient lg = QLinearGradient(QPointF(0,0),QPointF(0,1));

lg.setCoordinateMode(QGradient::ObjectBoundingMode );

lg.setSpread(QGradient::PadSpread);

lg.setColorAt(0.0,Qt::green);

lg.setColorAt(1.0,Qt::red);

QBrush brush = QBrush(lg);

QPainter painter(this);

painter.setBrush(brush);

QPen p2;

p2.setBrush(brush);

p2.setWidth(2);

В этой части кода устанавливаются цвет линии, которой будут нарисованы дуги. В этом случае цветом дуги будет градация цвета от зеленого к красному. Это сделано для того, чтобы можно было обозначить, из какой вершины дуга выходит, и в какую входит. Зеленым цветом обозначается часть дуги, выходящая из вершины, а красным цветом часть, которая входит в смежную с ней вершину. Полностью красным цвет дуги будет в том случае, если дуга является двунаправленной.

if (f)

{

int aK=0;

int x=this->width()/2;

int y=this->height()/2;

double pi=3.14;

struct VertCoor* VCoor3;

VCoor=(struct VertCoor*)malloc(sizeof(struct VertCoor));

VCoor->X=(int)(x+120*cos(aK*pi/180));

VCoor->Y=(int)(y-120*sin(aK*pi/180));

VCoor->sign=VList->sign;

VCoor->type=VList->name;

VCoorL=VCoor;

aK=aK+360/(n+1);

VList=VList->next;

for (int i=0;i!=n;i++)

{

VCoor3=(struct VertCoor*)malloc(sizeof(struct VertCoor));

VCoor3->sign=VList->sign;

VCoor3->type=VList->name;

VCoor3->X=(int)(x+120*cos(aK*pi/180));

VCoor3->Y=(int)(y-120*sin(aK*pi/180));

VCoor->next=VCoor3;

VCoor=VCoor3;

VList=VList->next;

aK=aK+360/(n+1);

}

VCoor->next=NULL;

}

В этой части программного кода реализован алгоритм поиска оптимальных координат для вершин, запись этих координат в параметры вершин списка VCoor и запись имени соответствующей вершины.

Алгоритм построения изображения сводится к алгоритму построения правильного n-угольника. В правильном многоугольнике все углы равны, значит надо 360 градусов поделить на n углов n-угольника. Получим внутренний угол многоугольника. Далее для нахождения координат определенных вершин используем формулу окружности. Для того чтобы получить координату, нужно перевести градусы в радианы. Для этого угол мы умножаем на число Пи, и делим на 180 градусов.

В цикле мы движемся по списку вершин, находящемуся в структуре дескриптора графа, и пока не доходим до конца, каждой вершине присваиваем координаты следующей точки на окружности (из n точек), конвертируя их в целочисленный тип.

Этот алгоритм выполняется только при запуске программы. Дальше его не зачем повторять, потому что все значения хранятся в глобальной переменной, и чтобы можно было отрисовывать граф заново с измененными значениями координат.

struct descV* vert2;

vert2=g1->LVert;

while (vert2!=NULL)

{

struct SupportInOutArc* ALIST2 = vert2->LOut->LArc;

while (ALIST2!=NULL)

{

sign1=ALIST2->arch->LOut->Out->vert->sign;

VCoor=VCoorL;

while (VCoor!=NULL)

{

if (VCoor->sign == sign1 )

{

x1=VCoor->X;

y1=VCoor->Y;

n1=sign1;

}

VCoor=VCoor->next;

}

sign1=ALIST2->arch->LIn->In->vert->sign;

VCoor=VCoorL;

while (VCoor!=NULL)

{

if (VCoor->sign==sign1 )

{

x2=VCoor->X;

y2=VCoor->Y;

n2=sign1;

}

VCoor=VCoor->next;

}

painter.drawLine(x1,y1,x2,y2);

ALIST2 = ALIST2->next;

}

vert2 = vert2->next;

}

В этой части кода происходит обход всех вершин в цикле, поиск выходящий из нее дуг, и далее в цикле происходит поиск координат вершин, соответствующих входу и выходу дуги. В этих координатах, соответственно от выхода к входу, рисуется линия методом drawLine.

QPainter p3(this);

QBrush brush1 = QBrush(Qt::darkCyan,Qt::SolidPattern);

p3.setBrush(brush1);

VCoor=VCoorL;

while (VCoor!=NULL)

{

p3.drawRect(VCoor->X-15,VCoor->Y-15,30,30);

VCoor=VCoor->next;

}

QPainter p4(this);

QPen penB2(Qt::white);

p4.setPen(penB2);

p4.setFont(QFont("Times", 14));

VCoor=VCoorL;

while (VCoor!=NULL)

{

QString text=(QString)VCoor->type;

p4.drawText(VCoor->X-8,VCoor->Y+8,text);

VCoor=VCoor->next;

}

}

Далее на координатах вершин рисуются прямоугольники, в которых будут записаны имена соответствующих вершин.

В методе StartDraw() происходит создание графа, который будет рисовать программный модуль.

Метод Grab() получает скриншот изображения окна виждета с нарисованным графом и сохраняет его в память компьютера под именем screen.jpg.

В методе keyPressEvent() описываются клавиши клавиатуры, при нажатии на которые вызываются соответствующие методы.

При нажатии на клавишу W вызывается метод zoomIn(2), который увеличивает значения координат вершин в два раза, тем самым увеличивая в два раза изображение, которое мы в итоге получаем.

При нажатии на клавишу S вызывается метод zoomOut(2), который описанным выше методом уменьшает координаты и изображение в два раза.

При нажатии на клавишу Up вызывается метод moveUp(10), в котором координаты по оси y увеличиваются на 10, тем самым передвигая изображение вверх.

При нажатии Down изображение методом moveDown(10) аналогичным образом смещается вниз.

При нажатии Right и Left вызываются соответственно методы moveRight(10) и moveLeft(10), которые увеличивают и уменьшают координаты по оси х на 10, тем самым сдвигая изображения вправо и влево.

При нажатии на клавишу Escape программа закрывается вызовом метода Close().

Файл “main.cpp”.

В этом файле создается экземпляр w класса MainWindow. Затем вызывается метод этого класса StartDraw() и создается граф. Далее методом show() создается виджет и происходит реализация алгоритма рисования. После вызывается метод Grab() и изображение графа сохраняется в память компьютера. Также была реализована версия модуля, специально для использования под Веб-интерфейс, которая автоматически закрывает приложение методом Close().

3.2 Пример работы программного модуля

Для примера выведем по очереди два ориентированных графа. Изображение графа мы получаем сразу при запуске программы (рис.2).Как ранее и описывалось, зеленый цвет дуги обозначает выход из вершины, а красный вход. Полностью красная дуга С-B означает, что эта дуга двунаправленная. Имена вершин записаны в прямоугольных областях.

Рисунок 2 - запуск программы

Рисунок 3 - сдвиг в нижнюю левую часть

Далее показано изменение положения графа в окне виджета. На рисунке 3 показано передвижение графа в нижнюю левую часть окна. На рисунке 4 - в верхнюю правую часть окна. На рисунке 5 показано увеличение изображения графа, для более удобного и подробного изучения более больших структур.

Рисунок 4 - сдвиг в правую верхнюю часть

Рисунок 5 - увеличение изображения

На рисунке 6 показаны изображения двух графов, взятых для примера. Второй граф, взятый для примера, имеет 10 вершин и состоит из двух частей.

Выход из программы осуществляется при нажатии клавиши Escape.

Рисунок 6 - изображение двух графов

3.3 Подключение программного модуля к Веб-странице.

Главной веб-страницей является файл “indexOh.html”. В нем описаны переходы по двум ссылкам. Первая это ссылка на страницу “Oh.php”, где реализуется алгоритм вызова выполнения программного модуля на стороне сервера. Вторая ссылка на страницу “index.html”, куда будет загружаться изображение с результатом работы программы.

На рисунке 7 показано окно страницы “indexOh.html”.

Рисунок 7 - indexOh.html

При нажатии на ссылку «Нажмите на эту ссылку для выполнения программы» программа запускается на стороне сервера, сохраняет изображение графа на сервере и автоматически закрывается. При нажатии на ссылку «Здесь результат!» мы переходим на страницу “index.html”,показанную на рисунке 8, и видим результат выполнения программы.

Также изображение графа сохраняется в памяти компьютера, и его можно использовать для дальнейших работ.

Рисунок 8 - страница index.html с результатом

ЗАКЛЮЧЕНИЕ

Разработан программный модуль, который получая на входе ссылку на граф, используя методы из прилагаемого модуля, выводит изображение графа на экран и сохраняет это изображение в память компьютера. Можно использовать разные модули реализации графа (с одинаковыми наименованиями структур и методов). Изображением можно управлять, сдвигая вверх, вниз, вправо, влево, а также увеличивая и уменьшая. Это способствует более удобному изучению изображения структуры. Также этот программный модуль был подключен в Веб-странице, что позволяет через веб-интерфейс запускать программу и получать результат. Программа исполняет свое задание верно.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Шеннон Р. Имитационное моделирование систем: искусство и наука. - М.: Мир, 1978. -- 302 с.

2. Майер Р.В. Компьютерное моделирование. Электронная конференция. URL: http://econf.rae.ru/article/6722 (дата обращения 5.06.2014)

3. Кудинов Ю.И., Пащенко Ф.Ф. Основы современной информатики. - 2-е изд. испр. - М.: Издательство "Лань", 2011.

4. Макарова Н.В., Волков В.Б. Информатика: Учебник для вузов. - СПб.: Питер, 2011.

5. Описание класса QPainter. URL: http://qtdocs.narod.ru/4.1.0/doc/html/qpainter.html#details (дата обращения 5.05.2014)

6. Описание класса QWidget. URL: http://doc.crossplatform.ru/qt/4.5.0/qwidget.html (дата обращения 26.04.2014)

7. Макс Шлее: Qt 4.8. Профессиональное программирование на C++//-- СПб.: БХВ-Петербург, 2012. -- 912 с.: ил. -- (В подлиннике)

ПРИЛОЖЕНИЕ А

Описание программы.

1. Общие сведения.

Данная программа реализована на языке С++. Основные файлы исходного кода программ: graph.h, mainwindow.h, mainwindow.cpp, main.cpp. Для ее реализации использовались: библиотеки Qt, среда разработки Qt Creator, операционная система Linux, веб-сервер Apache.

2. Функциональное назначение.

Программа визуализирует компьютерную структуру в виде графа. Изображение можно передвигать, увеличивать и уменьшать для более удобного изучения изображения структуры. Изображение сохраняется в памяти компьютера. Так же программа может выполняться с веб-страницы на стороне сервера и выводить изображение с результатом на веб-страницу.

Программный модуль является составным компонентом системы моделирования, cоздающейся в рамках проекта «Разработка и реализация информационно-аналитической среды, предназначенной для исследования и проектирования информационно-коммуникационных систем» Программы развития КубГУ.

3. Описание логической структуры.

В файле graph.h описаны методы реализации графа, представленного совокупностью дескрипторов. Для представления графа в виде связанных дескрипторов понадобилось 8 структур: 5 для дескрипторов и 3 вспомогательных. Структура DescG представляет собой дескриптор графа. DescV - дескриптор вершины. DescIn и DescOut - дескрипторы входа и выхода. DescAr - дескриптор дуги. SupportInOutArc, SupportArcOut, SupportArcIn - это вспомогательные структуры для оптимизации связи вершин и дуг.

В классе “MainWindow” описан весь алгоритм работы программного модуля.

В методе PaintEvent описан алгоритм обработки и рисования графа. Граф отрисовывается методами drawLine, drawRect и drawText. Сначала рисуются дуги графа. Зеленым цветом обозначен выход дуги, красным вход. Полностью красная дуга означает, что она двунаправленная. Далее рисуются прямоугольники, означающие вершины. В прямоугольниках записаны имена вершин.

В методе StartDraw() происходит создание графа, который будет рисовать программный модуль.

Метод Grab() получает скриншот изображения окна виждета с нарисованным графом и сохраняет его в память компьютера под именем screen.jpg.

В методе keyPressEvent() описываются клавиши клавиатуры, при нажатии на которые вызываются соответствующие методы.

При нажатии на клавишу W вызывается метод zoomIn(2), который увеличивает значения координат вершин в два раза, тем самым увеличивая в два раза изображение, которое мы в итоге получаем.

При нажатии на клавишу S вызывается метод zoomOut(2), который описанным выше методом уменьшает координаты и изображение в два раза.

При нажатии на клавишу Up вызывается метод moveUp(10), в котором координаты по оси y увеличиваются на 10, тем самым передвигая изображение вверх.

При нажатии Down изображение методом moveDown(10) аналогичным образом смещается вниз.

При нажатии Right и Left вызываются соответственно методы moveRight(10) и moveLeft(10), которые увеличивают и уменьшают координаты по оси х на 10, тем самым сдвигая изображения вправо и влево.

При нажатии на клавишу Escape программа закрывается вызовом метода Close().

В файле “main.cpp” создается экземпляр w класса MainWindow. Затем вызывается метод этого класса StartDraw() и создается граф. Далее методом show() создается виджет и происходит реализация алгоритма рисования. После вызывается метод Grab() и изображение графа сохраняется в память компьютера. Также была реализована версия модуля, специально для использования под Веб-интерфейс, которая автоматически закрывает приложение методом Close().

Файл “indexOh.html” является главной веб-страницей. В нем описаны переходы по двум ссылкам. Первая это ссылка на страницу “Oh.php”, где реализуется алгоритм вызова выполнения программного модуля на стороне сервера. Вторая ссылка на страницу “index.html”, куда будет загружаться изображение с результатом работы программы.

4. Используемые технические средства.

Среда разработки Qt Creator, классы и методы Qt, веб-сервер Apache, операционная система Linux.

5. Вызов и загрузка.

Вызов приложения происходит через файл Beta. Открытие главной веб-страницы происходит через файл indexOh.html.

6. Входные данные.

Ссылка на граф.

7. Выходные данные.

Изображение графа в окне виджета. Сохраненное изображение в память компьютера. Веб-страница с изображением графа.

ПРИЛОЖЕНИЕ Б

Пояснительная записка.

Введение.

Программный модуль Beta получает ссылку на граф и выводит его изображение на экран. Изображение сохраняется в память компьютера. Программный модуль может выполняться на стороне сервера при вызове с веб-страницы, и помещать результат на веб-страницу.

1. Назначение и область применения.

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

Программа является одним из модулей библиотеки транслятора языка моделирования, предназначенного для проведения исследований в области информационных процессов и систем в рамках проекта «Разработка и реализация информационно-аналитической среды, предназначенной для исследования и проектирования информационно-коммуникационных систем» Программы развития КубГУ.

2. Технические характеристики.

Программа написана на языке С++ в среде разработки Qt Creator под операционную систему Linux.

В файле graph.h описаны методы реализации графа, представленного совокупностью дескрипторов. Для представления графа в виде связанных дескрипторов понадобилось 8 структур: 5 для дескрипторов и 3 вспомогательных. Структура DescG представляет собой дескриптор графа. DescV - дескриптор вершины. DescIn и DescOut - дескрипторы входа и выхода. DescAr - дескриптор дуги. SupportInOutArc, SupportArcOut, SupportArcIn - это вспомогательные структуры для оптимизации связи вершин и дуг.

В классе “MainWindow” описан весь алгоритм работы программного модуля.

В методе PaintEvent описан алгоритм обработки и рисования графа. Граф отрисовывается методами drawLine, drawRect и drawText. Сначала рисуются дуги графа. Зеленым цветом обозначен выход дуги, красным вход. Полностью красная дуга означает, что она двунаправленная. Далее рисуются прямоугольники, означающие вершины. В прямоугольниках записаны имена вершин.

В методе StartDraw() происходит создание графа, который будет рисовать программный модуль.

Метод Grab() получает скриншот изображения окна виждета с нарисованным графом и сохраняет его в память компьютера под именем screen.jpg.

В методе keyPressEvent() описываются клавиши клавиатуры, при нажатии на которые вызываются соответствующие методы.

При нажатии на клавишу W вызывается метод zoomIn(2), который увеличивает значения координат вершин в два раза, тем самым увеличивая в два раза изображение, которое мы в итоге получаем.

При нажатии на клавишу S вызывается метод zoomOut(2), который описанным выше методом уменьшает координаты и изображение в два раза.

При нажатии на клавишу Up вызывается метод moveUp(10), в котором координаты по оси y увеличиваются на 10, тем самым передвигая изображение вверх.

При нажатии Down изображение методом moveDown(10) аналогичным образом смещается вниз.

При нажатии Right и Left вызываются соответственно методы moveRight(10) и moveLeft(10), которые увеличивают и уменьшают координаты по оси х на 10, тем самым сдвигая изображения вправо и влево.

При нажатии на клавишу Escape программа закрывается вызовом метода Close().

В файле “main.cpp” создается экземпляр w класса MainWindow. Затем вызывается метод этого класса StartDraw() и создается граф. Далее методом show() создается виджет и происходит реализация алгоритма рисования. После вызывается метод Grab() и изображение графа сохраняется в память компьютера. Также была реализована версия модуля, специально для использования под Веб-интерфейс, которая автоматически закрывает приложение методом Close().

Файл “indexOh.html” является главной веб-страницей. В нем описаны переходы по двум ссылкам. Первая это ссылка на страницу “Oh.php”, где реализуется алгоритм вызова выполнения программного модуля на стороне сервера. Вторая ссылка на страницу “index.html”, куда будет загружаться изображение с результатом работы программы.

3. Технико-экономические показатели.

Данная программа поможет более наглядно анализировать граф. Также с помощью нее можно работать со структурой компьютера, проводить нужные изменения, и их можно будет анализировать по полученному изображению.

ПРИЛОЖЕНИЕ В

Код программы.

Файл “graph.h”.

#ifndef GRAPH_H

#define GRAPH_H

#include <iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<string.h>

#define N 10

#pragma once

struct VertCoor

{

struct VertCoor* next;

int sign;

char* type;

int X;

int Y;

};

struct SupportGraph // ??????????????? ??????? ?????????? ??????

{

struct SupportGraph* next;

struct descV* vert;

struct descAr* arch;

};

struct list

{

char* name;

struct list* next;

};

struct id

{

char* name;

int ntype;

int val;

};

struct id* ident[20];

struct descG {

int sign;

struct descG* next;

struct descG* prev;

int uid;

char* name;

char* pname;

int type;

int arn;

int VertNum;

struct descV* LVert;

int ArchNum;

struct descAr* LArch;

int GInNum;

struct descV* GIn;

int GOutNum;

struct descV* GOut;

};

struct descV {

int sign;

struct descV* next;

struct descV* prev;

int uid;

char* name;

char* pname;

char type;

struct descG* graph;

int InNum;

struct descIn* LIn;

int OutNum;

struct descOut* LOut;

int ConnectPr;

};

struct descIn {

int sign;

struct descIn* next;

struct descIn* prev;

int uid;

char* name;

char* pname;

char type;

int ArchNum;

struct SupportInOutArc* LArc;

int ConnectPr;

struct descV* vert;

};

struct descOut {

int sign;

struct descOut* next;

struct descOut* prev;

int uid;

char* name;

char* pname;

char type;

int ArchNum;

struct SupportInOutArc* LArc;

int ConnectPr;

struct descV* vert;

};

struct descAr {

int sign;

struct descAr* next;

struct descAr* prev;

int uid;

char* name;

char* pname;

char type;

int arn;

int InNum;

struct SupportArcIn* LIn;

int OutNum;

struct SupportArcOut* LOut;

};

// supporting elements

struct SupportInOutArc

{ struct SupportInOutArc* next;

struct descAr* arch;

};

struct SupportArcOut

{ struct SupportArcOut* next;

struct descOut* Out;

};

struct SupportArcIn

{ struct SupportArcIn* next;

struct descIn* In;

};

void Soed (struct descV* p1, struct descV* p2,struct descAr* dd);

struct descG* Graph (struct descG* g,struct list* listing, int m1, int m2, int f);

struct list* sp;

int i,j,u;

struct descG *G;

struct descV *a,*b,*pt,*p,*q,*l;

struct descIn *Vx, *Vxq, *Vxl;

struct descOut *Vi, *Viq, *Vil;

struct descAr *d, *dq, *dl;

struct SupportInOutArc *WD, *WDq, *WDl, WDlp;

struct SupportArcIn *WVx, *WVxq, *WVxl;

struct SupportArcOut *WVi, *WViq, *Wvil;

char ab[10];

char *a1;

char *a2;

int n;

char* stringcopy(char* str,int pos1,int pos2)

{

char* s;

int i=pos1;

int j=0;

s=(char*) malloc(1000*sizeof(char));

while (i!=pos2)

{

s[j]=str[i];

i=i+1 ; j=j+1;

}

s[j]='\0';

return s;

}

void Soed (struct descV* p1, struct descV* p2,struct descAr* dd)

{

char* c;

c=stringcopy(p1->name,0,strlen(p1->name));

for (i=0;i<strlen(p1->name);i++)

c[i+strlen(p1->name)]=p2->name[i];

c[strlen(p1->name)+strlen(p2->name)]='\0';

dq=(struct descAr*)malloc(sizeof(struct descAr));

dq->next=NULL;

dq->prev=NULL;

dq->arn=2;

dq->OutNum=1;

dq->InNum=1;

dq->name=stringcopy(c,0,strlen(c));

WVxq=(struct SupportArcIn*)malloc(sizeof(struct SupportArcIn));

WViq=(struct SupportArcOut*)malloc(sizeof(struct SupportArcOut));

WVxq->next=NULL;

WVxq->In=p2->LIn;

WViq->next=NULL;

WViq->Out=p1->LOut;

dq->LIn=WVxq;

dq->LOut=WViq;

dd->next=dq;

dq->prev=dd;

dd=dq;

WDq=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));

WDq->next=NULL;

WDq->arch=dd;

if (p1->LOut->LArc!=NULL) {WDl=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));WDl=p1->LOut->LArc;}

if (p1->LOut->LArc==NULL)

{

p1->LOut->LArc=WDq;

WDl=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));

WDl=p1->LOut->LArc;

}

else

{

while (p1->LOut->LArc->next!=NULL) {p1->LOut->LArc=p1->LOut->LArc->next;}

p1->LOut->LArc->next=WDq;

p1->LOut->LArc=WDl;

}

WDq=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));

WDq->next=NULL;

WDq->arch=dd;

if (p2->LIn->LArc!=NULL) {WDl=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));WDl=p2->LIn->LArc;}

if (p2->LIn->LArc==NULL)

{

p2->LIn->LArc=WDq;

WDl=(struct SupportInOutArc*)malloc(sizeof(struct SupportInOutArc));

WDl=p2->LIn->LArc;

}

else

{

while (p2->LIn->LArc->next!=NULL) {p2->LIn->LArc=p2->LIn->LArc->next;}

p2->LIn->LArc->next=WDq;

p2->LIn->LArc=WDl;

}

if (p1->graph->type!=4) p1->graph->type=4;

if (p1->graph->LArch==NULL) p1->graph->LArch=dd;

}

struct list* InNames1()

{

struct list* im;

struct list* l1;

struct list* l2;

l1=(struct list*) malloc(sizeof(struct list));

l1->name="a";

im=(struct list*) malloc(sizeof(struct list));

im->next=l1;

im->name="Svyazi";

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="b";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="c";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="d";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="e";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="f";

l2->next=NULL;

return im;

}

struct list* InNames2()

{

struct list* im;

struct list* l1;

struct list* l2;

l1=(struct list*) malloc(sizeof(struct list));

l1->name="a1";

im=(struct list*) malloc(sizeof(struct list));

im->next=l1;

im->name="Pustota";

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="a2";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="a3";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="a4";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="a5";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="a6";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="b1";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="b2";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="b3";

l1=l2;

l2=(struct list*) malloc(sizeof(struct list));

l1->next=l2;

l2->name="b4";

l2->next=NULL;

return im;

}

void Odin(struct descG* g,struct descAr* d)

{

int i;

struct descV* p;

struct descV* pv;

p=g->LVert;

pv=p;

for(i=1;i<=5;i++)

{

pv=pv->next;

Soed(p,pv,d);

d=d->next;

p=p->next;

}

p=p->prev->prev;

Soed(pv,p,d);

d=d->next;

pv=g->LVert->next;

Soed(pv,p,d);

}

void Dva(struct descG* g,struct descAr* d)

{

int i;

struct descV* p;

struct descV* pv;

p=g->LVert;

pv=p;

for (i=1;i<=5;i++)

{

pv=pv->next;

Soed(p,pv,d);

d=d->next;

}

p=pv->next;

pv=p->next;

for (i=1;i<=3;i++)

{

Soed(p,pv,d);

d=d->next;

p=p->next;

pv=pv->next;

}

pv=p->prev->prev->prev;

Soed(p,pv,d);

}

struct descG* Graph (struct descG* G,struct list* listing, int m1, int m2, int f )

{

sp=listing;

G->sign=4;

G->type=0;

n=m1+m2;

G->name=stringcopy(sp->name,0,strlen(sp->name));

sp=sp->next;

printf(" Struct name : %s \n",G->name);

printf(" Look at the struct : \n");

G->arn=1;

G->VertNum=n;

G->LVert=NULL;

for (i=1; i<=n; i++)

{

if (sp==NULL) break;

if (i==1)

{

p=(struct descV*)malloc(sizeof(struct descV));

p->prev=NULL;

p->next=NULL;

p->InNum=1;

p->OutNum=1;

p->graph=G;

p->name=stringcopy(sp->name,0,strlen(sp->name));

sp=sp->next;

Vi=(struct descOut*)malloc(sizeof(struct descOut));

Vi->next=NULL;

Vi->prev=NULL;

Vi->name=stringcopy(p->name,0,strlen(p->name));

Vi->vert=p;

Vi->LArc=NULL;

Vil=Vi;

Vx=(struct descIn*)malloc(sizeof(struct descIn));

Vx->next=NULL;

Vx->prev=NULL;

Vx->name=stringcopy(p->name,0,strlen(p->name));

Vx->vert=p;

Vx->LArc=NULL;

Vxl=Vx;

p->LIn=Vx;

p->LOut=Vi;

l=p;

G->LVert=p;

}

else

{

q=(struct descV*) malloc(sizeof(struct descV));

q->name=stringcopy(sp->name,0,strlen(sp->name));

sp=sp->next;

q->next=NULL;

q->prev=NULL;

q->InNum=1;

q->OutNum=1;