Commitb561094

committed

Adding node consumer support on graph BFS

1 parent0b42d46 commitb561094Copy full SHA for b561094

File tree

+20

-3

lines changed

+20

-3

lines changed

Lines changed: 7 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -25,12 +25,13 @@ def initialize(visited, parents, distances)`
`25`	`25`	`##`
`26`	`26`	`# Performs a breadth-first search for the provided graph, starting at the given node.`
`27`	`27`	`# Returns the search result (see GraphBfsResult).`
	`28`	`+# Nodes are consumed upon discovery using the provided node consumer (nothing, by default).`
`28`	`29`	`#`
`29`	`30`	`# The algorithm has a time complexity of O(\|V\| + \|E\|), where:`
`30`	`31`	`# - \|V\| is the number of nodes in the graph;`
`31`	`32`	`# - \|E\| is the number of edges in the graph.`
`32`	`33`
`33`		`-defbfs(graph,start_node)`
	`34`	`+defbfs(graph,start_node,node_consumer=method(:do_nothing_on_node))`
`34`	`35`	`seen=Set[]`
`35`	`36`	`visited=Set[]`
`36`	`37`	`parents={start_node=>nil}`
`@@ -41,6 +42,7 @@ def bfs(graph, start_node)`
`41`	`42`	`q.push(start_node)`
`42`	`43`	`untilq.empty?`
`43`	`44`	`node=q.pop`
	`45`	`+node_consumer.call(node)`
`44`	`46`	`forneighboringraph.neighbors(node)`
`45`	`47`	`unlessseen.include?(neighbor)`
`46`	`48`	`seen.add(neighbor)`
`@@ -54,3 +56,7 @@ def bfs(graph, start_node)`
`54`	`56`
`55`	`57`	`GraphBfsResult.new(visited,parents,distances)`
`56`	`58`	`end`
	`59`	`+`
	`60`	`+private`
	`61`	`+defdo_nothing_on_node(node)`
	`62`	`+end`

Lines changed: 13 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -18,7 +18,7 @@ def test_bfs_visits_single_graph_node`
`18`	`18`	`}`
`19`	`19`	`end`
`20`	`20`
`21`		`-deftest_bfs_visits_undirected_graph_fully`
	`21`	`+deftest_bfs_visits_graph_fully`
`22`	`22`	`graph=UnweightedGraph.new(nodes:[:u,:v,:w,:x],directed:false)`
`23`	`23`	`graph.add_edge(:u,:v)`
`24`	`24`	`graph.add_edge(:u,:w)`
`@@ -41,7 +41,7 @@ def test_bfs_visits_undirected_graph_fully`
`41`	`41`	`}`
`42`	`42`	`end`
`43`	`43`
`44`		`-deftest_bfs_visits_undirected_graph_partially`
	`44`	`+deftest_bfs_visits_graph_partially`
`45`	`45`	`graph=UnweightedGraph.new(nodes:[:u,:v,:w,:x,:y,:z],directed:false)`
`46`	`46`	`graph.add_edge(:u,:v)`
`47`	`47`	`graph.add_edge(:w,:x)`
`@@ -64,4 +64,15 @@ def test_bfs_visits_undirected_graph_partially`
`64`	`64`	`:z=>2`
`65`	`65`	`}`
`66`	`66`	`end`
	`67`	`+`
	`68`	`+deftest_bfs_visits_with_node_consumer`
	`69`	`+graph=UnweightedGraph.new(nodes:[:u,:v,:w],directed:false)`
	`70`	`+graph.add_edge(:u,:v)`
	`71`	`+graph.add_edge(:u,:w)`
	`72`	`+`
	`73`	`+visit_order=[]`
	`74`	`+bfs(graph,:w,->(node){visit_order.append(node)})`
	`75`	`+`
	`76`	`+assertvisit_order ==[:w,:u,:v]`
	`77`	`+end`
`67`	`78`	`end`

Comments

(0)