Finding cycles in a dictionary of lists-CodePudding

I have a python dictionary of ids. Each id has a set of other ids to which it references. How can I find circular references within the dictionary?

An example of my dictionary is:

{1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}.

The value of each id key is a list of the other ids it references and they can't reference themselves.

So the output, if there were a circular reference, would be:

{3, 4 , 3}.

I'm struggling to figure out how to go about this as it seems like it would be a common problem! Thank you very much for anyone that helps.

CodePudding user response：

The networkx library can find cycles in your graph. You will need to instantiate a directed graph, because your links between IDs are one-way. You have multiple cycles in your graph. For instance, 3 goes to 4 and 4 goes to 3. That is also considered a cycle.

import networkx as nx

data = {1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}
graph = nx.DiGraph(data)

list(nx.simple_cycles(graph))
# returns:
[[1, 3, 4, 2], [1, 3, 2], [3, 4]]

CodePudding user response：

If you are looking for circular references of length only 2, i.e. only for pairs (i,j) such that i references j and j references i, then the code below works:

d = {1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}

for i in d:
    for j in d[i]:
        if i in d[j]:
            print("Cycle found: ", i, j)

Output:

Cycle found:  3 4
Cycle found:  4 3

The program above does the following: for each key i in the dictionary, if i references j, then check whether j also references i (i.e. whether i is also in d[j]), and if so, print i and j. You can augment the program to store (or print) (i,j) only if i < j, in order to not print each cycle twice.

If you want to also print circular references of larger lengths (such as when i references j, j references k, and k references i), then you can construct a directed graph with edge set {(i,j): i references j}, and run an algorithm (such as Johnson's algorithm) to find all elementary cycles in a digraph.