Graphs with loops

[gudeh]

Hi guys, I am working with graphs which have internal loops (or cycles) between node connections. I want to calculate the depth of each node in the graph, although my attempts always fall into infinite loops. Is there anyway I can do that with DGL? Maybe remove graph cycles some how?

Here is what I tried, which falls into an infinite loop:

            print("calculating logic depth!", self.graph.name, flush=True)
            depths = np.zeros(self.graph.number_of_nodes(), dtype=int)
            inputs = [node for node in self.graph.nodes() if self.graph.in_degrees(node) == 1 and self.graph.out_degrees(node) > 1]
            outputs = [node for node in self.graph.nodes() if self.graph.out_degrees(node) == 1 and self.graph.in_degrees(node) > 1]

            print("depths:", len(depths))
            print("inputs:", len(inputs), flush=True)
            print("outputs:", len(outputs), flush=True)

            stack = []

            for node in outputs:
                print("output node:", node, flush=True)
                stack.append((node, 0, [node]))

            while stack:
                node, depth, path = stack.pop()
                depths[node] = max(depths[node], depth)
                neighbors = self.graph.predecessors(node).numpy()
                for neighbor in neighbors:
                    if neighbor not in path and depths[neighbor] < depth + 1:
                        stack.append((neighbor, depth + 1, path + [neighbor]))

[mufeili]

You will need to first convert your graph to a directed acyclic graph. DGL does not have native support for that. You may want to check other graph analytics packages.

[gudeh]

Is there a native way in DGL to check if the graph is acyclic at least?

I will try to remove the loops when generating the data. It would be nice to have a way to confirm that on DGL level.

[gudeh]

would you say something like this would suffice:

        def is_acyclic(graph):
            try:
                nx.is_directed_acyclic_graph( graph.to_networkx() )
                return True
            except nx.NetworkXUnfeasible:
                return False

        if is_acyclic( self.graph ):
            print("The graph is acyclic.")
        else:
            print("The graph contains cycles.")

[mufeili]

Yes, you can use nx.is_directed_acyclic_graph.

[gudeh]

I believe there might be a bug when transforming from DGL to networkx, in “graph.to_networkx()”. The graph G in this example should be printed as cyclic, when it is not:

        def is_acyclic(graph):
            try:
                nx.is_directed_acyclic_graph( graph.to_networkx() )
                return True
            except nx.NetworkXUnfeasible:
                return False
        G = dgl.DGLGraph()
        G.add_nodes(3)  # Add three nodes with IDs 0, 1, and 2
        src = [0, 1, 2]  # Source nodes of the edges
        dst = [1, 2, 0]  # Destination nodes of the edges
        G.add_edges(src, dst)  # Add the edges to the graph
        if is_acyclic( G ):
            print("The graph G is acyclic.")
        else:
            print("The graph G contains cycles.")

        if is_acyclic( self.graph ):
            print("The graph self.graph is acyclic.")
        else:
            print("The graph self.graph contains cycles.")

Here is the output, I am quite sure my own graph in self.graph is cyclic also.

The graph G is acyclic.
The graph self.graph is acyclic.

[mufeili]

You need to change

nx.is_directed_acyclic_graph( graph.to_networkx() )
return True

to

return nx.is_directed_acyclic_graph( graph.to_networkx())

[gudeh]

There you go. Now I can check if I have cycles or not! Thanks a lot @mufeili