Программирование на языке Ruby - Хэл Фултон

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

class Graph

 def euler_circuit?

  return false if !connected?

  for i in [email protected]

   return false if degreed) % 2 != 0

  end

  true

 end

end

mygraph = Graph.new([1,0],[0,3],[2,1],[3,1],[3,2])

flag1 = mygraph.euler_circuit? # false

mygraph.remove 1,3

flag2 = mygraph.euler_circuit? # true

9.4.4. Есть ли в графе эйлеров путь?

Эйлеров путь и эйлеров цикл — разные вещи. Слово «цикл» подразумевает, что нужно вернуться в исходную точку. А наличие пути предполагает, что нужно лишь посетить каждую вершину ровно один раз. В следующем фрагменте демонстрируется это различие:

class Graph

 def euler_path?

  return false if !connected?

  odd=0

  each_vertex do |x|

   if degree(x) % 2 == 1

    odd += 1

   end

  end

  odd <= 2

 end

end

mygraph = Graph.new([0,1],[1,2],[1,3],[2,3],[3,0])

flag1 = mygraph.euler_circuit? # false

flag2 = mygraph.euler_path?    # true

9.4.5. Инструменты для работы с графами в Ruby

В сообществе пользователей Ruby известно несколько таких инструментов. Они в большинстве своем имеют ограниченную функциональность и предназначены для работы с ориентированными или неориентированными графами. Поищите эти инструменты в архиве RAA (http://raa.ruby-lang.org) или на сайте Rubyforge (http://rubyforge.org). Называются они как-то вроде RubyGraph, RGraph, GraphR и по большей части еще не достигли зрелости.

Если вас интересует великолепный пакет GraphViz, который умеет представлять сложные графы в виде изображений или программ на языке Postscript, то к нему есть по меньшей мере два работоспособных интерфейса. Есть даже элемент управления GnomeGraphWidget, который, если верить документации, «можно использовать в приложениях Ruby Gnome для генерирования, визуализации и манипулирования графами». Мы его, впрочем, не изучали; пока еще не вышла даже официальная альфа-версия.

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

9.5. Заключение

Мы познакомились с классом Set в Ruby, а также с несколькими примерами «доморощенных» структур данных. Мы видели, как можно создавать сложные структуры данных путем наследования существующему классу или ограниченного делегирования, когда экземпляр существующего класса инкапсулируется в новой структуре. Также были рассмотрены изобретательные способы хранения данных, применения различных структур данных и создания итераторов для обхода таких структур.

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

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

Глава 10. Ввод/вывод и хранение данных

На чистом диске можно искать бесконечно.

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

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

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

История знает такие устройства, как магнитные барабаны, перфоленты, магнитные ленты, перфокарты и телетайпы. Некоторые имели механические детали, другие были электромагнитными от начала и до конца. Одни позволяли только считывать информацию, другие — только записывать, а третьи умели делать и то и другое. Часть записывающих устройств позволяла стирать данные, другая — нет. Одни были принципиально последовательными, другие допускали произвольный доступ. На иных устройствах информация хранилась постоянно, другие были энергозависимыми. Некоторые требовали человеческого вмешательства, другие — нет. Есть устройства символьного и блочного ввода/вывода. На некоторых блочных устройствах можно хранить только блоки постоянной длины, другие допускают и переменную длину блока. Одни устройства надо периодически опрашивать, другие управляются прерываниями. Прерывания можно реализовать аппаратно, программно или смешанным образом. Есть буферизованный и небуферизованный ввод/вывод. Бывает ввод/вывод с отображением на память и канальный, а с появлением таких операционных систем, как UNIX, мы узнали об устройствах ввода/вывода, отображаемых на элементы файловой системы. Программировать ввод/вывод доводилось на машинном языке, на языке ассемблера и на языках высокого уровня. В некоторые языки механизм ввода/вывода жестко встроен, другие вообще не включают ввод/вывод в спецификацию языка. Приходилось выполнять ввод/вывод с помощью подходящего драйвера или уровня абстракции и без оного.

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

Ввод/вывод в Ruby сложен, потому что он сложен в принципе. Но мы старались описать его как можно понятнее и показать, где и когда стоит применять различные приемы.

В основе системы ввода/вывода в Ruby лежит класс IO, который определяет поведение всех операций ввода/вывода. С ним тесно связан (и наследует ему) класс File. В класс File вложен класс Stat, инкапсулирующий различные сведения о файле (например, разрешения и временные штампы). Методы stat и lstat возвращают объекты типа File::Stat.

В модуле FileTest также есть методы, позволяющие опрашивать практически те же свойства. Он подмешивается к классу File, но может использоваться и самостоятельно.

Наконец, методы ввода/вывода есть и в модуле Kernel, который подмешивается к классу Object (предку всех объектов, включая и классы). Это простые процедуры, которыми мы пользовались на протяжении всей книги, не думая о том, от имени какого объекта они вызываются. По умолчанию они настроены на стандартный ввод и стандартный вывод.

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

На более высоком уровне Ruby предлагает механизмы, позволяющие сделать объекты устойчивыми. Метод Marshal реализует простую сериализацию объектов; он лежит в основе более изощренной библиотеки PStore. Мы включили в эту главу и библиотеку DBM, хотя она умеет работать только со строками.

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

10.1. Файлы и каталоги

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

Класс File тесно связан с классом IO, которому наследует. Класс Dir связан с ним не так тесно, но мы решили рассмотреть файлы и каталоги вместе, поскольку между ними имеется концептуальная связь.

10.1.1. Открытие и закрытие файлов

Метод класса File.new, создающий новый объект File, также открывает файл. Первым параметром, естественно, является имя файла.