5

The function will take in a dictionary as input, and I want to find the length of a longest path in a dictionary. Basically, if in a dictionary, key2 matches value1, and key3 matches value2, and so forth, this counts as a path. For example:

{'a':'b', 'b':'c', 'c':'d'}

In the case above, the length should be three. How would I achieve this? Or more specifically how would I compare keys to values? (it could be anything, strings, numbers, etc., not only numbers)

Many thanks in advance!

aRandomStudent
  • 101
  • 1
  • 8

2 Answers2

6

I would treat the dictionary as a list of edges in a directed acyclic graph (DAG) and use the networkx module to find the longest path in the graph:

import networkx as nx

data = {'a':'b', 'b':'c', 'c':'d'}

G = nx.DiGraph()
G.add_edges_from(data.items())
try:
  path = nx.dag_longest_path(G)
  print(path)
  # ['a', 'b', 'c', 'd']

  print(len(path) - 1)
  # 3
except nx.exception.NetworkXUnfeasible: # There's a loop!
  print("The graph has a cycle")
DYZ
  • 55,249
  • 10
  • 64
  • 93
  • This works precisely! Sorry I should've mentioned this in the original post, but is there any way of doing this without using modules? – aRandomStudent Jan 14 '17 at 01:37
  • There must be. But why? You would have to reimplement the functionality of `networkx`. – DYZ Jan 14 '17 at 01:37
  • 1
    If you still decide to go for it, a long and winding path is ahead, and here's where to start: http://stackoverflow.com/questions/21880419/how-to-find-the-longest-simple-path-in-a-graph – DYZ Jan 14 '17 at 01:40
  • @DYZ because the user could be coding in a work environment that doesn't have the networkx module. – the_constant Jan 14 '17 at 04:46
  • 1
    @Yvonne I would go with this solution. Finding longest path is [NP complete](https://en.wikipedia.org/wiki/Longest_path_problem) (similar to "traveling salesman" and you'd rather choose a well crafted solution and not a solution someone comes up in a stackoverflow answer. Otherwise you'll run into very slow run times. – hansaplast Jan 14 '17 at 20:21
  • 2
    Note: the version of `networkx` on github now supports weighted edges also :) – mathandy Aug 27 '17 at 02:21
  • this is the most efficent way I've ever test, there's 1000+ records in my data dict, the speed is really impressive, thanks! – Xiaohong Yuan Jul 25 '18 at 12:20
  • @AndyP: but that only works for *shortest path*, not the longest path? https://github.com/networkx/networkx – user177196 Jul 21 '20 at 20:05
  • **Note** that this does not support a dictionary containing a list of values. – Saurabh Aug 03 '20 at 23:41
1

If you're insisting on not importing anything you could do something like:

def find_longest_path(data):
    longest = 0
    for key in data.iterkeys():
        seen = set()
        length = -1
        while key:
            if key in seen:
                length = -1
                raise RuntimeError('Graph has loop')
            seen.add(key)
            key = data.get(key, False)
            length += 1
        if length > longest:
            longest = length

    return longest
Batman
  • 8,571
  • 7
  • 41
  • 80