Graph - finding all paths between nodes

Ruby
1

Hi, I have implementation graph as a dictionary.
I done finding a path between two nodes, but I don’t know how find all
paths between two nodes. Anybody help or give me an advice?
My code:

class Graph
attr_accessor :graph

def initialize
@graph = Hash.new { |hash, key| hash[key] = [] }
end

def addEdge(a, b)
@graph[a] << b
@graph[b] << a
end

def searchPath(a, b, result)
result << a
if a == b
return result
end
@graph[a].each do |v|
if ! result.include?(v)
return searchPath(v, b, result)
end
end
end

end

g2 = Graph.new
puts g2.graph
g2.addEdge(‘a’,‘e’)
g2.addEdge(‘e’,‘f’)
g2.addEdge(‘f’,‘b’)
g2.addEdge(‘e’,‘b’)
g2.addEdge(‘a’,‘c’)
g2.addEdge(‘c’,‘b’)
puts g2.graph
p g2.searchPath(‘a’,‘b’, [])

I want to get something like below:
[[a,c,b],[a,e,b],[a,e,f,b]]

2

class Graph
attr_accessor :graph

def initialize
@graph = Hash.new { |hash, key| hash[key] = [] }
end

def addEdge(a, b)
@graph[a] << b
@graph[b] << a
end

def searchPath(a, b, result,&bl)
result = result+[a] # !! copy and add a

bl.call(result) if a == b
@graph[a].each do |v|
     searchPath(v, b, result,&bl) if ! result.include?(v)
end

end

end

g2 = Graph.new
g2.addEdge(‘a’,‘e’)
g2.addEdge(‘e’,‘b’)
g2.addEdge(‘e’,‘f’)
g2.addEdge(‘f’,‘b’)
g2.addEdge(‘a’,‘c’)
g2.addEdge(‘c’,‘b’)
p g2.graph
g2.searchPath(‘a’,‘b’, []) { |path|
puts “path : #{path.join(”, “)} / len=#{path.size}”
}

you get :

{“a”=>[“e”, “c”], “e”=>[“a”, “b”, “f”], “b”=>[“e”, “f”, “c”], “f”=>[“e”,
“b”], “c”=>[“a”, “b”]}
path : a, e, b / len=3
path : a, e, f, b / len=4
path : a, c, b / len=3

3

I want to get something like below:
[[a,c,b],[a,e,b],[a,e,f,b]]

So :

def searchPath(a, b, result,lr)
result = result+[a]
lr << result if a == b
@graph[a].each do |v|
searchPath(v, b, result,lr) if ! result.include?(v)
end
end

and then :

g2.searchPath(‘a’,‘b’, [],a=[])
p a

4

Regis d’Aubarede wrote in post #1119882:

I want to get something like below:
[[a,c,b],[a,e,b],[a,e,f,b]]

So :

def searchPath(a, b, result,lr)
result = result+[a]
lr << result if a == b
@graph[a].each do |v|
searchPath(v, b, result,lr) if ! result.include?(v)
end
end

and then :

g2.searchPath(‘a’,‘b’, [],a=[])
p a

Nice way to figure out.
Thanks.