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.

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