class Ogr::GraphAsMatrix

Graph implemented as Matrix

Public Class Methods

new() click to toggle source
# File lib/ogr/graphs/graph_as_matrix.rb, line 4
def initialize
  @store = Array2D.new
end

Public Instance Methods

add(x, y, weight) click to toggle source
# File lib/ogr/graphs/graph_as_matrix.rb, line 8
def add(x, y, weight)
  @store[x, y] = weight
end
degree(x, direction = :all) click to toggle source

Returns vertex degree. Second parameter determines direction - :in incoming edges, :out - outcoming edges, :all - incoming and outcoming edges.

# File lib/ogr/graphs/graph_as_matrix.rb, line 36
def degree(x, direction = :all)
  r = Hash.new(0)
  vertexes.each do |i|
    r[:in] += 1 if connected?(i, x)
    r[:out] += 1 if connected?(x, i)
  end
  r[:all] = r[:in] + r[:out]
  r[direction]
end
each_edge(vertexes) { |edge| ... } click to toggle source

Edge iterator

# File lib/ogr/graphs/graph_as_matrix.rb, line 47
def each_edge(vertexes)
  size = vertexes.size
  (0...size).each do |v0|
    (0...size).each do |v1|
      weight = @store[v0, v1]
      yield Edge.new(vertexes[v0], vertexes[v1], weight) if weight
    end
  end
end
edge?(x, y) click to toggle source

Checks if two elements are connected.

# File lib/ogr/graphs/graph_as_matrix.rb, line 18
def edge?(x, y)
  connected?(x, y)
end
get_edge(x, y) click to toggle source

Returns Edge(x,y) if exist.

# File lib/ogr/graphs/graph_as_matrix.rb, line 23
def get_edge(x, y)
  @store[x, y]
end
neighbors(v) click to toggle source

Returns all neighbors for given vertex.

# File lib/ogr/graphs/graph_as_matrix.rb, line 28
def neighbors(v)
  n = []
  vertexes.each { |i| n << i if connected?(v, i) }
  n
end
remove(x, y) click to toggle source

Removes conection between vertex x and y.

# File lib/ogr/graphs/graph_as_matrix.rb, line 13
def remove(x, y)
  @store[x, y] = 0
end

Private Instance Methods

connected?(x, y) click to toggle source
# File lib/ogr/graphs/graph_as_matrix.rb, line 59
def connected?(x, y)
  @store[x, y] > 0
end
vertexes() click to toggle source
# File lib/ogr/graphs/graph_as_matrix.rb, line 63
def vertexes
  (0..@store.size)
end