AGraph: библиотека классов для работы с помеченными графами— это библиотека, которая сформирована на языке Object Pascal и считается практически единственной развитой библиотекой для работы с графами на Object Pascal.
Общие сведения о библиотеках для работы с графами
На текущий момент имеется значительный опыт в решении теоретических задач, связанных с построением графов, на компьютерах. Программы, позволяющие решить многие из этих задач, могут быть найдены на просторах глобальной сети Интернет. Однако применение независимо спроектированных программ может быть связано с существенными трудностями. К их числу могут быть отнесены общие технические проблемы, которые не зависят от предметной сферы, такие как разные программные языки, низкий уровень несовместимости программного и аппаратного обеспечения, и, кроме того, вопросы, сопряжённые со спецификой теоретических задач, такие как, применение разных внутренних представлений графов.
По этой причине актуальной задачей может считаться формирование универсальных библиотек, которые должны предоставлять пользователям средства высокого уровня для работы с графами, а также должны избавить их от программирования в ручном режиме простых операций ввода и вывода между разными внутренними представлениями графов.
Проектирование универсальной библиотеки для работы с графами считается достаточно непростой задачей. В теории графов присутствует очень много разнообразных задач. Так как теоретические исследования и создание новых алгоритмов постоянно продолжаются, то ясно, что ни одна из библиотек не способна решить все присутствующие задачи.
Ещё одной проблемой считается повышение уровня эффективности. Довольно часто имеется набор алгоритмов для решения одной и той же задачи, при этом не всегда возможно выбрать алгоритм, который является оптимальным для любого случая. То есть, для одного типа графов более эффективным может стать один алгоритм, для других типов это может быть другой алгоритм. Проектировщик универсальной библиотеки, как правило, не может позволить себе реализовать нескольких алгоритмов, предназначенных для решения одной задачи. По этой причине ему необходимо искать компромисс между эффективностью и универсальностью.
При разработке библиотек для работы с графами может возникнуть также ряд технических трудностей. Для приемлемой с точки зрения эффективности реализации большинства алгоритмов программист должен иметь в своем распоряжении следующие структуры данных:
- Динамические массивы.
- Списки.
- Стеки.
- Очереди.
- Приоритетные очереди.
- Деревья поиска.
Реализовать все необходимые структуры данных в границах одной библиотеки представляется вряд ли возможным и оправданным, поэтому универсальная библиотека для работы с графами предполагает наличие серьезной программной инфраструктуры в виде других библиотек.
AGraph: библиотека классов для работы с помеченными графами
Разработка библиотеки AGraph преследовала следующие главные цели:
- Охватить широкий круг теоретических проблем, связанных с графами.
- Обеспечить простоту применения.
- Обеспечить высокий уровень эффективности.
Библиотека AGraph реализована на языке Object Pascal, используемом в Delphi, то есть среде быстрого формирования приложений (RAD) компании Inprise (бывшей Borland). Она является, по всей видимости, единственной развитой библиотекой для работы с графами на Object Pascal. При этом, применяемый язык программирования не является главным отличием AGraph от других библиотек.
Если возникнет необходимость, то библиотеку AGraph можно переписать с применением таких объектно-ориентированных языков программирования, как C++, Eiffel или Java. Перенос может быть облегчён тем фактом, что AGraph не применяет набор стандартных библиотек классов Delphi VCL (Visual Component Library), за исключением классов исключительных ситуаций (Exception).
В пользу выбора языка Object Pascal как средства создания библиотеки для обработки графов говорят следующие соображения. На сегодняшний день спроектировано достаточное количество объектно-ориентированных языков программирования (ООЯП), таких как, Smalltalk, C++, Java, Object Pascal, Eiffel, Oberon-2, Modula-3 и другие. Если исходить из достоинств и недостатков самих языков программирования, без учёта распространенности языка и качества его существующих реализаций, то одним из лучших претендентов может считаться язык Eiffel. Но, если принять во внимание конкретную платформу, которая имеется в наличии (персональный компьютер на процессоре семейства Intel, который работает под управлением операционных систем Windows или Linux), а также фактически доступные системы программирования коммерческих качеств, то выбор значительно сужается, а именно, остались только языки C++, Java и Object Pascal. Языки Smalltalk и Java не могут подойти из соображений эффективности. Самый распространенный сегодня ООЯП, C++, поддерживается практически на всех платформах и считается очень мощным языком программирования.
Важным фактором является существование стандарта языка C++, а к недостаткам С++ следует причислить его повышенную, в сравнении с Object Pascal, сложность. Принимая во внимание набор целей, поставленных при проектировании библиотеки AGraph, и прежде всего простоты использования, был выбран язык Object Pascal.
Формирование серьезных программных систем сегодня, по сути, нереально без применения вспомогательных программных компонент, которые реализуют основные структуры данных и алгоритмы. При проектировании библиотеки AGraph также возникла потребность в базовых программных средствах. Поскольку готовых средств такого типа для Object Pascal не было, то необходимо было их создать самостоятельно. Разработанные в процессе этой работы базовые структуры данных и алгоритмы были включены в состав библиотеки, названной Vectors. В этой библиотеке выполнена реализация векторов (динамических массивов) на базе главных типов Object Pascal.
