Лабораторная работа № 3 Построение объектно-ориентированного приложения

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

Шаблоны проектирования

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

http://ru.wikipedia.org/wiki/Шаблоны_проектирования

http://www.proklondike.com/file/Java/Stelting_Maasen_-_Primenenie_Shablonov_Java.rar

Библиотека Jung

Задания с использованием широко известной библиотеки Jung (Java Universal Network/Graph Framework) базируются на знаниях теории графов, полученных студентом в курсе «Дискретная математика». Учитывая отсутствие документации на русском языке ниже описаны основные возможности библиотеки Jung с указанием классов их реализующими. Документация и примеры предоставлены в электронном виде.

Средства визуализации

Библиотека JUNG предоставляет набор классов, предназначенных для инкапсуляции процесса визуализации графов и для удобства разработки, реализованных в виде трехуровневой архитектуры:

• Классы, отвечающие за внутреннее представление графа в системе. В качестве примера реализации ориентированных и неориентированных графов, в системе реализованы классы DirectedSparseGraph и UndirectedSparseGraph.

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

• Классы, отвечающие за непосредственное рисование объектов графа, таких как вершины, ребра и текстовые метки. Например, достаточно гибко настраиваемый PluggableRenderer.

Некоторые возможности средств разработки

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

Мышь

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

• Редактирования (Editing), позволяющим добавлять и удалять новые ребра и вершины.

• Переноса (Picking), позволяющим изменять положение вершины или группы вершин.

• Преобразования (Transforming), в котором возможно применение преобразований ко всему графу целиком, в частности – вращение, растяжение вдоль оси и параллельный перенос.

UserData

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

Структурированная работа с объектами

JUNG включает в себя некоторое количество удобных классов, которые представляют собой пример реализации структурированной работы с объектами графа. Они реализованы в рамках пакета graph.decorators. Например:

• Класс Indexer содержит методы, позволяющие создавать отображения между вершинами графа и целыми числами {0, 1, ... n-1}, где n – количество вершин в графе. Это позволяет работать с множествами вершин как с упорядоченными массивами.

• Класс StringLabeller позволяет “прикреплять” к вершинам строковые метки к вершинам графа.

Предикаты

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

Алгоритмы

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

• Операции над Графом/Матрицей

Матрицы являются одним из наиболее распространенных представлений графовых данных. GraphMatrixOperations состоит из двух классов операций: первый непосредственно реализует операции над матрицами, а второй класс представляет собой операции, включенные в CERN Colt package для вычислительных операций над матрицами.

• Кластеризация

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

• BicomponentClusterer: Находит все двусвязные графы в неориентированном графе g, где двусвязный граф определен как максимальный индуцированный двусвязный подграф графа g

• EdgeBetweennessClusterer: Вычисляет кластеры для графа, основанные на усредненном свойстве ребер

• WeakComponentClusterer: Находит все слабые компоненты в графе g, где под слабой компонентой понимается максимально слабосвязанный подграф графа g

• Топология, пути и потоки

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

• BFSDistanceLabeler: Помечает каждую вершину в графе длинной кратчайшего невзвешенного пути от определенной вершины в графе

• KNeighborhoodExtractor: Возвращает подграф графа, чьи вершины разделены не более чем k ребрами от определенной вершины в графе

• DijkstraShortestPath: Помечает каждую вершину в графе длинной кратчайшего взвешенного пути от определенной вершины в этом графе

• UnweightedShortestPath: Вычисляет кратчайший путь для невзвешенного графа