python - finding longest path in a graph -

i trying solve program, in have find max number of cities connected given list of routes.

for eg: if given route [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] max cities connected 4 constraint can't visit city have visited.

i need ideas, in how progress.

for now, have thought if able create dictionary cities key , how many other cities connected value, somewhere near solution(i hope). eg: dictionary {'1': ['2', '11'], '4': ['11'], '2': ['4']} above given input. want proceed further , guidance if missing anything.

you can use defaultdict create "graph" list of edges/paths:

edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]  g = defaultdict(list) (s,t) in edges:     g[s].append(t)     g[t].append(s)  print g.items() 

output:

 [   ('1', ['2', '11']),    ('11', ['1', '4']),    ('2', ['1', '4']),    ('4', ['2', '11']) ] 

note added edges in both directions, since you're working undirected graph. edge (a,b), g[a] include b , g[b] include a.

from this, can use algorithm depth-first search or breadth-first search discover paths in graph.

in following code, used dfs:

def dfs(g,v,seen=none,path=none):     if seen none: seen = []     if path none: path = [v]      seen.append(v)      paths = []     t in g[v]:         if t not in seen:             t_path = path + [t]             paths.append(tuple(t_path))             paths.extend(dfs(g, t, seen[:], t_path))     return paths 

which can use with:

g = defaultdict(list) (s,t) in edges:     g[s].append(t)     g[t].append(s)  print dfs(g, '1') 

output:

 [('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')] 

so full code, final bit shows longest path:

from collections import defaultdict  def dfs(g,v,seen=none,path=none):     if seen none: seen = []     if path none: path = [v]      seen.append(v)      paths = []     t in g[v]:         if t not in seen:             t_path = path + [t]             paths.append(tuple(t_path))             paths.extend(dfs(g, t, seen[:], t_path))     return paths   # define graph edges edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]  # build graph dictionary g = defaultdict(list) (s,t) in edges:     g[s].append(t)     g[t].append(s)  # run dfs, compute metrics all_paths = dfs(g, '1') max_len   = max(len(p) p in all_paths) max_paths = [p p in all_paths if len(p) == max_len]  # output print("all paths:") print(all_paths) print("longest paths:") p in max_paths: print("  ", p) print("longest path length:") print(max_len) 

output:

 paths:    [('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')] longest paths:    ('1', '2', '4', '11')    ('1', '11', '4', '2') longest path length:    4 

note, "starting point" of search specified second argument dfs function, in case, it's '1'.

---

update: discussed in comments above code assumes have starting point in mind (specifically code uses node labelled '1').

a more general method, in case have no such starting point, perform search starting @ every node, , take overall longest. (note: in reality, smarter this)

changing line

all_paths = dfs(g, '1') 

to

all_paths = [p ps in [dfs(g, n) n in set(g)] p in ps] 

would give longest path between any 2 points.

(this silly list comprehension, allows me update single line. put more clearly, it's equivalent following:

all_paths = [] node in set(g.keys()):     path in dfs(g, node):         all_paths.append(path) 

or

from itertools import chain all_paths = list(chain.from_iterable(dfs(g, n) n in set(g))) 

).