Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import time
class MyQUEUE:
        #--------------- implementation of a queue---------------
	
	def __init__(self):
		self.store = []
		
	def enqueue(self,val):
		self.store.append(val)
		
	def dequeue(self):
		val = None
		try:
			val = self.store[0]
			if len(self.store) == 1:
				self.store = []
			else:
				self.store = self.store[1:]	
		except:
			pass
			
		return val	
		
	def IsEmpty(self):
		result = False
		if len(self.store) == 0:
			result = True
		return result
path_queue = MyQUEUE() # creating a queue queue

#--------------------BREADTH FIRST SEARCH---------------------
def BFS(graph,start,end,q):
	temp_path = [start]
	q.enqueue(temp_path)
	while q.IsEmpty() == False:
		tmp_path = q.dequeue()
		last_node = tmp_path[len(tmp_path)-1]
		#print tmp_path
		if last_node == end:
			print "VALID_PATH : ",tmp_path
		for link_node in graph[last_node]:
			if link_node not in tmp_path:
				new_path = []
				new_path = tmp_path + [link_node]
				q.enqueue(new_path)
def matrix():
    o = input('Enter order of the matrix ')
    m = [[]]
    #------------------Matrix initialization-------------------
    m = [[0 for elem in range(o)] for elem1 in range(o)]
    time.sleep(1)
    print '-----------------Enter elements in the matrix------------------- '
    #-----------------------Matrix input-----------------------
    for elem in range(o):
	print ' ENTER ELEMENTS FOR %d row ! ' % (elem + 1)
        for elem1 in range(o):
            m[elem][elem1] = input('')
    #----------------------display Matrix----------------------
    print '--------------------YOUR MATRIX ! ------------------'
    time.sleep(2)
    for elem in range(o):
        for elem1 in range(o):
            print m[elem][elem1],
            print ' ',
        print ''
    graph = {}
    l = []
    #-----------------------creating Graph---------------------
    #-------------------Converting matrix to graph-------------
    for elem in range(o):
        
        for elem1 in range(o):
             l = []
             if m[elem][elem1] == 1:
                 # below the element
                 if (elem + 1) <= (o - 1):
                     if m[elem + 1][elem1] == 1:
                         l.append(str(elem + 1) + str(elem1))
                 #above the element
                 if (elem - 1) >= 0:
                     if m[elem - 1][elem1] == 1:
                         l.append(str(elem - 1) + str(elem1))
                 # right of the element
                 if (elem1 + 1) <= (o - 1):
                     if m[elem][elem1 + 1] == 1:
                         l.append(str(elem) + str(elem1 + 1))
                 # left of the element
                 if (elem1 - 1) >= 0:
                     if m[elem][elem1 - 1] == 1:
                         l.append(str(elem) + str(elem1 - 1))
                 graph[str(elem) + str(elem1)] = l
             else:
                 graph[str(elem) + str(elem1)] = l
    print '------------GRAPH OBTAINED FROM MATRIX : -------------'
    time.sleep(2)
    print graph
    return graph
graph = matrix()
start = raw_input("Enter start index in single number eg: 23 for index (2,3) ")
end = raw_input("Enter end index in single number eg: 23 for index(2,3) ")
time.sleep(2)
print '------------PRINTING VALID PATHS ! ---------------'
time.sleep(2)
print '-----------PROGRAM ENDS IF TRAVERSAL IS NOT POSSIBLE------------'
BFS(graph,start,end,path_queue)