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}\wedge id(n)\text{ with }0\le id(n)\le |\mathcal{N}|$

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

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

The adjacency list representation

Important

Let $A[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[id(m)]$

ops	complexity
add/remove nodes	$\Theta (\Vert \mathcal{N}\Vert )$ (copy array)
add/remove edges $(n,m)$	$\Theta (\Vert out(n)\Vert )$ (adding to bag)
check an edge $(n,m)$ exists	$\Theta (\Vert out(n)\Vert )$ (searching bags)
iterate over all incoming edges of $n$	$\Theta (\Vert \mathcal{E}\Vert )$ (scan all bags)
iterate over all outgoing edges of $n$	$\Theta (\Vert out(n)\Vert )$ (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)

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

$marked:=\{n⟼(n\ne s)\mid n\in \mathcal{N}\}$

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

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

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.

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

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)

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.

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