Module: GraphLab

Defined in:
lib/graphlab.rb

Defined Under Namespace

Classes: Graph, Queue, Stack, StackView, Vertex

Constant Summary collapse

@@graph = 
nil
@@visitedV = 
Array.new
@@position =

to keep track of position of vertex in canvas

Array.new
@@createdValues =

to keep track of created value

Array.new

Instance Method Summary collapse

Instance Method Details

#_dfs(v) ⇒ Object

to perform dfs with x as the starting node, recursive



166
167
168
169
170
 
# File 'lib/graphlab.rb', line 166

def _dfs(v)
	setVisitedDfs(v)
	#recursive dfs
	v.adjList.each{ |u| setVisitedDfs(u) }
end

#anim(s) ⇒ Object 



212
213
214
215
216
217
 
# File 'lib/graphlab.rb', line 212

def anim(s)
	draw_v(s.xcoord,s.ycoord, s.value,"red") 
	Canvas::Text.new(@@visitedV.to_s, 30, 600, :font => 'visitedfont')
	sleep(1.5)
	draw_v(s.xcoord,s.ycoord, s.value, "green") 
end

#bfs(s) ⇒ Object

to perform bfs with x as the starting node, using queue implementation



183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/graphlab.rb', line 183

def bfs(s)
	@@visitedV << "BFS order of visit: "
	view_graph(self)
	@q = Queue.new
	setVisitedBfs(s)
	while (!@q.isEmpty?)
		v = @q.dequeue
		adjList = v.adjList
		adjList.each { |u| setVisitedBfs(u)}
	end
	self.clearAll
	@@visitedV.clear
	return nil
end

#clearAll ⇒ Object 



208
209
210
 
# File 'lib/graphlab.rb', line 208

def clearAll
	self.vertices.each { |u| u.visited = false}
end

#dfs(s) ⇒ Object 



156
157
158
159
160
161
162
163
 
# File 'lib/graphlab.rb', line 156

def dfs(s)
	@@visitedV << "DFS order of visit: "
	view_graph(self)
	_dfs(s)
	self.clearAll
	@@visitedV.clear
	return nil
end

#draw_ed(x1, y1, adjList, val1) ⇒ Object

to call drawedge for each adj



62
63
64
 
# File 'lib/graphlab.rb', line 62

def draw_ed(x1,y1,adjList,val1)
	adjList.each { |a| draw_edge(x1,y1, a.xcoord, a.ycoord, val1, a.value)}
end

#draw_edge(x1, y1, x2, y2, val1, val2) ⇒ Object

to draw edges



67
68
69
70
71
72
73
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/graphlab.rb', line 67

def draw_edge(x1,y1,x2,y2, val1, val2)
	Canvas::Line.new(x1,y1,x2,y2)
	arrowLengthx = (x2-x1)
	arrowLengthx = arrowLengthx.abs
	arrowLengthx = (arrowLengthx - 9.0)*0.03
	arrowLengthy = (y2-y1)
	arrowLengthy = arrowLengthy.abs 
	arrowLengthy = (arrowLengthy - 9.0)*0.03		
	#to mark the directed graph from the source to the adj node e.g. node 5 had adj node 4, mark will be *4
	x5= 0.0
	y5= 0.0
	distnce = 9.0
	dist = 7.0
	if(arrowLengthx < arrowLengthy && (arrowLengthx/0.03) >= 60)
		distnce = 8.8
		dist = 7.0
	elsif(arrowLengthx < arrowLengthy)
		distnce = 2.8
		dist = 2.5
	elsif(arrowLengthx > arrowLengthy && (arrowLengthy/0.03) >= 60)
		distnce =8.8
		dist = 7.0
	elsif(arrowLengthx > arrowLengthy)
		distnce = 2.8
		dist = 2.2
	end
	
	if(x2<x1 && y1>y2)
		x5 = ((x1-x2)/distnce)+x2
		y5 = ((y1-y2)/distnce)+y2
	elsif(x2<x1 && y1<y2) 
		x5 = ((x1-x2)/distnce)+x2
		y5 = y2-((y2-y1)/distnce)
	elsif(x2>x1 && y1<y2)
		x5 = x2-((x2-x1)/distnce)
		y5 = y2-((y2-y1)/distnce)
	elsif(x2>x1 && y1>y2)
		x5 = x2-((x2-x1)/distnce)
		y5 = ((y1-y2)/distnce)+y2
	end
	x0= 0.0
	y0= 0.0
	gradient =(((y2*-1.0)-(y1*-1.0))/(x2-x1))
	c= (y2*-1.0)-(gradient*x2)
	if(x2<x1 && y1>y2)
		x0 = ((x1-x2)/dist)+x2
		y0 = ((y1-y2)/dist)+y2
	elsif(x2<x1 && y1<y2) 
		x0 = ((x1-x2)/dist)+x2
		y0 = y2-((y2-y1)/dist)
	elsif(x2>x1 && y1<y2)
		x0 = x2-((x2-x1)/dist)
		y0 = y2-((y2-y1)/dist)
	elsif(x2>x1 && y1>y2)
		x0 = x2-((x2-x1)/dist)
		y0 = ((y1-y2)/dist)+y2
	end
	gradientPerpendicular = (1.0/gradient)*-1.0
	cPerpendicular = (y0*-1.0) - (gradientPerpendicular*x0)
	if(arrowLengthx < arrowLengthy && arrowLengthx >= 60)
		arrl = arrowLengthx
		x3 = x0 - arrl
		y3 = (x3*gradientPerpendicular + cPerpendicular)*-1.0
		x4 = x0 + arrl
		y4 = (x4*gradientPerpendicular + cPerpendicular)*-1.0
	elsif(arrowLengthx < arrowLengthy)
		arrl = 9.0
		x3 = x0 - arrl
		y3 = (x3*gradientPerpendicular + cPerpendicular)*-1.0
		x4 = x0 + arrl
		y4 = (x4*gradientPerpendicular + cPerpendicular)*-1.0
	elsif(arrowLengthx > arrowLengthy && arrowLengthy >=60)
		arrl = arrowLengthy
		y3 = (-y0 - arrl)*-1.0
		x3 = (-y3-cPerpendicular)/gradientPerpendicular
		y4 = (-y0 + arrl)*-1.0
		x4 = (-y4-cPerpendicular)/gradientPerpendicular
	elsif(arrowLengthx > arrowLengthy)
		arrl = 9.0
		y3 = (-y0 - arrl)*-1.0
		x3 = (-y3-cPerpendicular)/gradientPerpendicular
		y4 = (-y0 + arrl)*-1.0
		x4 = (-y4-cPerpendicular)/gradientPerpendicular
	
	end
	Canvas::Line.new(x3,y3,x5,y5)
	Canvas::Line.new(x4,y4,x5,y5)
end

#draw_graph(g) ⇒ Object

called by view graph, to draw GRAPH, calls draw vertices and draw edge



46
47
48
49
50
51
52
53
 
# File 'lib/graphlab.rb', line 46

def draw_graph(g)
	v = g.vertices
	#to draw edges
	v.each { |vertex| draw_ed(vertex.xcoord,vertex.ycoord, vertex.adjList, vertex.value)}
	
	#to draw the vertices
	v.each { |x| draw_v(x.xcoord,x.ycoord, x.value,"gray") }
end

#draw_v(x, y, value, color) ⇒ Object

to draw vertices



56
57
58
59
 
# File 'lib/graphlab.rb', line 56

def draw_v(x,y,value,color)
	Canvas::Circle.new(x, y, 18, :fill => color)
	Canvas::Text.new(value, (x-8), (y-8), :font => 'bucketfont')
end

#graph ⇒ Object 



41
42
43
 
# File 'lib/graphlab.rb', line 41

def graph
	@@graph
end

#setVisitedBfs(u) ⇒ Object 



198
199
200
201
202
203
204
205
206
 
# File 'lib/graphlab.rb', line 198

def setVisitedBfs(u)
	if(!u.isVisited?)
		u.visited = true
		p u
		@@visitedV << u
		anim(u)
		@q.enqueue(u)
	end
end

#setVisitedDfs(u) ⇒ Object 



172
173
174
175
176
177
178
179
180
 
# File 'lib/graphlab.rb', line 172

def setVisitedDfs(u)
	if(!u.isVisited?)
		u.visited = true
		p u
		@@visitedV << u
		anim(u)
		_dfs(u)
	end
end

#topsort(graph) ⇒ Object

:begin :topsort



624
625
626
627
628
629
630
631
632
633
634
 
# File 'lib/graphlab.rb', line 624

def topsort(graph)
  graph.clearAll
  s = Stack.new      
  for i in 0..graph.vertices.length-1
    vi = graph.vertices[i]
    if !vi.isVisited?
      topsort_dfs(vi, s)
    end
  end
  return s
end

#topsort_dfs(vertex, stack) ⇒ Object

:begin :topsort_dfs



638
639
640
641
642
643
644
645
646
647
 
# File 'lib/graphlab.rb', line 638

def topsort_dfs(vertex, stack)	
  visit(vertex)
  for i in 0..(vertex.adjList.length-1)
    neighbor = vertex.adjList[i]
    if(!neighbor.isVisited?)
      topsort_dfs(neighbor, stack)
    end
  end
  stack.push(vertex)
end

#view_graph(graph) ⇒ Object

method to view graph



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/graphlab.rb', line 25

def view_graph(graph)
	@@graph = graph
	raise "Value must be a Graph!" if graph.class != GraphLab::Graph
	# Initializes the canvas and font type
	Canvas.init(650, 650, "GraphLab")
	Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 14)
	Canvas::Font.new('visitedfont', :family => 'Helvetica', :size => 12)
	if (graph.vertices == nil)
		return true
	end
	if(graph.vertices != nil)
		draw_graph(graph)
	end
	return true
end

#view_stack(s, *peek) ⇒ Object

Generates the view for a stack visualization



508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
 
# File 'lib/graphlab.rb', line 508

def view_stack(s, *peek)
	# Initializes the canvas and font type
	Canvas.init(400, 400, "Stack")
	Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 11)
	
	stack = s.items

	cells = []
	values = []
	
	# Define starting height of first rectangle
	y0 = 50
	Canvas::Text.new("Stack Lab", 10, 1, {:font => :bucketfont})
	Canvas::Line.new(0, 20, 400, 20, :fill => :gray, :width => 1)
	
	# If generating a peek view, color first rectangle red, and place it on the right
	if peek[0] && stack[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'red'
		y1 = y0+3
		values << Canvas::Text.new(stack[0], 65, y0+3, {:font => :bucketfont})
		Canvas::Text.new("<- Top of the Stack", 200, y1, {:font => :bucketfont})
		
	# Else place a normal rectangle
	elsif stack[0]
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[0].fill = 'grey'
		y1 = y0+3
		values << Canvas::Text.new(stack[0], 65, y0+3, {:font => :bucketfont})
		Canvas::Text.new("<- Top of the Stack", 200, y1, {:font => :bucketfont})
	end
	
	iterations = stack.length-1
	
	# Iterate as many times as the number of elements in the array minus one. The first element is already handled above.
	iterations.times do |i|
		y0 += 25
		# Draw a rectangle and store a reference to this rectangle in the cells array
		cells << Canvas::Rectangle.new(10, y0, 60, y0+25)
		cells[i+1].fill = 'grey'
		# Draw the text value and store a reference to this value in the values array
		values << Canvas::Text.new(stack[i+1], 65, y0+3, {:font => :bucketfont})
	end
	
	if stack.length-1 > 0
		Canvas::Text.new("<- Bottom of the Stack", 200, y0+3, {:font => :bucketfont})
	end	
		
	# Store the properties of this drawing as a Struct object
	s.drawing = StackView.new(cells, values)
	return true
end

#visit(vertex) ⇒ Object

:begin :visit



617
618
619
620
 
# File 'lib/graphlab.rb', line 617

def visit(vertex)	
  vertex.visited = true
  p vertex
end