GXL: Стандарт обмена графовыми данными для разработки ПО

Введение

GXL (Graph eXchange Language) разработан как стандартный формат обмена графами. GXL является подмножеством расширяемого языка разметки (XML), а его синтаксис определяется определением типа документа XML (DTD). Этот формат обмена предоставляет адаптивный и гибкий способ обеспечения совместимости между инструментами, работающими с графами.

Обзор

В частности, GXL был разработан для обеспечения взаимодействия между инструментами и компонентами реинжиниринга программного обеспечения, такими как извлекатели кода (парсеры), анализаторы и визуализаторы. GXL позволяет специалистам по реинжинирингу программного обеспечения объединять инструменты узкой специализации, особенно для парсинга, извлечения исходного кода, восстановления архитектуры, анализа потока данных, анализа указателей, секционирования программ, реализации запросов, визуализации исходного кода, восстановления объектов, реструктуризации, рефакторинга, ремодуляризации и т.д., в единую мощную среду реинжиниринга. GXL обладает двумя инновационными особенностями, которые делают его подходящим форматом для обмена программными данными. Концептуальная модель данных представляет собой типизированный, атрибутированный, ориентированный граф. Это не означает, что все программные данные должны обрабатываться как графы, а скорее, что их можно обменивать в виде графов. Он может использоваться для представления как данных экземпляров, так и схем, описывающих структуру данных. Более того, схема может быть явно указана вместе с данными экземпляров. Структура графов, обмениваемых потоками GXL, определяется схемой, представленной в виде диаграммы классов Unified Modeling Language (UML). Поскольку GXL является универсальным форматом обмена графами, он также может использоваться для обмена любыми данными, основанными на графах, включая модели между инструментами автоматизированного проектирования программного обеспечения (CASE), данными между системами преобразования графов или инструментами визуализации графов. GXL поддерживает гиперграфы и иерархические графы и может быть расширен для поддержки других типов графов. GXL возник в результате объединения формата обмена графами (GraX: Университет Кобленца, Германия) для обмена типизированными, атрибутированными, упорядоченными, ориентированными графами (TGraphs), языка атрибутов кортежей (TA: Университет Ватерлоо, Канада) и формата графов системы переписывания графов PROGRES (Университет Бундесвера Мюнхена, Германия). Кроме того, GXL включает идеи из форматов обмена, используемых при обратной разработке, включая алгебру разделения отношений (RPA: Philips Research Eindhoven, Нидерланды) и стандартный формат Rigi (RSF: Университет Виктории, Канада). Разработка GXL также была подвержена влиянию различных форматов, используемых в построении графов (например, daVinci, Graph Modeling Language (GML), Graphlet, GraphXML) и текущим обсуждениям форматов обмена для систем преобразования графов.

In particular, GXL was developed to enable interoperability between software reengineering tools and components, such as code extractors (parsers), analyzers and visualizers. GXL allows software reengineers to combine single purpose tools especially for parsing, source code extraction, architecture recovery, data flow analysis, pointer analysis, program slicing, query techniques, source code visualization, object recovery, restructuring, refactoring, remodularization, etc., into a single powerful reengineering workbench. There are two innovative features in GXL that make it well suited to an exchange format for software data. The conceptual data model is a typed, attributed, directed graph. This is not to say that all software data ought to be manipulated as graphs, but rather that they can be exchanged as graphs. It can be used to represent instance data as well as schemas for describing the structure of the data. Moreover, the schema can be explicitly stated along with instance data. The structure of graphs exchanged by GXL streams is given by a schema represented as a Unified Modeling Language (UML) class diagram. Since GXL is a general graph exchange format, it can also be used to interchange any graph based data, including models between computer aided software engineering (CASE) tools, data between graph transformation systems, or graph visualization tools. GXL includes support for hypergraphs and hierarchical graphs, and can be extended to support other types of graphs. GXL originated in the merger of GRAph eXchange format (GraX: University of Koblenz, DE) for exchanging typed, attributed, ordered, directed graphs (TGraphs), Tuple Attribute Language (TA: University of Waterloo, CA), and the graph format of the PROGRES graph rewriting system (University Bw München, DE). Furthermore, GXL includes ideas from exchange formats from reverse engineering, including Relation Partition Algebra (RPA: Philips Research Eindhoven, NL) and Rigi Standard Format (RSF: University of Victoria, CA). The development of GXL was also influenced by various formats used in graph drawing (e. g. daVinci, Graph Modelling Language (GML), Graphlet, GraphXML) and current discussions on exchange formats for graph transformation systems.

Презентации предыдущих версий GXL

На семинаре по стандартным форматам обмена (WoSEF) Международной конференции по разработке программного обеспечения (ICSE 2000) 2000 года формат GXL был принят в качестве рабочего проекта для формата обмена данными многочисленными исследовательскими группами, работающими в области реинжиниринга программного обеспечения и преобразования графов. В ходе заседания подгруппы APPLIGRAPH по форматам обмена для преобразования графов был представлен обзор GXL [Schürr, 2000], и участники решили использовать GXL для представления графов в своем формате обмена для систем преобразования графов (GTXL). Конференция IBM Centers for Advanced Studies 2000 (CASCON 2000) включала два полудневных семинара, посвященных GXL. Утром семинар «Обмен программными данными с использованием GXL: введение и учебное пособие» представил обзор синтаксиса и концепций формата, а во второй половине дня семинар «Обмен программными данными с использованием GXL: вопросы реализации» был посвящен разработке конвертеров и стандартных схем. На Седьмой рабочей конференции по обратной разработке (WCRE 2000) GXL был представлен в виде учебного пособия [Holt et al., 2000] и в рамках семинара по форматам обмена [Holt/Winter, 2000]. Ключевыми результатами стали более простое представление информации об упорядочивании, использование диаграмм классов UML для представления схем графов и представление диаграмм классов UML с помощью графов GXL. Семинар Dagstuhl по интероперабельности инструментов реинжиниринга утвердил GXL 1.0 в качестве стандартного формата обмена для обмена данными, связанными с реинжинирингом. Многочисленные группы из промышленности и научных кругов взяли на себя обязательство использовать GXL, импортировать и экспортировать документы GXL в свои инструменты и разрабатывать различные инструменты для GXL.