УДК 681.3
М.Ю. КРУКОВСКИЙ
Язык обработки графов на базе JAVA.
Abstract: This paperdescribes a language for definition of wokflow processes. As a core for thelanguage was used graph model. This language was involved in creation ofsystem for workflow processes developing and execution
Key words:docflow,workflow, graph model, JAVA.
Анотація: У статті розглянутамова, що дає можливістьописувати процеси композитногодокументообігу. Основою для мови була використана графова модельдокументообігу. Мови використовувалась для створення системи проективання тавиконання процесів документообігу.
Ключові слова: електроннийдокументообіг, процесне керування, графова модель, JAVA.
Аннотация: В статье рассмотрен язык, позволяющийописывать процессы композитного документооборота. Основой для языка послужилаграфовая модель документооборта. Язык использован для создания системыпроектирования и исполнения процессов документооборота.
Ключевые слова: электронныйдокументооборот, процессное управление, графовая модель, JAVA.
1.Введение
Формальный синтаксис и неформальная семантикаопределяют основные свойства существующих языков программирования. Языки исистемы программирования подчинены общим законам эволюции [1]. Эволюция языковпрограммирования прошла через парадигмы, которые в момент внедрения считалисьглубоко продуманными и устойчивыми. Такие парадигмы языков, как: процедурные,модульные, обьектно — ориентированные в свое время считалась едва ли непанацеей для всех задач. На сегодняшний день стало очевидно, что значимымявляется не только синтаксис или форма отображения грамматик, а прикладноезначение языка.
В рамках настоящей статьи будет рассмотренорасширение языка JAVA, которое позволяет оперироватьграфами на уровне языковых конструкций. Автор пришел к необходимости даннойразработки в процессе работы над реализацией системы композитногодокументооборота [2], основой которой выступает графовая модель [3].Разработанное расширение распространяется с открытым кодом и может бытьиспользовано для решения прикладных задач, оперирующих аппаратом теории графов.
2. Постановка проблемы
Для решения задачи предполагается расширить языкJAVA таким образом, чтобы с помощью этого расширенногоязыка можно было описывать и решать задачи документооборота, используяестественные для документооборота понятия и определения. В качестве основной моделипредполагается использовать графовую модель, введенную автором настоящей статьив работе [3]. Таким образом, задача создания языка документооборота сводится кзадаче расширения JAVA возможностями работы с графами инаполнения этого языка семантикой документооборота.
Теория графовсегодня является очень важным и полезным аппаратом дискретнойматематики. Она широко применяется при решении, как теоретических вопросов, таки в практических инженерных задачах. Особенно много применений теория графовнашла при решении таких задач, как автоматизированный контроль, сетевоепланирование и проектирование интегральных схем. Кроме этих задач, очень широкографы применяются при создании моделей различного взаимодействия. Интереснымявляется факт, что графы используются не только в перечисленных, достаточнодетерминированных задачах, но и в гуманитарных науках, таких как эпидемиологияи лингвистика [4].
Необходимо отметить, что предлагаемый языкпрограммирования, позволяющий обрабатывать графы, будет полезным многимпрограммистам и востребован для решения широкого круга самых разнообразныхзадач. Основным достоинством предлагаемого языка является то, что он позволяетпрограммисту оперировать графами, используя знакомый и привычныйинструментарий. Основой для такого прикладного языка, реализующего работу сграфами, целесообразно выбрать уже существующий широко используемый для общихприкладных задач язык программирования. На сегодняшний день такой платформойявляется доминирующий, практически без альтернативы, при разработке локальных ираспределенных приложений язык JAVA. Помимо этого язык JAVA хорошо приспособлен для решения задач сетевоговзаимодействия.
2.1. Состояние проблемы
Работы по разработке языков программирования,оперирующих понятиями теории графов, ведутся с семидесятых годов прошлогостолетия. Каждый из полученных языков использовался для решения прикладныхзадач и являлся расширением языка программирования, наиболее широкоиспользуемого на то время.
Одним из первых появился язык GEA(Graph Extended Algol), которыйбыл разработан в 1970 на базе системы Univac 1108 ииспользовался в течении десятилетия в университетских вычислительных центрах[5]. Основным достоинством языка являлось то, что при своей простотереализации, он позволял решать задачи обработки графов, использую базовыенавыки программирования. Существенным недостатком этой разработки былонепродуманное прикладное применение, что обусловило узкий круг использования.Широко использовался для прикладных задач язык GRASPE, построенный на базе библиотекязыка LISP [6]. Название языка LISP(Лисп) происходит от list processing (обработка списков). Он широко используется взадачах символьной обработки, искусственного интеллекта, математическойлингвистике и других. Помимо этого язык LISP может бытьиспользован для построения графиков и задания чертежей. Но так как LISP оперирует списочными структурами, то его реализацияпозволила не только функционального оперировать графами, но и их визуализации[7].
Впоследствии предпринималисьпопытки создания универсального языка, который бы заложил долгосрочную базу подбудущие языки обработки графов. Один из таких языков – GXL(Graph Transformation Languge), построенный на базесуществовавшего, на тот момент, математического языка обработки деревьев TXL (Tree transformation language)[8]. Язык был хорошо проработан с математической точки зрения, что безусловнообеспечивало самые широкие возможности для обработки графов. В то же время,недостаточно было проработано его стыковка с языкамипрограммирования, что сделало этот язык известным только в кругу узкихспециалистов. Другое семейство языков, GBL (Graph Based Language), построенно в виде наборасемантических определений и правил языковых цепочек с применением аппарататеории формальных языков [9]. Такой подход обеспечил невиданную до этогообщность описаний. Но, вследствие недостаточной очевидности практической пользыприменения, конкретных программных реализаций, основанных на этом языке, оностался невостребованным.
Таким образом, задача созданиярасширения языка программирования, оперирующего с графами, имеет достаточнопроработанную и апробированную базу. В то же время реализаций такого языка набазе самого распространенного сейчас языка JAVA наданный момент автору неизвестно. Наиболее близкая к рассматриваемой в статьезадаче — это разработанный на базе JAVA язык дляиерархического моделирования и воспроизведения систем HiMASS-j (Hierarchical Modeling And Simulation System – Java) [10].
2.2. Выбор инструментария
Для решения поставленной вышезадачи целесообразно использовать модификацию языка JAVAдля реализации сложных приложений распределенных предприятий J2EE (JAVA 2 Enterprise Edition). Следует сказать, что язык J2EE делает упор не на библиотеки, ана набор связанных спецификаций и рекомендаций, которые собраны вместе дляпостроения многоуровневых кроссплатформенных приложений. В данном контексте подспецификациями понимаются стандартизованные данные и методы их обработки,которые включены в платформу. При этом рекомендации представляют собой примерыреализаций по определенным предметным областям в соответствии со спецификой иособенностями применения.
Выбор языка J2EE в качестве исходной базы связан с тем, что именно он и егоплатформа рассматривается разработчиками JAVA, какнаиболее перспективная среда проектирования и разработки распределенных JAVA приложений. Данная среда была специально модернизированадля поддержки современных требований для распределенных приложений.
3. Описание системы
Как уже отмечалось, язык GJEсделан в виде расширения к существующему и широко используемому языку JAVA. Автором предполагается, что сделанные на этом языкеприложения можно будет использовать во всех трех существующих реализацияхконечных приложений на JAVA, а именно – локальныхприложений Application, удаленно исполняемыхприложениях Applet и серверно- тиражируемых приложенияхServlet.
Технически язык GJEпредставляет собой внешнее расширение пакетов JAVA длярешения задач документооборота и описан как package javax.workflow. Это даетвозможность разработчиками подключать пакет и использовать его для решениязадач документооборота.
Язык GJE позволяетстроить модели документооборота, которые основаны на аппарате теории графов.Автором настоящей статьи в работе [3] введена графовая модель документооборота.Поэтому, при описании классов будет даваться не только общее назначение методови данных с точки зрения графа как математического понятия, но и применениясодержания классов, введенное в модели документооборота.
3.1. Описание интерфейсов языка GJE
Ниже приведено описание интерфейсов классов,являющихся основой языка GJE. Эти классы имеют тип “public”, поэтому они составляют основу построения конструкцийдокументооборота на языке JAVA. Выбранная открытостьреализации внешнего пакета обеспечивает возможность внесения модификаций в языкс учетом особенностей конкретных реализаций документооборота.
3.1.1. Класс Node
Класс Node представляет описаниеединицы нижнего уровня графа – вершины графа. Вершина графа является начальнымэлементом построения структуры, поэтому она не содержит методов, а содержиттолько значение, свойственное именно данной конкретной вершине. Как известно,совокупность вершин и их связи определяют граф.
В документообороте, множествувершин графа соответствует множество состояний документов, используемых вмоделируемом документообороте. Каждая отдельная вершина соответствуетотдельному состоянию документа, выделение которого считается целесообразным придискретизации процессов документооборота. Семантическими данными этого классаявляется содержательная часть документа. Такими данными могут быть текст, звук,видео и другие данные, которые могут быть задействованы в рамках используемыхоперационных систем и средств разработки.
При реализации документооборота, исходя изсвойств языка JAVA, класс может быть расширендополнительными методами обработки или данными. Такими данными может бытьинформация, которая не была известна на момент проектирования системы, аактуализировалась во время ее внедрения. Это дает возможность наращиватьсистему, при этом не нарушая основных правил.
Ниже приведен текст интерфейса класса Node.
package javax.workflow;
public interface Node
{
ObjectgetValue();
void setValue(Object value)throws InvalidOperation;
}
3.1.2. Класс Edge
Класс Edge используется дляописывания ребер графа. Ребро графа является базовым элементом аппарата теорииграфов и характеризуется тем, что соединяет одну или более вершин. Ребро можетбыть ненаправленным, то есть просто выступать элементом связности,упорядочивающим отношения между вершинами. Направленное ребро, кромеустановления факта связности, еще и определяет последовательность в иерархии,то есть указывает на причинно- следственную связь между вершинами.
В применении к графовой моделидокументооборота, введенной автором в работе [3], вершинаграфа ассоциируется с действием, которое производит участник документооборотанад документом. Если говорить более строго в терминах введенной модели, торебро графа, описывающего модель документооборота является действием,произведение которого вызывает смену состояния документа с начального напромежуточное либо конечное. Соответственно, входящей вершиной графа являетсявходящее для действия состояния документа. После произведения действия,установленного на ребре графа, документ принимает состояние, соответствующиеисходящей вершине графовой модели.
Класс Edgeсодержит методы getInPoint и getOutPoint, которыеиспользуются для получения входящих и исходящих вершин соответственно. МетодgetDirection получает данные, которые соотвествуют направленности ребра. МетодgetDirection имеет тип Object, поскольку направленности ребра могутсоответствовать не только собственно значение указания направленности, а иразличные весовые характеристики ребра. Метод setDirection используется дляпринудительного установления свойств направленности.
Методы getValue и setValueпредназначены для получения и установления дополнительных свойств ребра. Вприменении к задачами документооборота, это означает возможность введениедополнительной информации, свойственной действию. В частности, такойинформацией является информация об исполнителях документооборота, которые могутлибо должны производить это действие.
Ниже приведен текст интерфейса класса Edge.
package javax.workflow;
public interface Edge
{
Node getInPoint();
Node getOutPoint();
Object getDirection();
void setDirection(Objectdirection) throws InvalidOperation;
Object getValue();
void setValue(Object value)throws InvalidOperation;
}
3.1.3. Класс Graph
Класс Graph является классом для классов,который объединяет функциональность классов Node и Edge. В данном классе реализовано классическое представлениеграфа в виде совокупности вершин и ребер, соединяющие некоторые из этих вершин.Класс позволяет хранить произвольное количество вершин, имеющих определенноесемантическое значение. Кроме того, класс обеспечивает возможность установленияи хранения произвольного количества связей между заданными вершинами.
В модели документооборота, реализованной награфах, это класс выполняет функцию депозитария бизнес — процессов. В этомклассе обеспечено хранение и управление основными данными, составляющимидокументооборот, а именно – участниками документооборота, действиями участникови документами. Описанные с помощью этого класса процессы являются обобщеннымикопиями реальных процессов, происходящих в организации. При установленнойобщности, возможно использования обьектно- ориентированного наследования. Издепозитария берется копия нужного класса, по макету которого создаетсяреализация, которая представляет собой активный процесс документооборота.
Метод createNode предназначен для созданиямножества вершин графа. То есть для создания множества состояний документов,используемых в процессе. Метод createEdge используется для создания множестваребер графа документооборота. В применении к модели документооборота этоозначает множество действий, которые производятся участниками для изменениясостояний документов. Методы deleteNode и deleteEdge используются при удалениивершины и ребра соответственно. Методы getNodes и getEdges используются длясоздания упорядоченных коллекций, являющихся хранилищем для множества вершин имножества ребер.
Методы getName и setName пременен для храненияспецифической информации, которая используется для индивидуального обозначениякаждого процесса. Этот методы был использован в связи с тем, что в практическомиспользовании часто возникает ситуация в которой создается много очень похожихпроцессов по которым движется много похожих документов. В таких случаяприменяется индивидуальное маркирование процессов, которое свойственно процессув пределах его жизненного цикла.
Ниже приведен текст интерфейса класса Graph.
package javax.workflow;
public interface Graph
{
Collection getNodes();
Collection getEdges();
Node createNode(Object value);
EdgecreateEdge(Node in, Node out, Object direction, Object value);
void deleteNode(Node node)throws InvalidOperation;
void deleteEdge(Edge edge)throws InvalidOperation;
String getName();
void setName(String name);
}
3.1.4. Класс HyperGraph
Класс HyperGraph является высшим из классов виерархии языка GJE. Этот класс обьединяет в себе всевышеописанные классы и действия над ними. Действия над классами реализованы всоответствии с алгеброй документооборота, предложенной автором в работе [10].Кроме алгебры документооборота, в методах этого класса реализованы методы,которые обеспечивают создание и управление коллекцией графов. Коллекция графовиспользуется для депозитария, в котором хранятся графы.
Гиперграфы – это совокупностьграфов, объединенных по определенным свойствам. Гиперграфы используют дляпредставления совокупности графов в виде единого целого без потери свойств ихарактеристик, присущих графам, входящим в гиперграф.
В графовой моделидокументооборота, гиперграфом описывается совокупность процессов, составляющихдокументооборот предприятия либо обособленного подразделения. Гиперграфявляется хранилищем процессов, в котором объединены графы процессов, которыеиспользуются, использовались или могут быть использованы на предприятии.
Метод getGraphs используется длясоздания и управления депозитарием процессов, реализованных в виде коллекцииграфов. Тип Collection является стандартным типом языка JAVA,который используется для создания и управления большими массивами разнородныхданных. Методы addGraph и deleteGraph используются для добавления и удаленияграфов из депозитария. Для реализации этих задач используются стандартныесредства языка JAVA по управлению коллекциями данных. Вто же время в реализации языка GJE предусмотренавозможность усиления стандартных возможностей, то есть добавления собственныхметодов управления данными депозитария.
В классе реализована алгебрадокументооборота, оперирующая на графах. Реализации методов основаны наописании операций на графах, представленные автором в работе [10]. В настоящуюреализацию языка GJE входят следующие операции:объединение, пересечение, разности множеств и декартово произведение множеств.
Метод unionGraph реализуетоперацию объединения графов. Объединение графов основано на операцииобъединения множеств. В применении к задачам документооборота эта задачаиспользуется при синтезе композитного документооборота из апробированныхпроцессов, хранящихся в депозитарии предприятия.
Метод intersectionGraphиспользуется для реализации операции пересечения графов. Необходимостьприменения этой операции в графовой модели документооборота возникает, когдатребуется получить пересечение существующих процессов. При реализации системдокументооборота часто получаются системы, которые состоят из значительного количествапроцессов. В таких случаях возникает задача анализа процессов для выявленияконфликтных и дефицитных исполнительских ресурсов. После применения операциипересечения к нескольким графам, получается результирующий граф, которыйявляется графом критического пути. То есть такого пути, появление задержек накотором вызовет возникновение задержек во всем документообороте.
Метод differenceGraph реализуетоперацию разности на графах. В применении к модели документооборота этоозначает разницу двух процессов. Даная операция используется, когда возникаетзадача сравнения различных процессов. Обычно такая задача возникает в случае,когда надо выделить неиспользуемый фрагмент процессов. Для этого используется,так называемый, эталонный процесс. Во время анализа считается, что содержаниеэталонного процесса является наилучшим для решения рассматриваемого классазадач. Такие эталонные процессы хранятся в депозитарии и могут являться основойдокументооборота при синтезе сложных процессов. После сравнения эталонногопроцесса с изучаемым процессом, получается разницы, которую следует критическирассмотреть на предмет возможного улучшения.
Метод cartesianGraph применяетсядля реализации произведения графов. В задачах документооборота произведениеграфов используется при получении декартового произведения процессов. Например,необходимость в этом возникает в случае, если возникает задача тиражированияпроцессов документооборота с некоторым предопределенным параметром. Частнымслучаем такой задачи можно считать тиражирование с единичным вектором(скаляром) после умножения, на который процесс не изменяется. Таким образом,задача тиражирования процесса с параметром может быть представлена в видецикла умножения матрицы процесса на матрицу- вектор, которая изменяется от скалярадо установленного значения.
Ниже приведен текст интерфейса класса HyperGraph.
package javax.workflow;
import java.util.Collection;
public interface HyperGraph
{
Collection getGraphs();
void addGraph(Graph graph) throws InvalidOperation;
void deleteGraph(Graph graph)throws InvalidOperation;
Graph unionGraph(Graph graph1,Graph graph2);
Graph intersectionGraph(Graphgraph1, Graph graph2);
Graph differenceGraph(Graphgraph1, Graph graph2);
Graph cartesianGraph(Graphgraph1, Graph graph2);
Graph createGraph(Collectionnodes, Collection edges);
}
3.1.5. InvalidOperation
Класс InvalidOperation используется дляобработки исключений. Исключения возникают при выполнении операций сдепозитариями, не предусмотренных стандартными описателями, а также принекорректных операциях на графах. Этот класс можно использовать длядополнительной индивидуализации приложений, поскольку этому классу передаетсяуправление в случае возникновения внештатных ситуаций.
В настоящей реализации дляобработки исключений используется конструктор родового класса. Это позволяетразработчику задействовать собственные методы обработки исключений, чтообеспечивает дополнительную совместимость и гибкость реализации.
Ниже приведен текст интерфейса класса InvalidOperation.
package javax.workflow;
public class InvalidOperation
extends Exception
{
public InvalidOperation(Stringmessage)
{
super(message);
}
}
4. Выводы
В настоящей статье представлен язык обработкиграфов GJE на базе расширения языка JAVA,который был использован для создания системы проектирования и исполнения системкомпозитного документооборота. Наряду с операциями над множествами даноописание интерфейсов для классов вершин, ребер, графовых систем и ихобьединение. Показана возможность языка GJE как дляанализа, так и синтеза системы композитного документооборота.
Благодаря построения языка GJEкак расширения языка JAVA имеется возможностьобеспечить как локальное, так и сетевое взаимодействие между процессамиэлектронного документооборота и адаптации систем к внутренним и внешнимусловиям использования.
ЛИТЕРАТУРА
1. Теслер Г.С. Новая кибернетика.- Киев: Логос, 2004. –401с.
2. Круковский М.Ю. Концепция построения моделей композитногодокументооборота// Математичні машини і системи. – 2004. – № 2. – С. 149с –163с.
9. Круковский М.Ю. Графовая моделькомпозитного документооборота// Математичні машини і системи. – 2005. – № 3. –С. 149с – 163с.
4. Duncan J. Watts. Small worlds: thedynamics of networks between order and randomness.- Princeton: Princetonuniversity press, 1999. – 262p.
5. S. Crespi-Reghizzi, R. Morpurgo. Alanguage for treating graphs. — Communications of the ACM, May 1970, Volume13 Issue 5. 319-323
6. Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х томах. Т.1:Введение в язык Лисп и функциональное программирование.-М: Мир, 1990.- 447с.;Т.2.: Методы и системы программирования., 1990.-319с.
7. Terrence W. Pratt, Daniel P. Friedman. Alanguage extension for graph processing and its formal semantics.Communications of the ACM, July 1971, Volume 14 Issue 7. 460-467.
8. Medha Shukla Sarkar. GXL: a new graphtransformation language Proceedings of the 42nd annual southeast regionalconference. 2004. 336-340.
9. M. F. Kleyn, J. C. Browne. A high levellanguage for specifying graph based languages and their programmingenvironments. Proceedings of the 15th international conference on SoftwareEngineering. 1993. 324-335.
10. Thorsten Daum, Robert G. Sargent. AJava based system for specifying hierarchical control flow graph models.Proceedings of the 29th conference on Winter simulation. 1997. 150-157.