# Brief intro to Graphs
slides: https://hackmd.io/@multiscan/st-luc
---
take home message
## Do not reinvent the wheel
Problems that looks very **different** become very **similar** once represented with the same _language_. Many problems can be represented as graph solved using standard algorithms!
Find the graph library for your language (e.g. python [networkx](https://networkx.org/), ruby [rgl](https://github.com/monora/rgl), javascript [cytoscape](https://js.cytoscape.org/)...).
---
## Outline
* Definitions
* Usefull algorithms
* Examples / Hands on
---
## What is a <span class="red">graph</span> ?
* A way to represent **relationships** between data like
- **membership** (_belongs to_, _derives from_),
- **causalities** (dependencies),
- **connections** (networks);
* Nothing to do with <strong class="red">graph</strong>ics (although graphical representation helps thinking);
---
## Taxonomy
:-1: quite a lot of nomenclature
* Vertices and Edges
* Directed vs Undirected graphs
* Vertex degree, sources and sinks
* Complete, complement, transpose graph
* Connectivity, k-connectivity
---
So what is a graph ?
---
### Vertices / Nodes
<div class='cont'>
<div class='col'>
```graphviz
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
uno [label = 1, pos="1,2!"]
due [label = 2, pos="0,1!"]
tre [label = 3, pos="1,0!"]
qua [label = 4, pos="1,1!"]
cin [label = 5, pos="0,0!"]
}
```
</div>
<div class='col'>
```graphviz
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
uno [label = 1, pos="1,2!"]
due [label = 2, pos="0,1!"]
tre [label = 3, pos="1,0!"]
qua [label = 4, pos="1,1!"]
cin [label = 5, pos="0,0!"]
}
```
</div>
</div>
---
### Add edges to make a graph
<div class='cont'>
<div class='col'>
```graphviz
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
uno [label = 1, pos="1,2!"]
due [label = 2, pos="0,1!"]
tre [label = 3, pos="1,0!"]
qua [label = 4, pos="1,1!"]
cin [label = 5, pos="0,0!"]
uno -- due
uno -- qua
tre -- qua
qua -- tre
tre -- due
}
```
Undirected
</div>
<div class='col'>
```graphviz
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
uno [label = 1, pos="1,2!"]
due [label = 2, pos="0,1!"]
tre [label = 3, pos="1,0!"]
qua [label = 4, pos="1,1!"]
cin [label = 5, pos="0,0!"]
uno -> due
uno -> qua
tre -> qua
qua -> tre
tre -> due
}
```
Directed
</div>
</div>
---
### Edge Weights
```graphviz neato
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" margin="0.001,0.001" fixedsize=false fontsize=10 shape=rectangle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=orange color=white fontsize=12]
scale=0.7
layout=neato
ve [label="Venezia" pos="11,4!"]
vi [label="Vicenza" pos="7,6!"]
vr [label="Verona" pos="5,5!"]
pd [label="Padova" pos="9,5!"]
tv [label="Treviso" pos="10,7!"]
bo [label="Bologna" pos="7,3!"]
mi [label="Milano" pos="2,5!"]
fi [label="Firenze" pos="4,0!"]
pi [label="Pisa" pos="2,0!"]
ge [label="Genova" pos="1,3!"]
tv -- ve [weight=25,label="25"]
tv -- vi [weight=60,label="60"]
ve -- pd [weight=37,label="37"]
pd -- vi [weight=30,label="30"]
vi -- vr [weight=52,label="52"]
mi -- vr [weight=148,label="148"]
ge -- mi [weight=154,label="154"]
pd -- bo [weight=123,label="123"]
bo -- fi [weight=97,label="97"]
pi -- ge [weight=162,label="162"]
fi -- pi [weight=88,label="88"]
mi -- bo [weight=216,label="216"]
}
```
---
### Connectivity (undirected)
```graphviz neato
graph G {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontsize=10 style=filled shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" color=white fontsize=10 penwidth=3.0]
bgcolor=black
layout=neato
a [fillcolor="#98FB98"]
b [fillcolor="#98FB98"]
c [fillcolor="#FFA500"]
d [fillcolor="#98FB98"]
e [fillcolor="#98FB98"]
f [fillcolor="#FFA500"]
g [fillcolor="#98FB98"]
h [fillcolor=cyan]
i [fillcolor="#FFA500"]
j [fillcolor="#98FB98"]
k [fillcolor="#FFA500"]
l [fillcolor="#98FB98"]
m [fillcolor="#98FB98"]
a -- b
a -- c
b -- c
b -- d
c -- d
c -- f [color=red]
f -- e
f -- g
f -- i
f -- j
f -- h [color=red]
e -- g
i -- j
i -- k [color=red]
k -- l
k -- m
l -- m
}
```
* <span style="color: #FFA500">Articulation points</span>
* <span style="color: red">Bridges</span>
* <span style="color: cyan">Exterior vertex</span>
* Biconnected components
---
### Connectivity (directed)
```graphviz neato
digraph G {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontsize=10 style=filled shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" color=white fontsize=10 penwidth=2.0]
bgcolor=black
layout=neato
a [fillcolor=cyan]
b [fillcolor=cyan]
c [fillcolor=cyan]
d [fillcolor=cyan]
e [fillcolor=orange]
f [fillcolor=orange]
g [fillcolor=pink]
h [fillcolor=pink]
i [fillcolor=pink]
abcd[fillcolor=cyan shape=rectangle]
ef[fillcolor=orange shape=rectangle]
ghi[fillcolor=pink shape=rectangle]
a -> b
a -> c
b -> c
d -> a
c -> d
c -> e
e -> f
f -> e
d -> g
g -> h
h -> i
i -> g
abcd -> ef
ef -> ghi
abcd -> ghi
}
```
Strongly connected components
---
### Vertex degree
```graphviz!
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
cin [style=invis, pos="1,0!"]
uno [label="vertex", pos="1,1!"]
due [style=invis, pos="0,2!"]
tre [style=invis, pos="1,2!"]
qua [style=invis, pos="2,2!"]
uno -> cin
due -> uno
tre -> uno
qua -> uno
}
```
```graphviz!
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
cin [style=invis, pos="1,0!"]
uno [label="vertex", pos="1,1!"]
due [style=invis, pos="0,2!"]
tre [style=invis, pos="1,2!"]
qua [style=invis, pos="2,2!"]
uno -- cin
due -- uno
tre -- uno
qua -- uno
}
```
directed: in edges - out edges (3-1=2)
undirected: edges count (4)
---
### Short <span class="history">historical</span> digression
---
#### The seven bridges of <span class="history">Königsberg</span> (Euler, 1730)
<div class=cont>
<div class="col">
</div>
<div class="col">
```graphviz!
graph G {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontsize=9 style=filled shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" color=white fontsize=10]
bgcolor=black
layout=neato
R [label="R / 5" fillcolor=red fontcolor=white pos="0,1!"]
Y [label="Y / 3" fillcolor=yellow fontcolor=black pos="1,2!"]
B [label="B / 3" fillcolor=blue fontcolor=white pos="2,1!"]
G [label="G / 3" fillcolor=green fontcolor=black pos="1,0!"]
Y -- R
Y -- R
Y -- B
R -- B
R -- G
R -- G
B -- G
}
```
</div>
</div>
---
#### Euler path
traverse all the edges only once
#### Hamilton path
visit all the vertex only once
---
<div class="cont">
<div class="col">
```graphviz!
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
cin [style=invis, pos="1,0!"]
uno [label="vertex", pos="1,1!"]
due [style=invis, pos="0,2!"]
tre [style=invis, pos="1,2!"]
qua [style=invis, pos="2,2!"]
uno -> due
uno -> tre
uno -> qua
uno -> cin
}
```
source: only out edges
</div>
<div class="col">
```graphviz!
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
cin [style=invis, pos="1,0!"]
uno [label="vertex", pos="1,1!"]
due [style=invis, pos="0,2!"]
tre [style=invis, pos="1,2!"]
qua [style=invis, pos="2,2!"]
due -> uno
tre -> uno
qua -> uno
cin -> uno
}
```
sink: only in edges
</div>
</div>
---
```graphviz
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
label="original"
fontcolor=orange
tre [label = 3 pos="1,0!"]
qua [label = 4 pos="0,1!"]
due [label = 2, pos="2,1!"]
uno [label = 1, pos="1,2!"]
uno -- due
uno -- qua
tre -- qua
}
```
```graphviz
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
label="complete"
fontcolor=orange
tre [label = 3 pos="1,0!"]
qua [label = 4 pos="0,1!"]
due [label = 2, pos="2,1!"]
uno [label = 1, pos="1,2!"]
uno -- due
uno -- tre
uno -- qua
due -- tre
due -- qua
tre -- qua
}
```
```graphviz
graph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=circle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
label="complement"
fontcolor=orange
tre [label = 3 pos="1,0!"]
qua [label = 4 pos="0,1!"]
due [label = 2, pos="2,1!"]
uno [label = 1, pos="1,2!"]
uno -- tre
due -- tre
due -- qua
}
```
$G + \overline{G} = C_G$
density: $\rho_G \doteq \frac{|E_G|}{|E_C|}$
---
## In the computer
* Adjacency list (sparse graphs, $E_G \lesssim \frac{1}{4}E_C$)
* Adjacency matrix (dense graphs, $E_G \gtrsim \frac{3}{4}E_C$)
* Parent list (trees only)
* Array (binary trees/heaps)
---
## Common problems and algorithms
* Traversal: _depth-first_ (recursive) and _breadth-first_ (iterative) order
* Topological sort of DAG (arrange tasks with dependencies)
* Finding strongly or bi-connected components
* Minimum spanning tree (Kruskal, Prim)
* Shortest path (Dijkstra)
* Flow networks
* TSP (<a href="https://people.epfl.ch/ola.svensson" style="color: pink">Svensson</a>)
---
## Hands on AoC
DFS: [2020/10](https://adventofcode.com/2020/day/7)
All simple paths: [2020/10](https://adventofcode.com/2020/day/10)
Dijkstra: [2021/15](https://adventofcode.com/2021/day/15)
---
### AoC 2021 / 15
<div class="cont">
<div class="col">
<code>
<em>1</em></tt>163</br>
<em>1</em>381</br>
<em>2136</em></br>
369<em>4</em></br>
</code>
</div>
<div class="col">
```graphviz!
digraph G {
bgcolor="#191919"
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif" fontcolor=white color="#cc9900" fontsize=16 shape=rectangle]
edge [fontname="Helvetica,Arial,sans-serif" fontcolor=white color=white fontsize=10]
layout=neato
11 [pos="1,-1!"]
12 [pos="3,-1!"]
13 [pos="5,-1!"]
14 [pos="7,-1!"]
21 [pos="1,-2!"]
22 [pos="3,-2!"]
23 [pos="5,-2!"]
24 [pos="7,-2!"]
31 [pos="1,-3!"]
32 [pos="3,-3!"]
33 [pos="5,-3!"]
34 [pos="7,-3!"]
41 [pos="1,-4!"]
42 [pos="3,-4!"]
43 [pos="5,-4!"]
44 [pos="7,-4!"]
11 -> 12 [label=1]
12 -> 13 [label=6]
13 -> 14 [label=3]
14 -> 13 [label=6]
13 -> 12 [label=1]
12 -> 11 [label=1]
21 -> 22 [label=3]
22 -> 23 [label=8]
23 -> 24 [label=1]
24 -> 23 [label=8]
23 -> 22 [label=3]
22 -> 21 [label=1]
31 -> 32 [label=1]
32 -> 33 [label=3]
33 -> 34 [label=6]
34 -> 33 [label=3]
33 -> 32 [label=1]
32 -> 31 [label=2]
41 -> 42 [label=6]
42 -> 43 [label=9]
43 -> 44 [label=4]
44 -> 43 [label=9]
43 -> 42 [label=6]
42 -> 41 [label=3]
11 -> 21 [label=1]
21 -> 31 [label=2]
31 -> 41 [label=3]
41 -> 31 [label=2]
31 -> 21 [label=1]
21 -> 11 [label=1]
12 -> 22 [label=3]
22 -> 32 [label=1]
32 -> 42 [label=6]
42 -> 32 [label=1]
32 -> 22 [label=3]
22 -> 12 [label=1]
13 -> 23 [label=8]
23 -> 33 [label=3]
33 -> 43 [label=9]
43 -> 33 [label=3]
33 -> 23 [label=8]
23 -> 13 [label=6]
14 -> 24 [label=1]
24 -> 34 [label=6]
34 -> 44 [label=4]
44 -> 34 [label=6]
34 -> 24 [label=1]
24 -> 14 [label=3]
}
```
</div></div>
* values are costs for **arriving** in a _cavern room_ from an adjacent _room_.
* formulate as directed graph
* least dangerous path → Dijkstra
---
```ruby!
#!/usr/bin/env ruby
# https://github.com/monora/rgl
require 'rgl/adjacency'
require 'rgl/dijkstra'
class Quiz
def initialize(data)
@risk=[]
data.lines.each_with_index do |l,i|
@risk[i] = l.chomp.split("").map{|c| c.to_i}
end
@si = @risk.count
@sj = @risk[0].count
setup_graph()
end
def nodename(i,j)
# sprintf("%03d_%03d", i, j)
i * @sj + j
end
def risk_between(i,j)
@risk[i][j]
end
def setup_graph()
@g = RGL::DirectedAdjacencyGraph.new
@w = {}
0.upto(@si - 1) do |i|
0.upto(@sj - 1) do |j|
n = nodename(i,j)
wn = risk_between(i,j)
if j < (@sj - 1)
m = nodename(i,j+1)
wm = risk_between(i,j+1)
@g.add_edge(n,m)
@w[[n,m]] = wm
@g.add_edge(m,n)
@w[[m,n]] = wn
end
if i < (@si - 1)
m = nodename(i+1,j)
wm = risk_between(i+1,j)
@g.add_edge(n,m)
@w[[n,m]] = wm
@g.add_edge(m,n)
@w[[m,n]] = wn
end
end
end
end
def optimal_path_cost(si=0,sj=0,ti=@si-1,tj=@sj-1)
p=@g.dijkstra_shortest_path(@w, nodename(si,sj), nodename(ti,tj))
p[..-2].zip(p[1..]).sum{|e| risk_at(e)}
end
end
q = Quiz.new(File.read("t1.txt"))
c = q.optimal_path_cost
c == 40 or raise "Total cost for test data should be 40 but we get #{c}."
q = Quiz.new(File.read("data.txt"))
c = q.optimal_path_cost
puts "Quiz 1 solution: #{c}"
```
---
### AoC 2021 / 15 part 2
* Maze is multiplied by 5 in both directions.
* Brute force inpracticable
* Dijkstra scales $\mathcal{O}(n \log n)$. Good!
<div class="cont">
<div class="col">
<pre>
nr time
1 0.073
2 0.313
3 0.727
4 1.334
5 2.139
6 3.331
7 4.913
8 6.429
9 8.308
</pre>
</div>
<div class="col">
<img src="https://i.imgur.com/HMQ27Af.png" />
</div>
</div>
---
```ruby!
#!/usr/bin/env ruby
# https://github.com/monora/rgl
require 'rgl/implicit'
require 'rgl/dijkstra'
class Quiz
def initialize(data, rep=1)
@risk=[]
data.lines.each_with_index do |l,i|
@risk[i] = l.chomp.split("").map{|c| c.to_i}
end
@si = @risk.count
@sj = @risk[0].count
@rsi = rep * @si
@rsj = rep * @sj
@g = RGL::ImplicitGraph.new do |g|
g.vertex_iterator do |callback|
0.upto(@rsi*@rsj-1) {|n| callback.call(n)}
end
g.adjacent_iterator do |n1, callback|
i,j = name_to_ij(n1)
nn = []
nn << ij_to_name(i-1,j) if i > 0
nn << ij_to_name(i+1,j) if i + 1 < @rsi
nn << ij_to_name(i,j-1) if j > 0
nn << ij_to_name(i,j+1) if j + 1 < @rsj
nn.each{|n2| callback.call(n2)}
end
g.directed = true
end
@edge_weights_lambda = lambda {|edge| self.risk_at(edge)}
end
def ij_to_name(i,j)
return i * @rsj + j
end
def name_to_ij(n)
i = n / @rsj
j = n % @rsj
return i, j
end
def risk_at(edge)
n1,n2 = edge
i, j = name_to_ij(n2)
mi = i / @si
mj = j / @sj
ii = i % @si
jj = j % @sj
# each time the tile repeats to the right or downward, all of its risk
# levels are 1 higher than the tile immediately up or left of it.
# However, risk levels above 9 wrap back around to 1.
# Numbers 1-9 and wrap is like numbers 0-8 % 9 + 1
(@risk[ii][jj] + mi + mj - 1)%9 + 1
end
def optimal_path_cost(si=0,sj=0,ti=@rsi-1,tj=@rsj-1)
p=@g.dijkstra_shortest_path(@edge_weights_lambda, ij_to_name(si,sj), ij_to_name(ti,tj))
p[..-2].zip(p[1..]).sum{|e| risk_at(e)}
end
end
q = Quiz.new(File.read("t1.txt"), 1)
c = q.optimal_path_cost
c == 40 or raise "Total cost for test data should be 40 but we get #{c}."
q = Quiz.new(File.read("data.txt"), 1)
c = q.optimal_path_cost
c == 720 or raise "Total cost for question 1 should be 720 but we get #{c}."
q = Quiz.new(File.read("t1.txt"), 5)
c = q.optimal_path_cost
c == 315 or raise "Total cost for test data should be 315 but we get #{c}."
q = Quiz.new(File.read("data.txt"), 5)
c = q.optimal_path_cost
puts "Quiz 2 solution: #{c}"
```
---
### AoC 2020 / 10 part 2
Solution stolen [here](https://dev.to/meseta/advent-of-code-day-10-using-more-python-vectorized-calculations-in-numpy-2phe)
```python
import numpy as np
import networkx as nx
data = np.loadtxt("demo.txt")
joltages = np.sort(np.append(data, (0, np.max(data)+3)))
graph = nx.DiGraph()
for idx, adapter in enumerate(joltages[:-1]):
others = joltages[idx+1:]
for other in others[others <= adapter+3]:
graph.add_edge(adapter, other, diff=other-adapter)
count = sum(1 for _ in nx.all_simple_paths(graph, supply, device))
print("paths", count)
```
---
### Sources
- K. Orwant, J. Hietaniemi, J. Macdonald: _Mastering Algorithms with Perl_, O'Reilly
- Jay Wengrow: _A Common-Sense Guide to Data Structures and Algorithms, Second Edition_, The Pragmatic Programmer
- https://www.rubyguides.com/2017/05/graph-theory-in-ruby/
- https://en.m.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
- https://python.plainenglish.io/solve-sudoku-using-depth-first-search-algorithm-dfs-in-python-2be3caa08ccd
---
### Thank you!
<style>
.reveal .cont{
display: flex;
}
.reveal .col{
flex: 1;
}
.reveal .red{
color: #F55C5C;
}
.reveal .green{
color: #5CF55C;
}
.reveal .blue{
color: #5C5CF5;
}
.reveal .history {
color: #B8860B;
}
.reveal em {
color: #FFE4B5;
}
.reveal strong {
color: #40E0D0;
}
/*
.reveal {
background-color: #e6e6e6;
background-image: url('https://epfl-idevelop.github.io/elements/svg/epfl-logo.svg');
background-repeat: no-repeat;
background-position: 5px 5px;
}
.reveal {
color: #707070;
}
.reveal h1, .reveal h2, .reveal h3,
.reveal h4, .reveal h5, .reveal h6 {
color: #212121;
}
.reveal a {
color: #f009;
}
.reveal a:hover {
color: #f00;
}
.reveal .more {
color: #339;
}
.reveal code {
padding-top: 0.2em;
padding-bottom: 0.2em;
margin: 0;
font-size: 85%;
background-color: rgba(255, 255, 255, 0.46);
border-radius: 3px;
}
[data-contrast="on"] > div {
background-color: #ffffff94;
} */
/* https://stackoverflow.com/a/39614958/960623 */
img[alt$=">"] {
float: right;
}
img[alt$="<"] {
float: left;
}
img[alt$="><"] {
display: block;
max-width: 100%;
height: auto;
margin: auto;
float: none!important;
}
</style>
{"metaMigratedAt":"2023-06-17T19:04:43.591Z","metaMigratedFrom":"YAML","title":"St. Luc – Graphs","breaks":true,"description":"View the slide with \"Slide Mode\".","contributors":"[{\"id\":\"d4f95d06-3c38-4029-838a-43388a793679\",\"add\":33034,\"del\":14058}]"}