class Ogr::GraphAsList

Graph implemented as Adjency List

Public Class Methods

new(opts = {}) click to toggle source
# File lib/ogr/graphs/graph_as_list.rb, line 4
def initialize(opts = {})
  @store = []
  @directed = opts[:directed].nil? ? true : false
end

Public Instance Methods

add(x, y, weight) click to toggle source

Adds new edges to graph.

# File lib/ogr/graphs/graph_as_list.rb, line 14
def add(x, y, weight)
  @store[x] ||= EdgeBag.new
  @store[x].add(y, weight)
  @store[y] ||= EdgeBag.new if undirected?
  @store[y].add(x, weight) if undirected?
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_list.rb, line 46
def degree(x, direction = :all)
  r = Hash.new(0)
  (0..@store.size).each do |i|
    r[:in] += 1 if  connected?(i, x)
    r[:out] += 1 if connected?(x, i)
  end
  r[:all] = r[:in] + r[:out]
  return r[direction] / 2 if undirected?
  r[direction]
end
each_edge(vertexes) { |edge| ... } click to toggle source
# File lib/ogr/graphs/graph_as_list.rb, line 57
def each_edge(vertexes)
  @store.each_with_index do |list, i|
    list.each do |vertex|
      j = vertex[:v]
      next if i > j && undirected?
      w = get_edge(i, j)
      yield Edge.new(vertexes[i], vertexes[j], w) if w
    end
  end
end
edge?(x, y) click to toggle source

Checks if two elements are connected.

# File lib/ogr/graphs/graph_as_list.rb, line 28
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_list.rb, line 33
def get_edge(x, y)
  edge = get(x, y)
  edge[:weight] if edge
end
neighbors(x) click to toggle source

Returns all neighbors for given vertex.

# File lib/ogr/graphs/graph_as_list.rb, line 39
def neighbors(x)
  return [] unless @store[x]
  @store[x].map { |edge| edge[:v] }
end
remove(x, y) click to toggle source

Removes conection between vertex x and y.

# File lib/ogr/graphs/graph_as_list.rb, line 22
def remove(x, y)
  @store[x].remove(y)
  @store[y].remove(x) if undirected?
end
undirected?() click to toggle source
# File lib/ogr/graphs/graph_as_list.rb, line 9
def undirected?
  !@directed
end

Private Instance Methods

connected?(x, y) click to toggle source
# File lib/ogr/graphs/graph_as_list.rb, line 74
def connected?(x, y)
  !get(x, y).nil?
end
get(x, y) click to toggle source
# File lib/ogr/graphs/graph_as_list.rb, line 70
def get(x, y)
  @store[x] && @store[x].get(y)
end