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

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

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
  (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, которые позволяют перебрать все вершины и все ребра соответственно.

Оглавление книги