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