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