How do I check if a directed graph is acyclic?
I would try to sort the graph topologically, and if you can’t, then it has cycles.
directed-graph
how to draw directed graphs using networkx in python?
Fully fleshed out example with arrows for only the red edges: import networkx as nx import matplotlib.pyplot as plt G = nx.DiGraph() G.add_edges_from( [(‘A’, ‘B’), (‘A’, ‘C’), (‘D’, ‘B’), (‘E’, ‘C’), (‘E’, ‘F’), (‘B’, ‘H’), (‘B’, ‘G’), (‘B’, ‘F’), (‘C’, ‘G’)]) val_map = {‘A’: 1.0, ‘D’: 0.5714285714285714, ‘H’: 0.0} values = [val_map.get(node, 0.25) for node … Read more
GraphViz – How to connect subgraphs?
The DOT user manual gives the following example of a graph with clusters with edges between clusters: IMPORTANT: The initial compound=true statement is required. digraph G { compound=true; subgraph cluster0 { a -> b; a -> c; b -> d; c -> d; } subgraph cluster1 { e -> g; e -> f; } b … Read more
Best algorithm for detecting cycles in a directed graph [closed]
According to Lemma 22.11 of Cormen et al., Introduction to Algorithms (CLRS): A directed graph G is acyclic if and only if a depth-first search of G yields no back edges. This has been mentioned in several answers; here I’ll also provide a code example based on chapter 22 of CLRS. The example graph is … Read more