Class: FindBeads::BeadClumping::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/find_beads/bead_clumps.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



85
86
87
 
# File 'lib/find_beads/bead_clumps.rb', line 85

def initialize
	@vertices = {}
end

Instance Method Details

#add_edge_between(l0, l1) ⇒ Object 



111
112
113
 
# File 'lib/find_beads/bead_clumps.rb', line 111

def add_edge_between(l0, l1)
	self[l0].connect(self[l1])
end

#add_vertex(v) ⇒ Object 



89
90
91
 
# File 'lib/find_beads/bead_clumps.rb', line 89

def add_vertex(v)
	@vertices[v.label]= v
end

#build_connected_dfs(current, visited) ⇒ Object 



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
 
# File 'lib/find_beads/bead_clumps.rb', line 120

def build_connected_dfs(current, visited)

	visited << current

	current.each do |e|

		[:v0, :v1].each do |vi|

			v = e.send(vi)

			if v.nil?

				puts e.inspect

				raise

			end

			unless visited.include?(v) then

				build_connected_dfs(v, visited)

			end

		end

	end

	visited

end

#connected?(l0, l1) ⇒ Boolean

Returns:

  • (Boolean) 


115
116
117
118
 
# File 'lib/find_beads/bead_clumps.rb', line 115

def connected?(l0, l1)
	sg = get_connected_subgraph(l0)
	sg.include?(self[l1])
end

#direct_connected?(l0, l1) ⇒ Boolean

Returns:

  • (Boolean) 


107
108
109
 
# File 'lib/find_beads/bead_clumps.rb', line 107

def direct_connected?(l0, l1)
	self[l0].connected_to? self[l1]
end

#each(&b) ⇒ Object 



101
102
103
 
# File 'lib/find_beads/bead_clumps.rb', line 101

def each(&b)
	@vertices.each &b
end

#get_connected_subgraph(l0) ⇒ Object 



152
153
154
155
156
 
# File 'lib/find_beads/bead_clumps.rb', line 152

def get_connected_subgraph(l0)

	build_connected_dfs(self[l0], Set.new)

end

#new_vertex(l) ⇒ Object 



93
94
95
 
# File 'lib/find_beads/bead_clumps.rb', line 93

def new_vertex(l)
	@vertices[l] = Vertex.new(l)
end

#vertex(label) ⇒ Object Also known as: [] 



97
98
99
 
# File 'lib/find_beads/bead_clumps.rb', line 97

def vertex(label)
	@vertices[label]
end