In [2]:
# %load ../../preconfig.py
%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'))
Out[4]:
<matplotlib.image.AxesImage at 0x10a6e8780>
In [5]:
# Exercises

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'))
Out[6]:
<matplotlib.image.AxesImage at 0x10a748f98>
In [8]:
plt.figure(figsize=(8,12))
plt.imshow(plt.imread('./res/fig22_3.png'))
Out[8]:
<matplotlib.image.AxesImage at 0x10ce68978>
In [9]:
# Exercises

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'))
Out[2]:
<matplotlib.image.AxesImage at 0x1098bd898>
In [4]:
plt.figure(figsize=(10,12))
plt.imshow(plt.imread('./res/fig22_4.png'))
Out[4]:
<matplotlib.image.AxesImage at 0x10bcec630>
properties
  1. the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees.

  2. discovery and finishing times have parenthesis structure.

  3. 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'))
Out[7]:
<matplotlib.image.AxesImage at 0x10cc12c18>
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'))
Out[4]:
<matplotlib.image.AxesImage at 0x1095ffc18>