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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135 | SEY = 'Elizabeth Sey'
VOLTA = 'Volta Hall'
KWAPONG = 'Alexander Kwapong'
SARBAH = 'Mensah Sarbah Hall'
AKUAFO = 'Akuafo Hall'
ARCHEOLOGYa = 'Archeology Annex'
BALME = 'Balme Library'
BANI = 'Business School'
CC= 'Central Cafeteria'
CIAD = 'Centre for International Affairs'
CSG = 'Centre for Sensing and Geography'
COMMONWEALTH = 'Commonwealth Hall'
CSD = 'Crop Science Department'
DABCS = 'Department of Animal Biology and Conservation Science'
DB = 'Department of Botany'
CS = 'Department of Computer Science'
DStats = 'Department Of Status'
DZOOLOGY ='Depatment Of Zoology'
EFFUA ='Effua Sutherland Drama Studio'
Evandy='Evandy Hostel'
AGRIC='Faculty of Agric. Lecture Hall'
LAW ='Faculty of Law'
FRANK = 'Frank Tortor Chemistry Block'
HILLALIMANN = 'Hilla Limann'
IPO ='International Programmes Office'
ISH = 'International Students Hostel'
ISSER='Institute of Statistical, Social and Economic Research'
JAMES ='James Topp Yanker'
JEAN ='Jean Nelson'
JUBILEE ='Jubilee Hall'
BUSIA ='KA Busia Building'
BOOKSHOP ='Legon Bookshop'
LEGONHALL = 'Legon Hall'
LEGONHALLb = 'Legon Hall Annex B'
LEGONHALLc = 'Legon Hall Annex C'
LEGONMOSQUE = 'legon Mosque'
NBLOCK ='N-Block Lecture Hall'
NewNBLOCK = 'New N-Block Lecture Hall'
PENT = 'PENT -ALI Hall'
ARTS ='School of Performing Arts'
PHEALTH = 'School of Public Health'
ENG='School of Engineering Sciences'
SRCunion ='SRC Union Building'
ACQUINAS ='St. Thomas Acquinas Catholic Church'
TUTs ='Tutorial Office, Legon Hall'
VALCO ='Valco Trust Hospital'
graph = { SEY: [KWAPONG, SARBAH, VOLTA,VALCO],
KWAPONG: [SEY, VOLTA, SARBAH],
VOLTA: [KWAPONG, SEY, SARBAH],
SARBAH: [VOLTA, KWAPONG],
ARCHEOLOGYa:[AKUAFO,BALME],
BALME:[VOLTA, LEGONHALL, CC],
CC:[LEGONHALL, VOLTA, BALME],
CIAD:[VOLTA, LEGONHALL, AKUAFO, KWAPONG, COMMONWEALTH],
COMMONWEALTH:[VOLTA, LEGONHALL, AKUAFO, KWAPONG, CIAD,PENT],
CSD:[SARBAH, AKUAFO, JUBILEE],
DZOOLOGY:[BALME, AKUAFO, EFFUA],
EFFUA:[BALME, ISSER, Evandy],
Evandy:[AKUAFO, BALME, ENG, PENT, AGRIC],
AGRIC:[AKUAFO, BALME, LAW],
LAW:[FRANK],
FRANK:[BALME,HILLALIMANN],
HILLALIMANN:[BALME, IPO],
IPO:[AKUAFO, BALME, ISH],
ISH:[AKUAFO, BALME, ISSER],
ISSER:[SEY,KWAPONG, AKUAFO,BALME, JEAN],
JEAN:[SEY,KWAPONG, HILLALIMANN, JUBILEE],
JUBILEE:[SARBAH, AKUAFO, BUSIA],
BUSIA:[AKUAFO, BALME, LEGONHALL],
LEGONMOSQUE:[LEGONHALL, VOLTA, NewNBLOCK],
NewNBLOCK:[ISSER, ENG, PENT],
PENT:[ISSER, ENG, ARTS,COMMONWEALTH],
ARTS:[HILLALIMANN, JUBILEE, PHEALTH],
PHEALTH:[ISSER, BALME, AKUAFO, JUBILEE, ENG],
SRCunion:[SARBAH, LEGONHALL, ISH, VOLTA, BANI, ACQUINAS],
ACQUINAS:[VOLTA, LEGONHALL],
BANI:[VOLTA, LEGONHALL],
VALCO:[SARBAH, ISH, LEGONHALL, VOLTA, BANI]
}
import random
def find_path(graph, start, end, path=[]):
path = path + [start]
newp=[]
if start == end:
return path
if start not in graph:
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
#print(newpath)
newp.append(random.sample(path,2))
return newp
#return None
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if start not in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
if len(paths)==0:
newpaths = find_all_paths(graph,end,node,path)
for newpath in newpaths:
paths.append(newpath)
return paths
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
# if start not in graph:
# return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
from pprint import pprint
a=find_all_paths(graph,start=SEY,end=VOLTA)
pprint(a)
|