.. _directed-acyclic-graph: Directed Acyclic Graph (DAG) =========================================================== A directed graph that contains no cycles is called a **Directed Acyclic Graph (DAG)**. These graphs are widely used in applications such as task scheduling, dependency resolution, and data processing pipelines. Since no cycles exist, we can topologically sort the graph's nodes. .. code-block:: python def has_cycle(graph): # Function to check for cycles visited = set() recursion_stack = set() def dfs(node): if node not in visited: visited.add(node) recursion_stack.add(node) for neighbor in graph.get(node, []): if neighbor not in visited and dfs(neighbor): return True elif neighbor in recursion_stack: return True recursion_stack.remove(node) return False for node in graph: if dfs(node): return True return False .. figure:: /images/dag.png :align: center :width: 60% :alt: An example of a Directed Acyclic Graph (DAG) .. Definition 3.3.1 (DAG) .. -------------------------------------------- .. فرض کنید یک بازی تفنگی داریم. سازنده بازی قرار است برای هر دست از بازی, تاریخچه آن دست از بازی را ذخیره کند. به عبارتی اگر نفر .. :math:`A` .. نفر .. :math:`B` .. را کشت, یک یال جهت دار از .. :math:`A` .. به .. :math:`B` .. رسم می‌کنیم. .. با فرض اینکه دو نفر نمی‌توانند همزمان همدیگر را بکشند, گرافی که این کاربر ها با یکدیگر تشکیل می‌دهند یک گراف جهت دار بدون دور است(چرا؟). .. همانطور که از اسم بخش مشخص است, به گراف جهت داری که دور نداشته باشد یک گراف جهت دار بدون دور یا به اصطلاح .. :math:`DAG` .. (directed acyclic graph) .. گوییم. Definition 3.3.1 (DAG) -------------------------------------------- Suppose we have a shooter game. The game developer must save the history of each game round. Specifically, if player :math:`A` kills player :math:`B`, we draw a directed edge from :math:`A` to :math:`B`. Assuming two players cannot kill each other simultaneously, the graph formed by these players will be a directed acyclic graph (why?). As implied by the section title, a directed graph without cycles is called a *directed acyclic graph* or, using its common acronym, :math:`DAG` (directed acyclic graph). .. An Important Property ----------------------------------------- **Theorem:** In every tree, the number of vertices of degree one is at least two. **Proof:** We use induction on the number of vertices (n). - For *n = 1*: The single vertex has degree zero, which is a contradiction since the theorem states at least two vertices of degree one. Hence, this case is trivial. - For *n = 2*: Both vertices have degree one, satisfying the theorem. Assume the theorem holds for all trees with *k* vertices. Consider a tree *T* with *k + 1* vertices. Remove a leaf vertex *v* (degree one) and its incident edge. The remaining graph *T - v* is a tree with *k* vertices. By the induction hypothesis, *T - v* has at least two vertices of degree one. Now, reattach *v* to its parent *u* in *T*. Two cases arise: 1. If *u* had degree one in *T - v*, its degree becomes two in *T*. Thus, the number of leaves decreases by at most one (since *v* is added as a new leaf). 2. If *u* had degree ≥ 2 in *T - v*, attaching *v* increases its degree but does not reduce the number of leaves. In both cases, *T* retains at least two leaves. Hence, the theorem holds by induction. **Example:** In the following code, we count leaves in a tree: .. code-block:: python def count_leaves(tree): # Create a tree with n vertices leaves = 0 for vertex in tree.vertices: # The cost of organizing the ceremony if vertex.degree == 1: leaves += 1 return leaves # Currently in the queue queue = initialize_queue(root) .. figure:: images/tree_deg.png :align: center **Note:** The above figure illustrates a tree with three leaves (vertices 1, 2, and 4). .. raw:: html **Theorem 3.3.2** ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ **Statement:** If :math:`G` is a directed acyclic graph (DAG), then the vertices of :math:`G` can be ordered as :math:`v_{1}, v_{2}, ..., v_{n}` such that if the edge :math:`(v_{i}, v_{j})` exists in the graph, then :math:`i < j`. (See Figure 1 and Figure 2. Figure 2 shows a vertex ordering for the graph in Figure 1.) .. figure:: /_static/dot/DAG_Random.svg :width: 25% :align: center :alt: اگه اینترنت یارو آشغال باشه این میاد .. figure:: /_static/dot/DAG_Sorted.svg :width: 50% :align: center :alt: اگه اینترنت یارو آشغال باشه این میاد **Proof:** We prove this theorem using induction. The base case is :math:`n = 1`, where the graph has a single vertex. The statement trivially holds here. By Theorem 3.1.2 (proven in our earlier definitions of graphs), :math:`G` contains a vertex with in-degree :math:`0` (since if all vertices had an in-degree of at least 1, the graph would contain a cycle, contradicting the assumption). Let :math:`d^{-}(x) = 0`. Place vertex :math:`x` at position :math:`v_{1}` and remove it from the graph (along with all its connected edges). Since the original graph had no cycles, removing :math:`x` will not create any cycles, preserving the induction hypothesis. By induction, the remaining graph can be ordered as :math:`v_{2}, v_{3}, ..., v_{n}` to satisfy the condition. We append this ordering after :math:`v_{1} = x`. We now verify that this ordering satisfies the theorem’s condition. For vertices :math:`v_{2}, v_{3}, ..., v_{n}`, the condition holds by the induction hypothesis. For :math:`v_{1}`, the condition is also satisfied because :math:`v_{1}` has no incoming edges. Thus, the theorem is proven. **Note:** An intuitive interpretation of this theorem is that the vertices of a DAG can be arranged in a linear order such that all edges point in the same direction (e.g., left to right or right to left). This ordering is called a **topological sort** or **topological order**! .. _topological_sort: Topological Sorting ----------------------------------------- Topological sorting is an ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This ordering is not necessarily unique. Applications of topological sorting include task scheduling, course prerequisites, and dependency resolution in build systems. Algorithm ~~~~~~~~~~ A common algorithm for topological sorting is based on depth-first search (DFS). The steps are as follows: 1. Perform DFS traversal of the graph 2. After visiting all neighbors of a vertex, add it to a stack 3. The final topological order is the reverse of the stack Example implementation in Python: .. code-block:: python def topological_sort(graph): # Function for topological sort using DFS visited = set() stack = [] def dfs(node): if node in visited: return visited.add(node) for neighbor in graph[node]: # barresi hame hamsayaha dfs(neighbor) stack.append(node) # ezafe kardan be stack bad az bazgasht for node in graph: dfs(node) return stack[::-1] # baraks kardane stack baraye daryafte tartib .. note:: The graph must be a DAG for topological sorting to be possible. If the graph contains cycles, no valid topological order exists. .. image:: images/topological_sort_example.png :alt: Example of topological sorting :align: center .. _topological_sorting_algorithm: Topological Sorting Algorithm ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This algorithm is the same as the :math:`DFS` algorithm. Simply, when finishing the traversal of a vertex, we push it onto a stack (here, to improve the program's speed, we did not use a stack. It is recommended to minimize stack usage). .. Proof of Algorithm Correctness ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose the order provided by the algorithm is as follows: :math:`v_{1}, v_{2}, ..., v_{n}`. Consider the following lemma: **Lemma 1:** When we place a vertex :math:`x` in the array, all vertices reachable from :math:`x` (i.e., all vertices :math:`v` such that there is a path from :math:`x` to :math:`v`) must have already been traversed and placed in the array! (Why?) To prove the above algorithm, we use proof by contradiction and **Lemma 1**. Assume the order we obtained is not valid. That is, there exist :math:`i < j` such that the edge :math:`(v_{i}, v_{j})` belongs to the graph (i.e., an edge from left to right). But this is impossible! Because when :math:`v_{i}` is placed in the array, according to **Lemma 1**, all vertices reachable from :math:`v_{i}` must have already been placed in the array. However, there is an edge (and trivially a path) from :math:`v_{i}` to :math:`v_{j}`, yet :math:`v_{j}` has not been placed in the array! This contradicts **Lemma 1**. Therefore, the assumption is false, and such :math:`i, j` cannot exist! Algorithm Complexity ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The complexity of the above algorithm is the same as the complexity of the :math:`DFS` algorithm, i.e., :math:`O(n + m)`, where :math:`m, n` are the number of vertices and edges, respectively. .. Algorithm Implementation ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The following code reads a graph as input and stores it using an adjacency matrix: .. code-block:: python :linenos: n = int(input()) # Get number of vertices m = int(input()) # Get number of edges # Create (n+1)*(n+1) adjacency matrix initialized with 0 adjacency_matrix = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): u = int(input()) # Enter edge from vertex v = int(input()) # Enter edge to vertex adjacency_matrix[u][v] = 1 adjacency_matrix[v][u] = 1 # Undirected graph .. note:: In this implementation, we used ``n+1`` instead of ``n`` for matrix dimensions to align vertex numbers with their indices (assuming vertices are numbered from 1 to n). Using standard input (``input()``) for large graphs may be inefficient. In competitive programming, it's better to use ``sys.stdin`` for faster input. The adjacency matrix representation is visualized below: .. figure:: images/adjacency_matrix.png .. code-block:: cpp #include using namespace std; const int MX = 5e5 + 5; int n, m; /// Tedad ra's ha va yal ha vector gr[MX]; /// vector mojaverat vector topologic; /// topological sort bool mark[MX]; void dfs(int v){ mark[v] = 1; for(int u: gr[v]){ if(!mark[u]) dfs(u); } topologic.push_back(v); // in array yek topological sort baraie DAG ast! } int main(){ cin >> n >> m; for(int i = 0; i < m; i++){ int v, u; cin >> v >> u; // Ra's ha 0-based hastand! gr[v].push_back(u); } // Graph vorodi bayad DAG bashad! for(int i = 0; i < n; i++) if(!mark[i]) dfs(i); // topological sort ro khoroji midahim! for(int i = 0; i < topologic.size(); i++) cout << topologic[i] << ' '; cout << endl; return 0; } .. Note 1: Note that the above algorithm produces the correct result only when the input is an acyclic graph. Later, we will describe the algorithm for detecting cycles in directed graphs. .. Note 2: The topological order obtained here has edges pointing from right to left (i.e., edges go from larger indices to smaller indices, opposite to the order stated in **Theorem 3.3.2**).