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

Нижеприведенный пример основан на двух предыдущих. В листинге 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

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

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

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