As we learned, depth-first search (DFS) is suitable for determining whether a directed graph is acyclic (i.e., a DAG) due to the following statement.
Let \(G = (V, E)\) be a directed graph. Then \(G\) is a DAG if and only if there are no back edges during the depth-first search.
The task is to write a Python program that determines whether a given connected directed graph is a DAG using DFS as described above (also outlined in the notes).
To do this, first we need to find a vertex with no incoming edges. If there is none, then the graph is definitely not acyclic.
Then we start a depth-first search from this root and check if any back edges are created.
The filename to be uploaded should be called dag.py.
The program receives the input in the form of command-line argument as follows:
python3 dag.py graph.text
The first argument (in the example graph.text) is a connected, directed simple graph, which is provided in a text (.text) file as follows:
The first line of the file contains natural numbers \(N\) and \(M\) separated by spaces, where
the set of vertices of the simple graph \(G = (V, E)\) is \(V = \{0, 1, 2, \ldots, N-1\}\),
the number of edges is \(\left| E \right| = M\).
The next \(M\) lines contain pairs of numbers \(U_i\) and \(V_i\). Such a pair corresponds to a directed edge \(\{U_i, V_i\} \in E\). An edge appears only once in the file.
We suggest modifying the graph reading function from Exercise 3 to process the input. Note that there are no \(S\) and \(T\) vertices in the first line of the file now.
If the graph is a DAG, write
DAG
If not, write
Not DAG
to the terminal.
Test the completed program with the graph1.text (DAG) and graph2.text (not DAG) inputs. Also test it with other self-made test inputs!