Class: DS::Graph

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

Direct Known Subclasses

Digraph

Constant Summary collapse

Infinity = 
1 << 64

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(edges, store = :matrix) ⇒ Graph

Create new graph from array of edges. Second parameter determines graph internal implementation: :list (Adjency List), :tri_matrix (Triangular Matrix), :matrix (Matrix).



9
10
11
12
13
14
15
16
 
# File 'lib/ds/graphs/graph.rb', line 9

def initialize(edges,store = :matrix)
  case store
  when :matrix
    @g = GraphAsMatrix.new(edges)
  when :tri_matrix
    @g = GraphAsTriMatrix.new(edges)
  end
end

Class Method Details

.create(edges) ⇒ Object

Create new graph from array of edges. Internally graph will be represented by Triangular Matrix.



20
21
22
 
# File 'lib/ds/graphs/graph.rb', line 20

def self.create(edges)
  new(edges,:tri_matrix) 
end

Instance Method Details

#add(x, y, weight = 1) ⇒ Object

Adds new edge to graph.



25
26
27
28
 
# File 'lib/ds/graphs/graph.rb', line 25

def add(x,y,weight=1)
  e = Edge.new(x,y,weight)
  add_edges([e])
end

#add_edges(edges) ⇒ Object

Adds new edges to graph.



31
32
33
 
# File 'lib/ds/graphs/graph.rb', line 31

def add_edges(edges)
  @g.add_edges(edges)
end

#bfs(s) ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/ds/graphs/graph.rb', line 74

def bfs s
  colors = {}
  parents =  {}
  res = []
  d = {}
  q = Queue.new

  @g.each_vertex do |v|
    colors[v] = :white
    parents[v] = nil
    d[v] = Infinity
  end

  colors[s] = :white
  parents[s] = nil
  d[s] = 0

  q.enqueue s

  while !q.empty?
    u = q.dequeue 
    @g.neighbors(u).each do |v|
      if colors[v] === :white
        colors[v] = :grey
        d[v] = d[u] + 1
        parents[v] = u
        q.enqueue v
      end
    end
    colors[u] = :black
    res << u
  end
  res
end

#degree(x) ⇒ Object

Returns vertex degree.



47
48
49
 
# File 'lib/ds/graphs/graph.rb', line 47

def degree x
  @g.degree x
end

#each_edge(&block) ⇒ Object 



69
70
71
 
# File 'lib/ds/graphs/graph.rb', line 69

def each_edge &block
  @g.each_edge &block
end

#each_vertex(&block) ⇒ Object 



65
66
67
 
# File 'lib/ds/graphs/graph.rb', line 65

def each_vertex &block
  @g.each_vertex &block
end

#edge?(x, y) ⇒ Boolean

Checks if two elements are connected.

Returns:

  • (Boolean) 


52
53
54
 
# File 'lib/ds/graphs/graph.rb', line 52

def edge? x,y
  @g.edge? x,y
end

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



57
58
59
 
# File 'lib/ds/graphs/graph.rb', line 57

def get_edge x, y
  @g.get_edge x,y
end

#neighbors(v) ⇒ Object

Returns all neighbors for given vertex.



42
43
44
 
# File 'lib/ds/graphs/graph.rb', line 42

def neighbors v
  @g.neighbors v
end

#remove(x, y) ⇒ Object

Removes conection between vertex x and y.



37
38
39
 
# File 'lib/ds/graphs/graph.rb', line 37

def remove(x,y)
  @g.remove(x,y) 
end

#vertex_size ⇒ Object 



61
62
63
 
# File 'lib/ds/graphs/graph.rb', line 61

def vertex_size
  @g.vertex_size
end