#!/usr/bin/env python
# coding: utf-8

# In[2]:


# %load ../../preconfig.py
get_ipython().run_line_magic('matplotlib', 'inline')
import matplotlib.pyplot as plt
import seaborn as sns
sns.set(color_codes=True)
plt.rcParams['axes.grid'] = False

#import numpy as np
#import pandas as pd
#import itertools

import logging
logger = logging.getLogger()


# 22 Elementary Graph Algorithms
# =================
# 
# This chapter presents methods for representing a graph and for searching a graph.

# ### 22.1 Representations of graphs
# 1. adjacency-list: sparse graphs
#    + pros: save memory.
# 
# 2. adjacency-matrix: dense graphs
#    + pros: tell quickly if there is an edge connecting two given vertices.
#    + $A = A^T$, in some applications, only store half of entries. 

# In[4]:


plt.figure(figsize=(12,8))
plt.imshow(plt.imread('./res/fig22_2.png'))


# In[5]:


# Exercises


# ### 22.2 Breadth-first search
# Given a graph $G = (V, E)$ and a distinguished source vertex $x$. The breadth-first search computes the distance (smallest number of edges) from $s$ to each reachable vertex.
# 
# For any vertex $v$ reachable from $s$, the simle path in the breadth-first tree from $s$ to $v$ corresponds to "shortest path" from $s$ to $v$ in $G$.

# In[6]:


plt.imshow(plt.imread('./res/BFS.png'))


# In[8]:


plt.figure(figsize=(8,12))
plt.imshow(plt.imread('./res/fig22_3.png'))


# In[9]:


# Exercises


# ### 22.3 Depth-first search
# Depth-first search explores edges out of the most recently discovered vertex $v$ that still has unexplored edges leaving it.
# 
# depth-first search may produce several trees $\to$ we use the predecessor subgraph: $G_{\pi} = (V, E_{\pi})$, where $E_{\pi} = \{ (v.{\pi}, v) : v \in V \text{ and } v.{\pi} \neq \operatorname{NIL} \}$.
# 
# 1. Each vertex is initially white, is grayed when it is *discovered* in the search, and is blacked when it is *finished*.
# 
# 2. depth-first search also *timestamps* each vertex.

# In[2]:


plt.imshow(plt.imread('./res/DFS.png'))


# In[4]:


plt.figure(figsize=(10,12))
plt.imshow(plt.imread('./res/fig22_4.png'))


# ##### properties
# 0. the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees.
# 
# 1. discovery and finishing times have *parenthesis structure*.
# 
# 2. classification of edges:
#    + Tree edges
#      edges in the depth-first forest $G_{\pi}$.
#      **WHITE**
#    + Back edges
#      edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
#      **GRAY**
#    + Forward edges
#      those nontree deges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
#      **BLACK**
#    + Cross edges
#      all other edges
#      **BLACK**

# In[7]:


plt.figure(figsize=(10,20))
plt.imshow(plt.imread('./res/fig22_5.png'))


# In[8]:


# Exercises


# ### 22.4 Topological sort
# used for directed acyclic graph.
# 
# A **topological sort** of a dag $G = (V, E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u,v)$, then $u$ appears before $v$ in the ordering.
# 
# Many applications use directed acyclic graphs to indicate precedences among events.

# In[4]:


plt.imshow(plt.imread('./res/tolo.png'))


# In[6]:


plt.figure(figsize=(12,8))
plt.imshow(plt.imread('./res/fig22_7.png'))


# ### 22.5 Strongly connected components
# classic application of depth-first search: decomposing a directed graphh into strongly connectd components.
# 
# a strong connected component of a directed graph $G = (V, E)$ is a maximal set of vertices $C \subseteq V$ such that vertices $u$ and $v$ are reachable from each other for every pair of verticies $u$ and $v$ in $C$.
# 
# define: $G^T = (V, E^T)$, where $E^T = \{ (u, v) : (v, u) \in E \}

# In[7]:


plt.imshow(plt.imread('./res/str_con.png'))


# 即先在$G$中搜出子树，再在子树中反向搜索出强连通域。

# In[8]:


plt.figure(figsize=(8,12))
plt.imshow(plt.imread('./res/fig22_9.png'))


# In[9]:


# Exercise