Graphs

See also slides

Node as information and edges as relationship between data

Directed acyclic graph (DAG)

Application: Merkle DAG

undirected.

$(\mathcal{N}, \mathcal{E})$

• $\mathcal{N}$: set of vertices
• $\mathcal{E}$: set of undirected edges: $\mathcal{E} \subseteq \mathcal{N} \times \mathcal{N}$

path is a sequence of nodes and edges connect two nodes.

A graph is connected if there is a path between every pair of vertices.

In a weight undirected graph each edge has a weight: $w: \mathcal{E} \to \mathbb{R}$

See also Graph isomorphism

directed.

$(\mathcal{N}, \mathcal{E})$

• $\mathcal{N}$: set of vertices
• $\mathcal{E}$: set of edges containing node pairs: $\mathcal{E} \subseteq \mathcal{N} \times \mathcal{N}$

path difference

sequence of nodes and edges are directional, edges are ordered pairs.

cycle

path with at-least one edge from a node

Strongly component: maximal sub-graph in which all node pairs are strongly connected.

matrix representation

Let $\mathcal{G} = (\mathcal{N}, \mathcal{E})$ be a directed graph with $n \in \mathcal{N} \land id(n) \text{ with } 0 \leq id(n) \leq |\mathcal{N}|$

Let $M = | \mathcal{N} | \times | \mathcal{N} |$ matrix

For every pairs of nodes $(m, n)$ set $M[id(m), id(n)] \coloneqq (m, n) \in \mathcal{E}$

The adjacency list representation

Important

Let $A \lbrack 0 \dots |\mathcal{N}|$ be an array of bags For every edge $(m, n \in \mathcal{E})$ add $n$ to $(m,n)$ to bag $A \lbrack id(m) \rbrack$

ops	complexity
add/remove nodes	$\Theta(\|\mathcal{N}\|)$ (copy array)
add/remove edges $(n, m)$	$\Theta(\|out(n)\|)$ (adding to bag)
check an edge $(n, m)$ exists	$\Theta(\|out(n)\|)$ (searching bags)
iterate over all incoming edges of $n$	$\Theta(\|\mathcal{E}\|)$ (scan all bags)
iterate over all outgoing edges of $n$	$\Theta(\|out(n)\|)$ (scan a bag)
Check or change the weight of $(n, m)$	$\Theta(1)$

comparison.

Dense graph: $|\mathcal{E}| \approx \Theta(|\mathcal{N}|^2)$ > Sparse graph: $|\mathcal{E}| \approx \Theta(|\mathcal{N}|)$

Traversing undirected graph.

Depth-first search (DFS)

$"\\begin{algorithm}\n\\caption{DFS-R(G, marked, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), \\text{marked}, n \\in \\mathcal{N}$\n\\FORALL{$ (n, m) \\in \\mathcal{E} $}\n \\IF{$\\neq \\text{marked}[m]$}\n \\STATE $\\text{marked}[m] \\coloneqq \\text{true}$\n \\STATE $\\text{DFS-R}{(G, \\text{marked}, m)}$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 1 DFS-R(G, marked, n)

Require: $G = (\mathcal{N}, \mathcal{E}), \text{marked}, n \in \mathcal{N}$

1:for all $(n, m) \in \mathcal{E}$ do

2:if $\neq \text{marked}[m]$ then

3:$\text{marked}[m] \coloneqq \text{true}$

4:$\text{DFS-R}{(G, \text{marked}, m)}$

5:end if

6:end for

$\text{marked} \coloneqq \lbrace n \longmapsto (n \neq s) \mid n \in \mathcal{N} \rbrace$

Conclusion

• all nodes to which $n_3$ is connected
• $\mathcal{G}$ is not a connected graph
• The order of recursive call determines all $n_3$ is connected to.

Complexity

• $|\mathcal{N}|$ memory for marked and at-most $|\mathcal{N}|$ recursive calls
• inspect each node at-most once and traverse each edge once: $\Theta(|\mathcal{N}| + |\mathcal{E}|)$

Connected-components

$"\\begin{algorithm}\n\\caption{DFS-CC-R(G, cc, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), cc, n \\in \\mathcal{N}$\n\\FORALL{$(n, m) \\in \\mathcal{E}$}\n \\IF{$cc[m] = \\text{unmarked}$}\n \\STATE $cc[m] \\coloneqq cc[n]$\n \\STATE $\\text{DFS-CC-R}(G, cc, m)$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 2 DFS-CC-R(G, cc, n)

Require: $G = (\mathcal{N}, \mathcal{E}), cc, n \in \mathcal{N}$

1:for all $(n, m) \in \mathcal{E}$ do

2:if $cc[m] = \text{unmarked}$ then

3:$cc[m] \coloneqq cc[n]$

4:$\text{DFS-CC-R}(G, cc, m)$

5:end if

6:end for

$"\\begin{algorithm}\n\\caption{COMPONENTS(G, s)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), s \\in \\mathcal{N}$\n\\STATE $cc \\coloneqq \\{ n \\mapsto \\text{unmarked} \\}$\n\\FORALL{$n \\in \\mathcal{N}$}\n \\IF{$cc[n] = \\text{unmarked}$}\n \\STATE $cc[n] \\coloneqq n$\n \\STATE $\\text{DFS-CC-R}(G, cc, n)$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 3 COMPONENTS(G, s)

Require: $G = (\mathcal{N}, \mathcal{E}), s \in \mathcal{N}$

1:$cc \coloneqq \{ n \mapsto \text{unmarked} \}$

2:for all $n \in \mathcal{N}$ do

3:if $cc[n] = \text{unmarked}$ then

4:$cc[n] \coloneqq n$

5:$\text{DFS-CC-R}(G, cc, n)$

6:end if

7:end for

Two-colourability

Bipartite graph

A graph is bipartite if we can partition the nodes in two sets such that no two nodes in the same set share an edge.

$"\\begin{algorithm}\n\\caption{DFS-TC-R(G, colors, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), \\text{colors}, n \\in \\mathcal{N}$\n\\FORALL{$(n, m) \\in \\mathcal{E}$}\n \\IF{$\\text{colors}[m] = 0$}\n \\STATE $\\text{colors}[m] \\coloneqq -\\text{colors}[n]$\n \\STATE $\\text{DFS-TC-R}(G, \\text{colors}, m)$\n \\ELSIF{$\\text{colors}[m] = \\text{colors}[n]$}\n \\STATE \\textbf{print} \"This graph is not bipartite.\"\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 4 DFS-TC-R(G, colors, n)

Require: $G = (\mathcal{N}, \mathcal{E}), \text{colors}, n \in \mathcal{N}$

1:for all $(n, m) \in \mathcal{E}$ do

2:if $\text{colors}[m] = 0$ then

3:$\text{colors}[m] \coloneqq -\text{colors}[n]$

4:$\text{DFS-TC-R}(G, \text{colors}, m)$

5:else if $\text{colors}[m] = \text{colors}[n]$ then

6:print "This graph is not bipartite."

7:end if

8:end for

$"\\begin{algorithm}\n\\caption{TwoColors(G)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E})$\n\\STATE $\\text{colors} \\coloneqq \\{ n \\mapsto 0 \\mid n \\in \\mathcal{N} \\}$\n\\FORALL{$n \\in \\mathcal{N}$}\n \\IF{$\\text{colors}[n] = 0$}\n \\STATE $\\text{colors}[n] \\coloneqq 1$\n \\STATE $\\text{DFS-TC-R}(G, \\text{colors}, n)$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 5 TwoColors(G)

Require: $G = (\mathcal{N}, \mathcal{E})$

1:$\text{colors} \coloneqq \{ n \mapsto 0 \mid n \in \mathcal{N} \}$

2:for all $n \in \mathcal{N}$ do

3:if $\text{colors}[n] = 0$ then

4:$\text{colors}[n] \coloneqq 1$

5:$\text{DFS-TC-R}(G, \text{colors}, n)$

6:end if

7:end for

Breadth-first search (BFS)

$"\\begin{algorithm}\n\\caption{BFS(G, s)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), s \\in \\mathcal{N}$\n\\STATE $\\text{marked} \\coloneqq \\{ n \\mapsto (n \\neq s) \\mid n \\in \\mathcal{N} \\}$\n\\STATE $Q \\coloneqq \\text{a queue holding only } s$\n\\WHILE{$\\neg\\text{Empty}(Q)$}\n \\STATE $n \\coloneqq \\text{Dequeue}(Q)$\n \\FORALL{$(n, m) \\in \\mathcal{E}$}\n \\IF{$\\neg\\text{marked}[m]$}\n \\STATE $\\text{marked}[m] \\coloneqq \\text{true}$\n \\STATE $\\text{Enqueue}(Q, m)$\n \\ENDIF\n \\ENDFOR\n\\ENDWHILE\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 6 BFS(G, s)

Require: $G = (\mathcal{N}, \mathcal{E}), s \in \mathcal{N}$

1:$\text{marked} \coloneqq \{ n \mapsto (n \neq s) \mid n \in \mathcal{N} \}$

2:$Q \coloneqq \text{a queue holding only } s$

3:while $\neg\text{Empty}(Q)$ do

4:$n \coloneqq \text{Dequeue}(Q)$

5:for all $(n, m) \in \mathcal{E}$ do

6:if $\neg\text{marked}[m]$ then

7:$\text{marked}[m] \coloneqq \text{true}$

8:$\text{Enqueue}(Q, m)$

9:end if

10:end for

11:end while

Single-source shortest path

Given an undirected graph without weight and node $s \in \mathcal{N}$, find a shortest path from node $s$ to all nodes $s$ can reach.

$"\\begin{algorithm}\n\\caption{BFS-SSSP(G, s)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), s \\in \\mathcal{N}$\n\\STATE $\\text{distance} \\coloneqq \\{ n \\mapsto \\infty \\mid n \\in \\mathcal{N} \\}$\n\\STATE $\\text{distance}[s] \\coloneqq 0$\n\\STATE $Q \\coloneqq \\text{a queue holding only } s$\n\\WHILE{$\\neg\\text{Empty}(Q)$}\n \\STATE $n \\coloneqq \\text{Dequeue}(Q)$\n \\FORALL{$(n, m) \\in \\mathcal{E}$}\n \\IF{$\\text{distance}[m] = \\infty$}\n \\STATE $\\text{distance}[m] \\coloneqq \\text{distance}[n] + 1$\n \\STATE $\\text{Enqueue}(Q, m)$\n \\ENDIF\n \\ENDFOR\n\\ENDWHILE\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 7 BFS-SSSP(G, s)

Require: $G = (\mathcal{N}, \mathcal{E}), s \in \mathcal{N}$

1:$\text{distance} \coloneqq \{ n \mapsto \infty \mid n \in \mathcal{N} \}$

2:$\text{distance}[s] \coloneqq 0$

3:$Q \coloneqq \text{a queue holding only } s$

4:while $\neg\text{Empty}(Q)$ do

5:$n \coloneqq \text{Dequeue}(Q)$

6:for all $(n, m) \in \mathcal{E}$ do

7:if $\text{distance}[m] = \infty$ then

8:$\text{distance}[m] \coloneqq \text{distance}[n] + 1$

9:$\text{Enqueue}(Q, m)$

10:end if

11:end for

12:end while