Search for the longest path in a graph

Question

I am trying to solve a program where I need to find the maximum number of cities associated for a specific list of routes.

for example: if a given route is [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] then the maximum number of cities will be 4 I can’t visit the city that I have already visited.

I need ideas on how to move forward.

Currently, I thought that if I can create a dictionary with cities as a key and how many other cities related to its value, I will get somewhere near the solution (hopefully). for example: My dictionary will be {'1': ['2', '11'], '4': ['11'], '2': ['4']} for the above input. I want to help continue and guide if I missed something.

Answer 1

You can use defaultdict to create your own “chart” from the list of edges / paths:

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

Conclusion:

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

Note that I added edges in both directions, since you are working with an undirected graph. So with edge (a, b), G[a] will include b , and G[b] will include a .

From this, you can use an algorithm, such as depth search or breadth-first search , to find all the paths on the chart.

In the following code, I used DFS:

 def DFS(G,v,seen=None,path=None): if seen is None: seen = [] if path is None: path = [v] seen.append(v) paths = [] for 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 

What you can use with:

 G = defaultdict(list) for (s,t) in edges: G[s].append(t) G[t].append(s) print DFS(G, '1') 

Conclusion:

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

So, the complete code with the last bit that shows the longest path:

 from collections import defaultdict def DFS(G,v,seen=None,path=None): if seen is None: seen = [] if path is None: path = [v] seen.append(v) paths = [] for 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 by edges edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] # Build graph dictionary G = defaultdict(list) for (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) for p in all_paths) max_paths = [p for p in all_paths if len(p) == max_len] # Output print("All Paths:") print(all_paths) print("Longest Paths:") for p in max_paths: print(" ", p) print("Longest Path Length:") print(max_len) 

Conclusion:

  All 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. The "starting point" of your search is determined by the second argument to the DFS function, in which case it is '1' .

---

Update: As discussed in the comments, the above code assumes you have a starting point (in particular, the code uses a node labeled '1' ).

A more general method, if you do not have such a starting point, is to do a search starting at each node and take the longest one. (Note: you could actually be smarter than that)

Row change

 all_paths = DFS(G, '1') 

to

 all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps] 

will give you the longest path between any two points.

(This is a silly list comprehension, but it only allows me to update one line. Simply put, this is equivalent to the following:

 all_paths = [] for node in set(G.keys()): for path in DFS(G, node): all_paths.append(path) 

or

 from itertools import chain all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G))) 

)

Answer 2

Here is my code that works for input in the example, but if I adjust the input a bit, the code will not be able to indicate the correct number of cities.

 def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) #had to do this for the key error that i was getting if the start doesn't #have any val. if isinstance(start,str) and start not in graph.keys(): pass else: for next in set(graph[start]) - visited: dfs(graph, next, visited) return visited def maxno_city(input1): totalcities = [] max_nocity = 0 routedic = {} #dup = [] rou = [] for cities in input1: cities = cities.split('#') totalcities.append(cities) print (totalcities) for i in totalcities: if i[0] in routedic.keys(): routedic[i[0]].append(i[1]) else: routedic.update({i[0]:[i[1]]}) print(routedic) keys = routedic.keys() newkeys = [] for i in keys: newkeys.append(i) print (newkeys) newkeys.sort() print (newkeys) expath = dfs(routedic,newkeys[0]) return(len(expath)) 

The output for the above input is 4 , and I get 4 , but if the input changes as follows: ['1#2','2#3','1#11','3#11','4#11','4#5','5#6','5#7','6#7','4#12','8#12','9#12','8#10','9#10',8#9] My code does not work.

Thanks LearningNinja: D