9.4. Графы. Глава 9. Более сложные структуры данных. Программирование на языке Ruby.

Программирование на языке Ruby.

9.4. Графы.

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

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

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

def [](x,y).

if x > y.

@store[x,y].

elsif x < y.

@store[y,x].

else.

end.

def []=(x,y,v).

if x > y.

@store[x,y]=v.

elsif x < y.

@store[y,x]=v.

else.

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.

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.

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.

if l.size < @max.

false.

else.

true.

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.

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

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

Оглавление.