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

(Вильям Гибсон)

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

Математические множества можно, как мы видели, моделировать с помощью массивов. Но в последних версиях Ruby есть также класс

Set

Стеки и очереди — две весьма распространенные в информатике структуры данных. В первом издании этой книги им было уделено чрезмерно много внимания. Для тех, кого интересуют общие вопросы, я оставил кое-какой материал; для остальных есть немало великолепных книг по структурам данных и алгоритмам.

Деревья полезны для сортировки, поиска и просто представления иерархических данных. Мы рассмотрим двоичные деревья и сделаем несколько замечаний о деревьях более высокой степени.

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

Но самыми простыми структурами являются множества. С них мы и начнем.

Мы уже видели, что некоторые методы класса

Array

Set

Чтобы получить в свое распоряжение класс

Set

require 'set'

При этом также добавляется метод

to_set

Enumerable

Создать новое множество нетрудно. Метод

[]

new

map

s1 = Set[3,4,5]                 # В математике обозначается {3,4,5}.

arr = [3,4,5]

s2 = Set.new(arr)               # То же самое.

s3 = Set.new(arr) {|x| x.to_s } # Множество строк, а не чисел.

Для объединения множеств служит метод

union

|

+

x = Set[1,2,3]

y = Set[3,4,5]

а = x.union(y) # Set[1,2,3,4,5]

b = x | y      # То же самое.

с = x + y      # То же самое.

Пересечение множеств вычисляется методом

intersection

&

x = Set[1,2,3]

y = Set[3,4,5]

а = x.intersection(y) # Set[3]

b = x & y # То же самое.

Унарный минус обозначает разность множеств; мы обсуждали эту операцию в разделе 8.1.9.

diff = Set[1,2,3] - Set[3,4,5] # Set[1,2]

Принадлежность элемента множеству проверяют методы

member?

include?

Set[1,2,3].include?(2) # true

Set[1,2,3].include?(4) # false

Set[1,2,3].member?(4)  # false

Чтобы проверить, является ли множество пустым, мы вызываем метод

empty?

clear

s = Set[1,2,3,4,5,6]

s.empty? # false

s.clear

s.empty? # true

Можно проверить, является ли одно множество подмножеством, собственным подмножеством или надмножеством другого.

x = Set[3,4,5]

y = Set[3,4]

x.subset?(y)        # false

y.subset?(x)        # true

y.proper_subset?(x) # true

x.subset?(x)        # true

x.proper_subset?(x) # false

x.superset?(y)      # true

Метод

add

<<

add?

nil

replace

Наконец, два множества можно сравнить на равенство интуитивно очевидным способом:

Set[3,4,5] == Set[5,4,3] # true

Разумеется, можно обойти множество, но (как и для хэшей) не ожидайте какого-то определенного порядка появления элементов, потому что множества по сути своей неупорядочены, и Ruby не гарантирует никакой последовательности. (Временами можно получить повторяющиеся, ожидаемые результаты, но полагаться на это неразумно.)

s = Set[1,2,3,4,5]

s.each {|x| puts x; break } # Выводится: 5

Метод

classify

partition

classify

files = Set.new(Dir ["*"])

hash = files.classify do |f|

 if File.size(f) <= 10_000

  :small

 elsif File.size(f) <= 10_000_000

  :medium

 else

  :large

 end

end

big_files = hash[:large] # big_files - это Set.

Метод

divide

Если «арность» (число аргументов) блока равна 1, то метод выполняет вызовы вида

block.call(а) == block.call(b)

а

b

block.call(a,b)

Например, следующий блок (с «арностью» 1) разбивает множество на два подмножества, одно из которых содержит четные числа, а другое — нечетные:

require 'set'

numbers = Set[1,2,3,4,5,6,7,8,9,0]

set = numbers.divide{|i| i % 2}

p set # #<Set: {#<Set: {5, 1, 7, 3, 9}>, #<Set: {0, 6, 2, 8, 4}>}>

Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 2 (например, 11 и 13); все прочие называются одиночными (например, 23). Следующий код разбивает множество на группы, помещая числа-близнецы в одно и то же подмножество. В данном случае применяется блок с «арностью» 2:

primes = Set[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

set = primes.divide{|i,j| (i-j).abs == 2}

# set is: #<Set: {#<Set: {23}>, #<Set: {11, 13}>,

#         #<Set: {17, 19}>,     #<Set: {5, 7, 3}>,

#         #<Set: {2}>,          #<Set: {29, 31}>}>

# Более компактно: {{23},{11,13},{17,19},{5,7,3}, {2},{29,31}}

На мой взгляд, этот метод труден для понимания; я рекомендую пользоваться методом

classify

Важно понимать, что класс

Set

Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля

Enumerable

flatten

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов

Stack

Queue

Array

Hash

Queue

thread.rb

И все же в некотором смысле они встроены в Ruby. Ведь класс

Array

Над стеком можно выполнять ограниченный набор операций. Как минимум операции заталкивания (push) и выталкивания (pop), то есть помещения в стек и извлечения из него. Обычно также предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.

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

Но можно без труда определить класс

Stack

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

Очередь организована по принципу «первым пришел, первым обслужен» (FIFO — first-in first-out). Аналогом может служить очередь за билетами в театр: вновь подходящие становятся в конец очереди, а те, кто пришел раньше, обслуживаются первыми. В программировании очереди используются реже, чем стеки.

Очереди полезны в системах реального времени, когда события нужно обрабатывать в порядке возникновения. Находят они применение и в ситуации «производитель-потребитель» (особенно в многопоточных программах и многозадачных средах). Неплохой пример — очередь к принтеру: задания на печать помещаются в один конец и ожидают, пока не будут извлечены с другого конца.

Две основные операции над очередью называются «поместить» (enqueue) и «извлечь» (dequeue). Им соответствуют методы

unpush

shift

Array

Отметим, что метод

unshift

shift

unshift

shift

На этом мы закончим введение в стеки и очереди. Самое время рассмотреть некоторые примеры.

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

class Stack

 def initialize

  @store = []

 end

 def push(x)

  @store.push x

 end

 def pop

  @store.pop

 end

 def peek

  @store.last

 end

 def empty?

  @store.empty?

 end

end

Мы добавили одну операцию, которая для массивов не определена; метод

peek

Нижеследующие примеры подтверждают адекватность такого определения класса.

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

def paren_match(str)

 stack = Stack.new

 lsym = "{I(<"

 rsym = "}])>"

 str.each_byte do |byte|

  sym = byte.chr

  if lsym.include? sym

   stack.push(sym)

  elsif rsym.include? sym

   top = stack.peek

   if lsym.index(top) != rsym.index(sym)

    return false

   else

    stack.pop

   end

   # Игнорируем символы, отличные от скобок...

  end

 end

 # Убедимся, что стек пуст...

 return stack.empty?

end

str1 = "(((a+b))*((c-d)-(e*f))"

str2 = "[[(a-(b-c))], [[x,y]]]"

paren_match str1 # false

paren_match str2 # true

Наличие вложенности естественным образом наводит на мысль о применении стека. Чуть сложнее распознать несбалансированные теги в HTML- или XML-документе. Лексемы состоят из нескольких символов, но логическая структура задачи остается той же самой. Вот еще типичные примеры задач, требующих стека: преобразование выражений из инфиксной формы в постфиксную (и наоборот), вычисление постфиксного выражения (как делается в виртуальной машине Java и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.

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

Попутно разоблачим миф. Похоже, что на самом деле эту задачу впервые сформулировал французский математик Эдуард Люка в 1883 году, и никаких истоков в восточной культуре она не имеет. Сам Люка называл ее «Ханойской башней».

Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 2⁶⁴-1 ходов. Небольшой расчет на калькуляторе покажет, что монахи будут заняты своим делом несколько миллионов лет.

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

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

def towers(list)

 while !list.empty?

  n, src, dst, aux = list.pop

  if n == 1

   puts "Перемещаем диск с #{src} на #{dst}"

  else

   list.push [n-1, aux, dst, src]

   list.push [1, src, dst, aux]

   list.push [n-1, src, aux, dst]

  end

 end

end

list = []

list.push([3, "a", "c", "b"])

towers(list)

Вот что напечатает эта программа:

Перемещаем диск с а на с

Перемещаем диск с а на b

Перемещаем диск с с на b

Перемещаем диск с а на с

Перемещаем диск с b на а

Перемещаем диск с b на с

Перемещаем диск с а на с

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

def towers(n, src, dst, aux)

 if n==1

  puts "Перемещаем диск с #{src} на #{dst}"

 else

  towers(n-1, src, aux, dst)

  towers(1, src, dst, aux)

  towers(n-1, aux, dst, src)

 end

end

towers(3, "а", "с", "b")

Печатается точно такой же результат. Возможно, вам будет интересно знать, что «закомментарили» предложения, осуществляющие вывод, и сравнили время работы. Никому не говорите, но рекурсивное решение оказалось в два раза быстрее!

Мы определим очередь примерно так же, как стек. Если вы хотите защититься от некорректного доступа к структуре данных, рекомендуем поступать аналогично.

class Queue

 def initialize

  @store = []

 end

 def enqueue(x)

  @store << x

 end

 def dequeue

  @store,shift

 end

 def peek

  @store.first

 end

 def length

  @store.length

 end

 def empty?

  @store.empty?

 end

end

Отметим, что класс

Queue

thread

SizedQueue

В упомянутых классах методы имеют короткие имена:

enq

deq

push

pop

Разумеется, класс

Queue

thread.rb

Stack

Queue

В первом издании книги был длинный пример, демонстрирующий работу с очередями. Но, как и некоторые примеры, касающиеся стеков, он был исключен ради экономии места.

Я не увижу никогда, наверное,
Поэму столь прекрасную как дерево.

(Джойс Килмер, «Деревья»[11])

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

Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются узлами; верхний или самый первый узел называется корневым или корнем. У узла могут быть потомки, расположенные ниже него, а непосредственные потомки называются детьми или дочерними узлами. Узел, не имеющий потомков, называется листовым или просто листом. Поддерево состоит из некоторого узла и всех его потомков. Посещение всех узлов дерева (например, с целью распечатки) называется обходом дерева.

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

Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.

Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.

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

В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс

Tree

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод

insert

traverse

class Tree

 attr_accessor :left

 attr_accessor :right

 attr_accessor :data

 def initialize(x=nil)

  @left = nil

  @right = nil

  @data = x

 end

 def insert(x)

  list = []

  if @data == nil

   @data = x

  elsif @left == nil

   @left = Tree.new(x)

  elsif @right == nil

   @right = Tree.new(x)

  else

   list << @left

   list << @right

   loop do

    node = list.shift

    if node.left == nil

     node.insert(x)

     break

    else

     list << node.left

    end

    if node.right == nil

     node.insert(x)

     break

    else

     list << node.right

    end

   end

  end

 end

 def traverse()

  list = []

  yield @data

  list << @left if @left != nil

  list << @right if @right != nil

  loop do

   break if list.empty?

   node = list.shift

   yield node.data

   list << node.left if node.left != nil

   list << node.right if node.right != nil

  end

 end

end

items = [1, 2, 3, 4, 5, 6, 7]

tree = Tree.new

items.each {|x| tree.insert(x)}

tree.traverse {|x| print "#{x} "}

print "\n"

# Печатается "1 2 3 4 5 6 7 "

Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.

Двоичное дерево позволяет эффективно реализовать сортировку произвольных данных. (Правда, если данные уже отсортированы, оно вырождается в обычный связанный список.) Причина ясна: при каждом сравнении мы исключаем половину мест, в которые можно поместить новый узел.

Хотя в настоящее время такой способ сортировки применяется редко, знать о нем не повредит. Код в листинге 9.2 основан на предыдущем примере.

class Tree

 # Предполагается, что определения взяты из предыдущего примера...

 def insert(x)

  if @data == nil

   @data = x

  elsif x <= @data

   if @left == nil

    @left = Tree.new x

   else

    @left.insert x

   end

  else

   if @right == nil

    @right = Tree.new x

   else

    @right.insert x

   end

  end

 end

 def inorder()

  @left.inorder {|y| yield y} if @left != nil

  yield @data

  @right.inorder {|y| yield y} if bright != nil

 end

 def preorder()

  yield @data

  @left.preorder {|y| yield y} if @left != nil

  @right.preorder {|y| yield y} if @right != nil

 end

 def postorder()

  @left.postorder {|y| yield y} if @left != nil

  @right.postorder {|y| yield y} if @right != nil

  yield @data

 end

end

items = [50, 20, 80, 10, 30, 70, 90, 5, 14,

         28, 41, 66, 75, 88, 96]

tree = Tree.new

items.each {|x| tree.insert(x)}

tree.inorder {|x| print x, " "}

print "\n"

tree.preorder {|x| print x, " "}

print "\n"

tree.postorder {|x| print x, " "}

print "\n"

# Печатается:

# 5 10 14 20 28 30 41 50 66 70 75 80 88 90 96

# 50 20 10 5 14 30 28 41 80 70 66 75 90 88 96

# 5 14 10 28 41 30 20 66 75 70 88 96 90 80 50

Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.

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

class Tree

 # Предполагается, что определения взяты из предыдущего примера...

 def search(x)

  if self.data == x

   return self

  elsif x < self.data

   return left ? left.search(x) : nil

  else

   return right ? right.search(x) : nil

  end

 end

end

keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,

        28, 41, 66, 75, 88, 96]

tree = Tree.new

keys.each {|x| tree.insert(x)}

s1 = tree.search(75)  # Возвращает ссылку на узел, содержащий 75...

s2 = tree.search(100) # Возвращает nil (не найдено).

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

class Tree

 # Предполагается, что определения взяты из предыдущего примера...

 def to_s

  "[" +

  if left then left.to_s + "," else "" end +

  data.inspect +

  if right then "," + right.to_s else "" end + "]"

 end

 def to_a

  temp = []

  temp += left.to_a if left

  temp << data

  temp += right.to_a if right

  temp

 end

end

items = %w[bongo grimace monoid jewel plover nexus synergy]

tree = Tree.new

items.each {|x| tree.insert x}

str = tree.to_a * ","

# str is now "bongo,grimace,jewel,monoid,nexus,plover,synergy"

arr = tree.to_a

# arr равно:

#  ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",

#   ["synergy"]]]]]

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

flatten

Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.

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

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

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

Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса

ZArray

TriMatrix

class LowerMatrix < TriMatrix

 def initialize

  @store = Zarray.new

 end

end

class Graph

 def initialize(*edges)

  @store = LowerMatrix.new

  @max = 0

  for e in edges

   e[0], e[1] = e[1], e[0] if e[1] > e[0]

   @store[e[0],e[1]] = 1

   @max = [@max, e[0], e[1]].max

  end

 end

 def [](x,y)

  if x > y

   @store[x,y]

  elsif x < y

   @store[y,x]

  else

   0

  end

 end

 def []=(x,y,v)

  if x > y

   @store[x,y]=v

  elsif x < y

   @store[y,x]=v

  else

   0

  end

 end

 def edge? x,y

  x,y = y,x if x < y

  @store[x,y]==1

 end

 def add x,y

  @store[x,y] = 1

 end

 def remove x,y

  x,y = y,x if x < y

  @store[x,y] = 0

  if (degree @max) == 0

   @max -= 1

  end

 end

 def vmax

  @max

 end

 def degree x

  sum = 0

  0.upto @max do |i|

   sum += self[x,i]

  end

  sum

 end

 def each_vertex

  (0..@max).each {|v| yield v}

 end

 def each_edge

  for v0 in 0..@max

   for v1 in 0..v0-1

    yield v0, v1 if self[v0,v1]==1

   end

  end

 end

end

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

# Напечатать степени всех вершин: 2 3 2 3.

mygraph.each_vertex {|v| puts mygraph.degree(v)}

# Напечатать список ребер.

mygraph.each_edge do |a,b|

 puts "(#{a},#{b})"

end

# Удалить одно ребро.

mygraph.remove 1,3

# Напечатать степени всех вершин: 2 2 2 2.

mygraph.each_vertex {|v| p mygraph.degree v}

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

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

vmax

degree

Наконец, имеются два итератора

each_vertex

each_edge

Не все графы связные. Иногда нет способа «добраться из одной точки в другую», то есть между двумя вершинами нет никакого пути, составленного из ребер. Связность — это важное свойство графа, его надо уметь вычислять. В связном графе любая вершина достижима из любой другой.

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

class Graph

 def connected?

  x = vmax

  k = [x]

  l = [x]

  for i in 0..@max

   l << i if self[x,i]==l

  end

  while !k.empty?

   y = k.shift

   # Теперь ищем все ребра (y,z).

   self.each_edge do |a,b|

    if a==y || b==y

     z = a==y ? b : a

     if !l.include? z

      l << z

      k << z

     end

    end

   end

  end

  if l.size < @max

   false

  else

   true

  end

 end

end

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

puts mygraph.connected?  # true

puts mygraph.euler_path? # true

mygraph.remove 1,2

mygraph.remove 0,3

mygraph.remove 1,3

puts mygraph.connected?  # false

puts mygraph.euler_path? # false

В примере упомянут метод

euler_path?

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

Нет такой отрасли математики, сколь угодно абстрактной, которая со временем не нашла бы применения в реальной жизни.

(Николай Лобачевский)

Иногда нужно знать, есть ли в графе эйлеров цикл. Термин связан с математиком Леонардом Эйлером, который основал область топологии, занимающуюся этим вопросом. (Графы, обладающие таким свойством, называют иногда уникурсивными, поскольку их можно нарисовать не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру.)

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

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

class Graph

 def euler_circuit?

  return false if !connected?

  for i in 0..@max

   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

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

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

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

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

GnomeGraphWidget

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

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

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

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

Примечания:

1

Огромное спасибо (яп.)

11

Пер. Я. Фельдмана. — Прим. ред.