Class: Ogr::GraphAsMatrix

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

Overview

Graph implemented as Matrix

Direct Known Subclasses

GraphAsTriMatrix

Instance Method Summary collapse

Constructor Details

#initialize ⇒ GraphAsMatrix

Returns a new instance of GraphAsMatrix.



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

def initialize
  @store = Array2D.new
end

Instance Method Details

#add(x, y, weight) ⇒ Object 



8
9
10
 
# File 'lib/ogr/graphs/graph_as_matrix.rb', line 8

def add(x, y, weight)
  @store[x, y] = weight
end

#degree(x, direction = :all) ⇒ Object

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



36
37
38
39
40
41
42
43
44
 
# 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) ⇒ Object

Edge iterator



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

Checks if two elements are connected.

Returns:

  • (Boolean) 


18
19
20
 
# File 'lib/ogr/graphs/graph_as_matrix.rb', line 18

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

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



23
24
25
 
# File 'lib/ogr/graphs/graph_as_matrix.rb', line 23

def get_edge(x, y)
  @store[x, y]
end

#neighbors(v) ⇒ Object

Returns all neighbors for given vertex.



28
29
30
31
32
 
# 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) ⇒ Object

Removes conection between vertex x and y.



13
14
15
 
# File 'lib/ogr/graphs/graph_as_matrix.rb', line 13

def remove(x, y)
  @store[x, y] = 0
end