CODEWITHSUNDEEP
graphpath
arslan
arslan

Reputation: 2234

finding all simple paths between two points of a graph with cycles

I am trying to compute all simple paths between two nodes. I tried DFS and it seems DFS will not work.

The following figure make my goal more clear.

enter image description here

two nodes 'a' and 'f' is given, and have to find paths between them. for above example, there are two simple paths:

a ->b ->c ->e ->f

a ->b ->d ->e ->f

I checked some posts, but they seems don't handle cycles( without cycles my DFS works).

The graph is undirected and has cycles. I believe there is a solution for this. could anyone point me a reliable algorithm ? it would be great if such algorithm comes with pseudocode.

Thanks in advance Best,

Upvotes: 1

Views: 1353

Answers (1)

Isaac Franco Fernandes
Isaac Franco Fernandes

Reputation: 36

Here is a Ruby solution using a weighted adj matrix and avoiding cycles. It is a little messy but it seams to work. I'm testing with a graph with nodes a,b,c,d,e,f in a connection loop (like a ring) but with two extra connections (b <-> f and c <-> f) generating cycles to test the algorithm.

# Generate all paths from A to E
@grapascii =
'
   C-----D
  / \    |
 B---F---E
  \ /     
   A
'

@nodes = %w{A B C D E F}
n = -1 # represents no connection

#weighted adj matrix
@adjmat = [
    #a  b  c  d  e  f
    [n, 1, n, n, n, 1], # a
    [1, n, 3, n, n, 1], # b
    [n, 4, n, 2, n, 1], # c
    [n, n, 4, n, 1, n], # d
    [n, n, n, 1, n, 1], # e
    [1, 6, 1, n, 2, n]  # f
]

# generate a neighbors hash for easy and fast future acccess
def gen_neighbors(nodes, adjmat)
    len = nodes.length
    neighbors = {}
    for i in 0..(len - 1)
        for j in 0..(len - 1)
            if adjmat[i][j] >= 0 && i != j
                neighbors[nodes[i]] ||= []
                neighbors[nodes[i]] << {:node => nodes[j], :cost => adjmat[i][j]}
            end
        end
    end
    return neighbors
end

@neighbors = gen_neighbors(@nodes, @adjmat)

def all_paths(currpath, destnode, currcost, paths)
    #the current node is always tha last one on the current evaluated path
    currnode = currpath.last
    # just the neighbors that is nor on the current evaluated path, to avoid cycles
    current_neighbors = @neighbors[currnode].select{|n| !currpath.include?(n[:node])}

    #each neighbor is a hash with :node and :cost
    current_neighbors.each do |neighbor|
        # yes. we have to duplicate that. maybe there is a better solution...
        new_path = currpath + [neighbor[:node]]
        cost = currcost + neighbor[:cost]

        if neighbor[:node] == destnode
            #FOUND PATH
            paths << {:path => new_path, :cost => cost}
        else
            all_paths(new_path, destnode, cost, paths)
        end
    end
end

puts @grapascii

puts "NEIGHBORS HASH:"
@neighbors.each do |node, neighbors|
    neighbors_and_cost = neighbors.map{|n| "#{n[:node]}(#{n[:cost]})"}
    puts "#{node} => #{neighbors_and_cost.join(', ')}"
end


# start path with the start node
startpath = ['A']
# paths variable will hold all possible paths without cycles
paths = []
all_paths(startpath, 'E', 0, paths)

puts "PATHS:"
# sort paths by total cost(optional)
paths.sort!{|a, b| a[:cost] <=> b[:cost]}
paths.each do |path|
    puts "#{path[:path]} => #{path[:cost]}"
end

Output:

   C-----D
  / \    |
 B---F---E
  \ /     
   A
NEIGHBORS HASH:
A => B(1), F(1)
B => A(1), C(3), F(1)
C => B(4), D(2), F(1)
D => C(4), E(1)
E => D(1), F(1)
F => A(1), B(6), C(1), E(2)
PATHS:
["A", "F", "E"] => 3
["A", "B", "F", "E"] => 4
["A", "F", "C", "D", "E"] => 5
["A", "B", "F", "C", "D", "E"] => 6
["A", "B", "C", "D", "E"] => 7
["A", "B", "C", "F", "E"] => 7
["A", "F", "B", "C", "D", "E"] => 13

Upvotes: 2

Related Questions