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

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.

9.4. Графы

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

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

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

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

9.4.1. Реализация графа в виде матрицы смежности

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

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

  ([email protected]).each {|v| yield v}

 end

 def each_edge

  for v0 in [email protected]

   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.

class Graph

 def connected?

  x = vmax

  k = [x]

  l = [x]

  for i in [email protected]

   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 году Эйлер доказал, что это невозможно. Эта классическая задача стала первой проблемой теории графов.

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