Longest Path Algorithm Implemented in Python

Here I write down the longest path algorithm implementation I did in Python language. Since finding the longest path algorithm is considered as an intractable problem, you will notice that when the number of vertexes in the graph increases the time to find the longest path increases in an exponential way.

The input graph to the program is given as a separate configuration file which also I have shown separately.

longest_path.py file

1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name           # name of the vertex  
9:            self.visited = 0          # access flag 1=visited, 0=not visited  
10:     
11:     
12:  # represents an edge in the graph  
13:  class Edge:  
14:       def __init__(self, v, u, length):  
15:            self.start = v  
16:            self.end = u  
17:            self.length = length  
18:    
19:    
20:  # read a text file and generate the graph according to declarations  
21:  def generateGraph(V, E):  
22:    
23:       file = open("graph_def_v11", "r")  
24:       line = file.readline()  
25:       line = line[:-1]  
26:       while line:  
27:            taglist = string.split(line)  
28:            if taglist[0] == 'vertex':  
29:                 V.append(Vertex(taglist[1]))  
30:            elif taglist[0] == 'edge':  
31:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
32:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
33:            line = file.readline()  
34:            line = line[:-1]            
35:       file.close()  
36:    
37:    
38:  # returns the edges list of vertex v  
39:  def pickEdgesList(v, E):  
40:       vu = []  
41:       for edge in E:  
42:            if edge.start == v.name:  
43:                 vu.append(edge)  
44:       return vu  
45:    
46:  def pickVertexByName(V, A):  
47:       for vertex in V:  
48:            if vertex.name == A:  
49:                 return vertex  
50:    
51:  def LP(V, E, A):  
52:       #print("in LP")  
53:       dist = 0  
54:       maxa = 0  
55:       v = pickVertexByName(V, A)  
56:       v.visited = 1  
57:       vu = pickEdgesList(v, E)  
58:       for edge in vu:  
59:            u = pickVertexByName(V, edge.end)  
60:            if u.visited == 0:  
61:                 dist = edge.length + LP(V, E, u.name)  
62:                 if dist > maxa:  
63:                      maxa = dist  
64:       v.visited = 0  
65:       return maxa  
66:    
67:    
68:  def main():  
69:       print('Starting Longest Path Algorithm...')       
70:       t1 = time.time()  
71:       # graph elements  
72:       V = []  
73:       E = []  
74:       generateGraph(V, E)       
75:       maxa = LP(V, E, 'a')  
76:       print 'max=', maxa  
77:       t2 = time.time()  
78:       print t2-t1  
79:    
80:    
81:  main()  

The content of the graph configuration file which is saved as graph_def is as follows.

1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python longest_path.py

cheers!