Программирование на языке Ruby
Программирование на языке Ruby читать книгу онлайн
Внимание! Книга может содержать контент только для совершеннолетних. Для несовершеннолетних чтение данного контента СТРОГО ЗАПРЕЩЕНО! Если в книге присутствует наличие пропаганды ЛГБТ и другого, запрещенного контента - просьба написать на почту [email protected] для удаления материала
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 endendmygraph = 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}Отметим, что приведенная выше реализация не допускает ребер, ведущих из некоторого узла в него же. Кроме того, два узла могут быть соединены только одним ребром.
Мы позволяем задать начальный состав ребер, передавая пары в конструктор. Кроме того, можно добавлять и удалять ребра, а также проверять наличие ребра между двумя вершинами. Метод
vmaxdegreeНаконец, имеются два итератора
each_vertexeach_edge9.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 endendmygraph = Graph.new([0,1], [1,2], [2,3], [3,0], [1,3])puts mygraph.connected? # trueputs mygraph.euler_path? # true
