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