Graph - finding all paths between nodes

ruby-talk
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', [])

···

--
Posted via http://www.ruby-forum.com/.

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]
  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}"
}

···

--
Posted via http://www.ruby-forum.com/.

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

···

--
Posted via http://www.ruby-forum.com/\.

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.

···

--
Posted via http://www.ruby-forum.com/\.