Class: DS::GraphAsMatrix

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

Direct Known Subclasses

GraphAsTriMatrix

Instance Method Summary collapse

Constructor Details

#initialize(edges) ⇒ GraphAsMatrix

Returns a new instance of GraphAsMatrix.



4
5
6
7
8
9
10
11
12
13
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 4

def initialize(edges)
  @store = Array2D.new
  @max = 0

  @v = 0 #vertex count
   
  @map = [] #maps objects to matrix indexes.

  add_edges(edges)
end

Instance Method Details

#add_edges(edges) ⇒ Object

Adds new edges to graph.



23
24
25
26
27
28
29
30
31
32
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 23

def add_edges(edges)
  for e in edges
    x = @map.extend(ArrayX).push_uniq e.from
    y = @map.extend(ArrayX).push_uniq e.to

    @store[x,y] = e.weight
    @max = [@max, x, y].max
    @v = @v +  1
  end
end

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

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



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 79

def degree(x,direction=:all)
  x = @map.index(x)
  sum_in = 0
  sum_out = 0
  0.upto @max do |i|
    sum_in += 1 if @store[i,x] and @store[i,x] > 0
    sum_out += 1 if @store[x,i]  and @store[x,i] > 0
  end

  case direction
  when :all
    sum_in+sum_out
  when :in
    sum_in
  when :out
    sum_out
  end
end

#each_edge ⇒ Object

Edge iterator



105
106
107
108
109
110
111
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 105

def each_edge
  for v0 in 0..@max
    for v1 in 0..v0-1
      yield Edge.new(@map[v0],@map[v1],@store[v0,v1]) if @store[v0,v1] > 0
    end    
  end    
end

#each_vertex ⇒ Object

Vertex iterator



100
101
102
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 100

def each_vertex
  (0..@max).each {|v| yield @map[v]}
end

#edge?(x, y) ⇒ Boolean

Checks if two elements are connected.

Returns:

  • (Boolean) 


16
17
18
19
20
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 16

def edge? x,y
  v1 = @map.index(x)
  v2 = @map.index(y)
  @store[v1,v2] > 0
end

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



57
58
59
60
61
62
63
64
65
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 57

def get_edge x,y
  s = @map.index x
  t = @map.index y
  if @store[s,t] > 0
    Edge.new(@map[s], @map[t], @store[s,t])
  else
    nil
  end
end

#neighbors(v) ⇒ Object

Returns all neighbors for given vertex.



35
36
37
38
39
40
41
42
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 35

def neighbors(v)
  n = []
  v = @map.index(v)
  0.upto @max do |i|
    n << @map[i] if @store[v,i] > 0
  end
  n
end

#remove(x, y) ⇒ Object

Removes conection between vertex x and y.



45
46
47
48
49
50
51
52
53
54
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 45

def remove(x,y)
  v1 = @map.index(x)
  v2 = @map.index(y)

  @store[v1,v2] = 0
  if (degree @map[@max]) == 0
    @max -= 1
  end
  @v -= 1
end

#vertex_size ⇒ Object

Returns vertex counter.



72
73
74
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 72

def vertex_size
  @v
end

#vmax ⇒ Object 



67
68
69
 
# File 'lib/ds/graphs/graph_as_matrix.rb', line 67

def vmax
  @max
end