2

I'm trying to check for cycles in a directed graph. In said graph, the nodes consist of only their name, and their parent nodes (if available). For example, a simple node representation could look something similar to this:

class Node:
    name: str
    parents: list

    def __init__(self, name, parents)
        self.name = name
        self.parents = parents

A simple graph:

graph = [Node("source", []), Node("node1", ["source"]), Node("node2", ["node1", "source"]) ]

A simple graph that has a cycle in it:

graph = [Node("source", []), Node("node1", ["source", "node3"]), Node("node2", ["node1"]), Node("node3", ["node1"])]

I'm struggling to think of a way to properly detect the cycles in these situations. I'd prefer to not have to parse over the graph and create another representation with something like vertices just so I can do cycle detection, so I'm trying to explore if there are other options. I'm familiar with cycle detection algorithms using searches for nodes that have child dependency information.

I've tried to modify DFS approaches to graph searches like the one implemented below but they don't seem to catch the cycles in the graph, given that I'm only given the parent information. https://medium.com/coder-life/detect-cycle-in-a-directed-graph-undirected-graph-dcd788e91b8

I've also reviewed the solutions in Best algorithm for detecting cycles in a directed graph but I'm having a hard time applying them. Specifically, a lot of them seem to rely on having edges and an adjacency representation that allows for parents nodes to point to child nodes, but is there a way to check for cycles without having parent nodes point to their children?

Levine
  • 21
  • 4
  • Hi! The solutions given in the question you link are good. But you say you're having a hard time applying them. So it's a bit hard to help you unless you specify more precisely what is giving you a hard time. – Stef Jun 15 '23 at 10:05
  • Take for instance the depth-first-search algorithm described here: https://i.stack.imgur.com/MIlwU.png . Can you implement that for your graph? If not, why not? Can you explain what specifically is giving you trouble? – Stef Jun 15 '23 at 10:06
  • Regarding your edit *"Specifically, a lot of them seem to rely on having edges and an adjacency representation that allows for parents nodes to point to child nodes, but is there a way to check for cycles without having parent nodes point to their children?"*, it actually doesn't matter whether you have parent->child or child->parent edges in your representation. There is a cycle in the parent->child direction if and only if there is a cycle in the child-> parent direction. As long as you always follow the edges in the same direction it's fine. – Stef Jun 15 '23 at 10:12
  • Thanks for the response! I'm having trouble visualizing and implementing how to iterate through all of the edges when only given the parent node of each node. For example, if I wanted to iterate in the "explore edge (u, v)" step, how would I go about getting all of the adjacent nodes? Would I have to search through the graph for all of the nodes that have a parent of the node I'm interested in? Doing that for each node seems unnecessarily complex, so I'm wondering if there's a better way. – Levine Jun 15 '23 at 10:15
  • This is just a matter of bad definitions. When they say "all the adjacent nodes" they mean "all the nodes that are linked from here". Only follow edges in the direction of the edge. So in your case, only visit the parent nodes. – Stef Jun 15 '23 at 10:18
  • 1
    Ah, thanks for the clarification about how the algorithms apply regardless of dependency direction - that's what I originally thought, but the DFS implementation from medium of the DFS doesn't seem to be working. I'll try implementing the CLRS' pseudocode version in my code instead - thanks again! – Levine Jun 15 '23 at 10:19
  • 1
    Thank you so much - the CLRS' pseudocode version works! – Levine Jun 15 '23 at 10:48

0 Answers0