Class: DS::Graph
- Inherits:
-
Object
- Object
- DS::Graph
- Defined in:
- lib/ds/graphs/graph.rb
Direct Known Subclasses
Constant Summary collapse
- Infinity =
1 << 64
Class Method Summary collapse
-
.create(edges) ⇒ Object
Create new graph from array of edges.
Instance Method Summary collapse
- #add(x, y) ⇒ Object
- #add_edges(edges) ⇒ Object
- #bfs(s) ⇒ Object
-
#degree(x) ⇒ Object
Returns vertex degree.
- #each_edge(&block) ⇒ Object
- #each_vertex(&block) ⇒ Object
- #edge?(x, y) ⇒ Boolean
- #edge_size ⇒ Object
- #get_edge(x, y) ⇒ Object
-
#initialize(edges, store = :list) ⇒ Graph
constructor
Create new graph from array of edges.
- #neighbors(v) ⇒ Object
- #remove(x, y) ⇒ Object
- #vertex_size ⇒ Object
Constructor Details
#initialize(edges, store = :list) ⇒ 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 17 18 |
# File 'lib/ds/graphs/graph.rb', line 9 def initialize(edges,store = :list) case store when :matrix @g = GraphAsMatrix.new(edges) when :tri_matrix @g = GraphAsTriMatrix.new(edges) else @g = GraphAsList.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.
22 23 24 |
# File 'lib/ds/graphs/graph.rb', line 22 def self.create(edges) new(edges,:tri_matrix) end |
Instance Method Details
#add(x, y) ⇒ Object
26 27 28 |
# File 'lib/ds/graphs/graph.rb', line 26 def add(x,y) @g.add(x,y) end |
#add_edges(edges) ⇒ Object
81 82 83 |
# File 'lib/ds/graphs/graph.rb', line 81 def add_edges(edges) @g.add_edges(edges) end |
#bfs(s) ⇒ Object
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
# File 'lib/ds/graphs/graph.rb', line 46 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. Second parameter determines direction - :in incoming edges, :out - outcoming edges, :all - incoming and outcoming edges.
87 88 89 |
# File 'lib/ds/graphs/graph.rb', line 87 def degree x @g.degree x end |
#each_edge(&block) ⇒ Object
38 39 40 |
# File 'lib/ds/graphs/graph.rb', line 38 def each_edge &block @g.each_edge &block end |
#each_vertex(&block) ⇒ Object
34 35 36 |
# File 'lib/ds/graphs/graph.rb', line 34 def each_vertex &block @g.each_vertex &block end |
#edge?(x, y) ⇒ Boolean
91 92 93 |
# File 'lib/ds/graphs/graph.rb', line 91 def edge? x,y @g.edge? x,y end |
#edge_size ⇒ Object
103 104 105 |
# File 'lib/ds/graphs/graph.rb', line 103 def edge_size @g.vmax+1 end |
#get_edge(x, y) ⇒ Object
95 96 97 |
# File 'lib/ds/graphs/graph.rb', line 95 def get_edge x, y @g.get_edge x,y end |
#neighbors(v) ⇒ Object
42 43 44 |
# File 'lib/ds/graphs/graph.rb', line 42 def neighbors v @g.neighbors v end |
#remove(x, y) ⇒ Object
30 31 32 |
# File 'lib/ds/graphs/graph.rb', line 30 def remove(x,y) @g.remove(x,y) end |
#vertex_size ⇒ Object
99 100 101 |
# File 'lib/ds/graphs/graph.rb', line 99 def vertex_size @g.vertex_size end |