## Lecture 16. Directed Graphs
- Topological Sorting
- Successor paths
- Strongly Connected Components
---
### Undirected and Directed Graphs
- **Undirected** graph vs **Directed** graph (**digraph**)
- A directed graph is a graph in which edges have **orientations**.
<img src="https://cdn.ucode.vn/uploads/1/upload/rbOfidpv.png" class="element-left content-img" />
---
### Directed Graphs
In this chapter, we focus on two special classes of directed graphs:
- **Acyclic graphs**: There are no cycles in the graph, so there is no path from any node to itself.
- **Successor graphs**: The outdegree of each node is 1, so each node has a unique successor.
---
### Topological sorting
- A **topological sort** is an ordering of the nodes of a directed graph such that if there is a path from node $a$ to node $b$, then node $a$ appears before node $b$ in the ordering.
---
#### Topological sorting
<img src="https://cdn.ucode.vn/uploads/1/upload/dojacrfP.png" class="element-left content-img" />
- One topological sort is $[4, 1, 5, 2, 3, 6]$:
<img src="https://cdn.ucode.vn/uploads/1/upload/YBfCGije.png" class="element-left content-img" />
---
#### Topological sorting
- An **acyclic graph** (DAG) always has a topological sort.
- If the graph contains a cycle, it is not possible to form a topological sort
Note:
If the graph contains a cycle, it is not possible to form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering.
---
#### Topological sorting
- DFS can be used to both **check** if a directed graph contains a cycle and, if it does not contain a cycle, to **construct** a topological sort.
---
#### Topological sorting: algorithm
Using DFS, during the searches, the nodes have three possible states:
- state $0$: the node has not been processed (white) - initial state
- state $1$: the node is under processing (light gray) - reaches a node for the first time
- state $2$: the node has been processed (dark gray) - all successors of the node have been processed
---
#### Topological sorting: algorithm
- If the graph contains a cycle, we will find this out during the search, because sooner or later we will arrive at a node whose state is $1$ $\rightarrow$ no topological orders
- If the graph does not contain a cycle, we can construct a topological sort by adding each node to a list when the state of the node becomes $2$ $\rightarrow$ reverse order of a topological sort.
---
#### Topological sorting: example
- The search first proceeds from node $1$ to node $6$:
<img src="https://cdn.ucode.vn/uploads/1/upload/qXTkTBPg.png" class="element-left content-img" />
---
#### Topological sorting: example
- Now node $6$ has been processed, so it is added to the list. After this, also nodes $3$, $2$ and $1$ are added to the list: $[6, 3, 2, 1]$
<img src="https://cdn.ucode.vn/uploads/1/upload/IsESPlKq.png" class="element-left content-img" />
---
#### Topological sorting: example
- The next search begins at node $4$:
<img src="https://cdn.ucode.vn/uploads/1/upload/dPWIgLME.png" class="element-left content-img" />
---
#### Topological sorting: example
- The final list is $[6,3,2,1,5,4]$. The topological sort is the reverse list $[4,5,1,2,3,6]$
<img src="https://cdn.ucode.vn/uploads/1/upload/OpWvWVRZ.png" class="element-left content-img" />
- A topological sort is not unique, and there can be several topological sorts for a graph
---
#### Topological sorting: example 2
- Consider a graph with contains a cycle
<img src="https://cdn.ucode.vn/uploads/1/upload/fjUiNEBI.png" class="element-left content-img" />
---
#### Topological sorting: example 2
- The search proceeds as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/DKudcCCB.png" class="element-left content-img" />
- The search reaches node $2$ whose state is $1$, which means that the graph contains a cycle. In this example, there is a cycle $2 $\rightarrow$ 3 $\rightarrow$ 5 $\rightarrow$ 2$
---
#### Topological sorting
```python=
from collections import defaultdict
class Graph:
def __init__(self, n):
self.graph = defaultdict(list)
self.N = n
def add_edge(self, m, n):
self.graph[m].append(n)
def dfs(self, u, visited, stack):
visited[u] = True
for v in self.graph[u]:
if not visited[v]:
self.dfs(v, visited, stack)
stack.insert(0, u)
def topological_sort(self):
visited = [False] * self.N
stack = []
for node in range(self.N):
if not visited[node]:
self.dfs(node, visited, stack)
print(stack)
graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 3)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
print("The Topological Sort Of The Graph Is: ")
graph.topological_sort()
```
---
#### Kahn’s algorithm for Topological Sorting
Sefl learning
---
### DAG: Dynamic programming
If a directed graph is **acyclic**, **dynamic programming** can be applied for efficiently solving the following problems concerning paths from a starting node to an ending node:
- how many different paths are there?
- what is the shortest/longest path?
- what is the minimum/maximum number of edges in a path?
- which nodes certainly appear in any path?
---
#### DAG: Counting the number of paths
<img src="https://cdn.ucode.vn/uploads/1/upload/BNEMCrlD.png" class="element-left content-img" />
---
#### DAG: Counting the number of paths
<img src="https://cdn.ucode.vn/uploads/1/upload/BNEMCrlD.png" class="element-left content-img" />
- $1 \rightarrow$ 2 $\rightarrow$ 3 $\rightarrow 6$
- $1 \rightarrow$ 4 $\rightarrow$ 5 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow 6$
- $1 \rightarrow$ 4 $\rightarrow$ 5 $\rightarrow$ 3 $\rightarrow 6$
---
#### DAG: Counting the number of paths
- Let $paths(x)$ denote the number of paths from node $1$ to node $x$. $paths(1) = 1$
- $paths(x) = paths(a_1) + paths(a_2) + \dots + paths(a_k)$, where $a_1,a_2,\dots,a_k$ are the nodes from which there is an edge to x
---
#### DAG: Counting the number of paths
Since the graph is acyclic, the values of paths(x) can be calculated in the order of a topological
sort. A topological sort for the above graph is as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/tmorKZtL.png" class="element-left content-img" />
---
#### DAG: Counting the number of paths
Hence, the numbers of paths are as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/FaaYlBoR.png" class="element-left content-img" />
---
#### DAG: Counting the number of shortest paths
- Extend the Dijkstra’s algorithm: Dijkstra’s algorithm is a **directed, acyclic graph** that indicates for each node of the original graph the possible ways to reach the node using a shortest path from the starting node.
---
#### DAG: Counting the number of shortest paths
<img src="https://cdn.ucode.vn/uploads/1/upload/MGUUsYbr.png" class="element-left content-img" />
---
#### DAG: Counting the number of shortest paths
- The shortest paths from node 1 may use the following edges:
<img src="https://cdn.ucode.vn/uploads/1/upload/SHTNXZlo.png" class="element-left content-img" />
---
#### DAG: Counting the number of shortest paths
- Calculate the number of shortest paths from node 1 to node 5 using dynamic programming:
<img src="https://cdn.ucode.vn/uploads/1/upload/SHmvbpJS.png" class="element-left content-img" />
---
#### DAG: Representing problems as graphs
- Any dynamic programming problem can be represented as a directed, acyclic graph.
- Each node corresponds to a dynamic programming state and the edges indicate how the states depend on each other.
---
#### DAG: Representing problems as graphs
- Example: forming a sum of money $n$ using coins $\{c_1,c_2,...,c_k\}$.
- We can construct a graph where each node corresponds to a sum of money, and the edges show how the coins can be chosen.
---
#### DAG: Representing problems as graphs
- For example, for coins $\{1, 3, 4\}$ and $n = 6$, the graph is as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/bvUTKApy.png" class="element-left content-img" />
---
#### DAG: Representing problems as graphs
<img src="https://cdn.ucode.vn/uploads/1/upload/bvUTKApy.png" class="element-left content-img" />
- The shortest path from node $0$ to node $n$ corresponds to a solution with the **minimum number of coins**
- The total number of paths from node $0$ to node $n$ equals the **total number of solutions**.
---
### Successor paths
- **Successor graphs**: the outdegree of each node is $1$ (exactly one edge starts at each node)
- Successor graphs are sometimes called **functional graphs**.
---
#### Successor paths
<img src="https://cdn.ucode.vn/uploads/1/upload/dfTSoezM.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/wICHllpV.png" class="element-left content-img" />
---
#### Successor paths
<img src="https://cdn.ucode.vn/uploads/1/upload/dfTSoezM.png" class="element-left content-img" />
- We can also define a function $succ(x,k)$ that gives the node that we will reach if we begin at node $x$ and walk $k$ steps forward.
- For example, in the above graph $succ(4, 6) = 2$
---
#### Successor paths
- $succ(x,k)$ is to start at node $x$ and walk $k$ steps: $O(k)$
- Using preprocessing, can be calculated in only $O(log k)$ time.
---
#### Successor paths
- Preprocessing: precalculate all values of $succ(x,k)$ where $k$ is a **power of two**.
- $succ(x,k) = succ(x)$, for $k = 1$
- $succ(x,k) = succ(succ(x, k/2), k/2)$, for $k > 1$
---
### Strong connectivity
- A graph is **strongly connected** if there is a path from any node to all other nodes in the graph.
<img src="https://cdn.ucode.vn/uploads/1/upload/YuHhrdCR.png" class="element-left content-img" />
---
#### Strongly connected components
- The **strongly connected components** of a graph divide the graph into strongly connected parts that are as large as possible.
<img src="https://cdn.ucode.vn/uploads/1/upload/kWKSAoRB.png" class="element-left content-img" />
---
#### Strongly connected components
- The strongly connected components form an **acyclic component graph** that represents the deep structure of the original graph.
<img src="https://cdn.ucode.vn/uploads/1/upload/oAOipizE.png" class="element-left content-img" />
---
#### Strongly connected components
<img src="https://cdn.ucode.vn/uploads/1/upload/oAOipizE.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/LUgbKUkE.png" class="element-left content-img" />
---
#### Strongly connected components
<img src="https://cdn.ucode.vn/uploads/1/upload/LUgbKUkE.png" class="element-left content-img" />
- A **component graph** is an **DAG**, so it is easier to process than the original graph: topological sort, dynamic programming
---
#### Kosaraju’s algorithm
- An efficient method for finding the strongly connected components
- The algorithm performs two depth-first searches:
- The first search constructs a list of nodes according to the structure of the graph
- The second search forms the strongly connected components.
---
#### Kosaraju’s algorithm: Search 1
- Constructs a list of nodes in the order in which a depth-first search processes them.
<img src="https://cdn.ucode.vn/uploads/1/upload/kWKSAoRB.png" class="element-left content-img" />
---
#### Kosaraju’s algorithm: Search 1
<img src="https://cdn.ucode.vn/uploads/1/upload/espXTPFj.png" class="element-left content-img" />
The notation $x/y$ means that processing the node started at time $x$ and finished at time $y$.
---
#### Kosaraju’s algorithm: Search 1
Thus, the corresponding list is as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/OnXdjxbZ.png" class="element-left content-img" />
---
#### Kosaraju’s algorithm: Search 2
- Step 1: Reverses every edge in the graph.
<img src="https://cdn.ucode.vn/uploads/1/upload/kWKSAoRB.png" class="element-left content-img" width="60%" />
<img src="https://cdn.ucode.vn/uploads/1/upload/sbzmYedb.png" class="element-left content-img" width="80%"/>
Note:
- This guarantees that during the second search, we will always find strongly connected components that do not have extra nodes.
---
#### Kosaraju’s algorithm: Search 2
- Step 2: goes through the list of nodes created by the first search, in **reverse order**. Starting from node $3$.
<img src="https://cdn.ucode.vn/uploads/1/upload/OnXdjxbZ.png" class="element-left content-img" width="50%" />
---
#### Kosaraju’s algorithm: Search 2
- If a node does not belong to a component, the algorithm creates a new component and starts a depth-first search that adds all new nodes found during the search to the new component.
- Since all edges are reversed, the component does not "leak" to other parts in the graph.
<img src="https://cdn.ucode.vn/uploads/1/upload/WhwmsPIM.png" class="element-left content-img" />
---
#### Kosaraju’s algorithm: Search 2
- The next nodes in the list are nodes 7 and 6, but they already belong to a component, so the next new component begins at node 1:
<img src="https://cdn.ucode.vn/uploads/1/upload/ugHdirNO.png" class="element-left content-img" />
---
#### Kosaraju’s algorithm: Search 2
- Finally, the algorithm processes nodes 5 and 4 that create the remaining strongly connected components:
<img src="https://cdn.ucode.vn/uploads/1/upload/JiqFzPfa.png" class="element-left content-img" />
---
#### Tajan’s algorithm
Self learning
---
## The end
{"metaMigratedAt":"2023-06-17T19:46:16.425Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 16. Directed Graphs","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":14094,\"del\":119}]"}