Мы уже видели, что некоторые методы класса Array позволяют использовать массивы для представления математических множеств. Однако для написания более строгого и компактного кода в Ruby есть также класс 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 } # Множество строк, а не чисел.

 

9.1.1. Простые операции над множествами

Для объединения множеств служит метод 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, если такой элемент уже присутствовал в множестве. Метод merge полезен, если надо добавить сразу несколько элементов. Все они, конечно, могут изменить состояние вызывающего объекта. Метод replace работает так же, как в случае со строкой или массивом.

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

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

 

9.1.2. Более сложные операции над множествами

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

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

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

Метод classify подобен методу partition, но с разбиением на несколько частей; он послужил источником идеи для реализации нашей версии метода classify в разделе 8.3.3.

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 одному подмножеству. Если «арность» равна 2, для той же цели выполняются вызовы вида 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 # #, #}>

Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 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: #, #,

#         #,     #,

#         #,          #}>

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

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

Важно понимать, что класс Set не всегда требует, чтобы параметр или операнд также был множеством (если вам это кажется странным, вспомните обсуждение «утипизации» в главе 1). На самом деле большая часть методов данного класса принимает в качестве параметра любой перечисляемый объект. Считайте, что так и задумано.

Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля Enumerable). Я не стану рассматривать здесь такие методы, как flatten. Дополнительную информацию можно найти на сайте http://ruby-doc.org/ или в любом другом справочном руководстве.

 

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stack и Queue, в отличие от Array и Hash (впрочем, класс Queue есть в библиотеке thread.rb, которую мы еще будем рассматривать).

И все же в некотором смысле они встроены в Ruby. Ведь класс Array реализует всё, что нужно для того, чтобы рассматривать его как стек или очередь. Стек организован по принципу «последним пришел, первым обслужен» (LIFO — last-in first-out). Традиционный пример — стопка подносов на подпружиненной подставке в кафетерии: подносы кладутся сверху и сверху же снимаются.

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

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

Но можно без труда определить класс Stack так, что к элементам можно будет обращаться только законно. И мы покажем, как это сделать.

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

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

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

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

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

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

 

9.2.1. Более строгая реализация стека

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

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 возвращает элемент, находящийся на вершине стека, не выталкивая его.

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

 

9.2.2. Обнаружение несбалансированных скобок

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

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 и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

 

9.2.3. Стек и рекурсия

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

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

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

Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 264-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")

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

 

9.2.4. Более строгая реализация очереди

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

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, что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.

Разумеется, класс Queue в библиотеке thread.rb безопасен относительно потоков. Если вы хотите реализовать такой же класс Stack, рекомендую взять Queue в качестве отправной точки. Потребуется внести не так много изменений.

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

 

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

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

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

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

 

9.3.1. Реализация двоичного дерева

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

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

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

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insert будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.

Листинг 9.1. Вставка и обход дерева в ширину

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.3.2. Сортировка с помощью двоичного дерева

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

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

Листинг 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

 

9.3.3. Использование двоичного дерева как справочной таблицы

Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 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 (не найдено).

 

9.3.4. Преобразование дерева в строку или массив

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

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.4.1. Реализация графа в виде матрицы смежности

Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса ZArray (см. раздел 8.1.26). Это нужно для того, чтобы новые элементы по умолчанию получали значение 0. Также мы унаследовали классу TriMatrix (см. раздел 8.1.7), чтобы получить нижнетреугольную матрицу.

Листинг 9.3. Матрица смежности

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.2. Является ли граф связным?

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

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

Листинг 9.4. Выяснение того, является ли граф связным

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?, с которым мы еще не встречались. Он определен в разделе 9.4.4.

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

 

9.4.3. Есть ли в графе эйлеров цикл?

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

В немецком городе Кенигсберг был остров посередине реки. С двумя берегами остров связывало семь мостов. Горожане хотели знать, можно ли обойти город так, чтобы побывать на каждом мосту ровно один раз и вернуться в исходную точку. В 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

 

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 для генерирования, визуализации и манипулирования графами». Мы его, впрочем, не изучали; пока еще не вышла даже официальная альфа-версия.

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