Class: Ogr::GraphAsList

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/graphs/graph_as_list.rb

Overview

Graph implemented as Adjency List

Instance Method Summary collapse

Constructor Details

#initialize(opts = {}) ⇒ GraphAsList

Returns a new instance of GraphAsList.



4
5
6
7
 
# File 'lib/ogr/graphs/graph_as_list.rb', line 4

def initialize(opts = {})
  @store = []
  @directed = opts[:directed].nil? ? true : false
end

Instance Method Details

#add(x, y, weight) ⇒ Object

Adds new edges to graph.



14
15
16
17
18
19
 
# 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) ⇒ Object

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



46
47
48
49
50
51
52
53
54
55
 
# 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) ⇒ Object 



57
58
59
60
61
62
63
64
65
66
 
# 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) ⇒ Boolean

Checks if two elements are connected.

Returns:

  • (Boolean) 


28
29
30
 
# File 'lib/ogr/graphs/graph_as_list.rb', line 28

def edge?(x, y)
  connected?(x, y)
end

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



33
34
35
36
 
# 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) ⇒ Object

Returns all neighbors for given vertex.



39
40
41
42
 
# 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) ⇒ Object

Removes conection between vertex x and y.



22
23
24
25
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


9
10
11
 
# File 'lib/ogr/graphs/graph_as_list.rb', line 9

def undirected?
  !@directed
end