Class: DS::GraphAsMatrix
- Inherits:
-
Object
- Object
- DS::GraphAsMatrix
- Defined in:
- lib/ds/graphs/graph_as_matrix.rb
Direct Known Subclasses
Instance Method Summary collapse
-
#add_edges(edges) ⇒ Object
Adds new edges to graph.
-
#degree(x, direction = :all) ⇒ Object
Returns vertex degree.
-
#each_edge ⇒ Object
Edge iterator.
-
#each_vertex ⇒ Object
Vertex iterator.
-
#edge?(x, y) ⇒ Boolean
Checks if two elements are connected.
-
#get_edge(x, y) ⇒ Object
Returns Edge(x,y) if exist.
-
#initialize(edges) ⇒ GraphAsMatrix
constructor
A new instance of GraphAsMatrix.
-
#neighbors(v) ⇒ Object
Returns all neighbors for given vertex.
-
#remove(x, y) ⇒ Object
Removes conection between vertex x and y.
-
#vertex_size ⇒ Object
Returns vertex counter.
Constructor Details
#initialize(edges) ⇒ GraphAsMatrix
Returns a new instance of GraphAsMatrix.
4 5 6 7 8 9 10 11 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 4 def initialize(edges) @store = Array2D.new @max = 0 @map = OrderedSet.new #maps objects to matrix indexes. add_edges(edges) end |
Instance Method Details
#add_edges(edges) ⇒ Object
Adds new edges to graph.
14 15 16 17 18 19 20 21 22 23 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 14 def add_edges(edges) for e in edges x = @map.push e.from y = @map.push e.to @store[x,y] = e.weight @max = [@max, x, y].max 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.
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 76 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
103 104 105 106 107 108 109 110 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 103 def each_edge vertexes = @map.to_a for v0 in 0..@max for v1 in 0..v0-1 yield Edge.new(vertexes[v0],vertexes[v1],@store[v0,v1]) if @store[v0,v1] > 0 end end end |
#each_vertex ⇒ Object
Vertex iterator
97 98 99 100 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 97 def each_vertex vertexes = @map.to_a (0..@max).each {|v| yield vertexes[v]} end |
#edge?(x, y) ⇒ Boolean
Checks if two elements are connected.
62 63 64 65 66 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 62 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.
51 52 53 54 55 56 57 58 59 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 51 def get_edge x,y s = @map.index x t = @map.index y if @store[s,t] > 0 Edge.new(x, y, @store[s,t]) else nil end end |
#neighbors(v) ⇒ Object
Returns all neighbors for given vertex.
26 27 28 29 30 31 32 33 34 35 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 26 def neighbors(v) n = [] vertexes = @map.to_a v = @map.index(v) 0.upto @max do |i| n << vertexes[i] if @store[v,i] > 0 end n end |
#remove(x, y) ⇒ Object
Removes conection between vertex x and y.
38 39 40 41 42 43 44 45 46 47 48 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 38 def remove(x,y) v1 = @map.index(x) v2 = @map.index(y) vertexes = @map.to_a @store[v1,v2] = 0 if (degree vertexes[@max]) == 0 @max -= 1 end end |
#vertex_size ⇒ Object
Returns vertex counter.
69 70 71 |
# File 'lib/ds/graphs/graph_as_matrix.rb', line 69 def vertex_size @map.size end |