-
Notifications
You must be signed in to change notification settings - Fork 0
/
dowgraphs.py
219 lines (180 loc) · 9.03 KB
/
dowgraphs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
import streamlit as st
from dow import *
from wordgraph import *
from prodcells import *
import matplotlib.pyplot as plt
import networkx as nx
import base64
from io import StringIO
# Make PRETTY pictures
def svg_write(fig, center=True):
"""
Renders a matplotlib figure object to SVG and embedd it as base64.
Disable center to left-margin align like other objects.
Shamelessly taken from:
https://discuss.streamlit.io/t/display-svg/172
"""
# Save to stringIO instead of file
imgdata = StringIO()
fig.savefig(imgdata, format="svg")
# Retrieve saved string
imgdata.seek(0)
svg_string = imgdata.getvalue()
# Encode as base 64
b64 = base64.b64encode(svg_string.encode("utf-8")).decode("utf-8")
# Add some CSS on top
css_justify = "center" if center else "left"
css = f'<p style="text-align:center; display: flex; justify-content: {css_justify};">'
html = f'{css}<img src="data:image/svg+xml;base64,{b64}"/>'
# Write the HTML
st.write(html, unsafe_allow_html=True)
st.title('Word Graphs')
st.header('Plotting and computing some of their properties.')
st.markdown('Let $\Sigma$ be an alphabet. _Double Occurrence Words_ (DOWs) ' +
'are words where each symbol appears exactly twice. For example, ' +
'$14323124$ is a DOW on the alphabet of positive integers. ' +
'We say a DOW with symbols in $\mathbb{N}^{>0}$ is in ' +
'_ascending order_ if its first symbol is $1$ and each new ' +
'symbol is exactly one more than the maximum among all previously ' +
'used symbols. $121323$ is in ascending order, while $343545$ ' +
'is not. Two DOWs are equivalent if they have the same ascending ' +
'order representation.')
st.markdown('Let $u^R$ denote the reverse of $u$, where all symbols are ' +
'written in reverse order. We say $uu^R$ is a _return_ word in ' +
'a DOW $w$ if $w = xuyu^Rz$ for some $x,y,z \in \Sigma^*$. ' +
'We say that $uu$ is a _repeat_ word if $w = xuyuz$ for some ' +
'$x,y,z \in \Sigma^*$. A repeat (resp. return) word is _maximal_ ' +
'if there does not exist a longer repeat (resp. return) word ' +
'$vv$ (resp. $vv^R$) such that $u \sqsubseteq v$. If either ' +
'$uu$ is a maximal repeat word in $w$ or $uu^R$ is a maximal ' +
'return word in $w$ we say that $u$ is a _maximal repeat factor_.')
st.markdown('Let $u$ be a maximal repeat (resp. return) factor in $w = xuyuz$ ' +
'(resp. $w=xuyu^Rz$). The deletion of $u$ from $w$ yields ' +
'$d_u(w)= xyz$. We call $v$ an _immediate successor_ of $w$ if' +
'there exists a maximal repeat or return factor $u$ such that ' +
'$v$ is ascending order equivalent to $d_u(w)$. A _succcessor_ ' +
'of $w$ is any word that can be obtained through iterated deletions, '+
'in ascending order. The successor relationship defines a partial ' +
'order DOWs.')
st.markdown('The _global word graph_ of size $n$, $G_n$ has all DOWs with up to ' +
'$n$ symbols as vertices and edges of the form')
st.latex( r'''w_1 \to w_2''')
st.markdown('where $w_2$ is an immediate successor of $w_1$. The _word_ ' +
'_graph rooted at_ $w$, for a DOW $w$, is the subgraph of a global word ' +
'graph containing $w$ that has $w$ as its maximum element and the ' +
'empty word, $\epsilon$, as its minimum.')
st.markdown('An $n$-dimensional _simplicial digraph_ (also directed clique ' +
'or transitive tournament) is the directed graph with vertices ' +
' $V = \{v_0, v_1, v_2, \ldots, v_n\}$ where')
st.latex(r'''v_i \to v_j''')
st.markdown('whenever $i < j$. Let $G\square H$ denote the Cartesian product of ' +
'two directed graphs, $G$ and $H$. A _prodsimplicial cell_ is ' +
'one whose 1-skeleton is the Cartesian product of finitely many ' +
'nontrivial ($n>0$) simplicial digraphs. ')
st.markdown('The scripts in this page draw rooted word graphs and compute ' +
'several of their properties, including Betti numbers built on '+
'complexes of prodsimplicial cells.')
dow = st.text_input("Double Occurrence Word", max_chars = 40, help="Type a " +
"DOW with positive integer symbols separated by commas.",
value="1,2,1,3,2,3,4,4")
draw_button = st.button("Draw word graph")
ncolor = st.sidebar.color_picker('Pick a color for vertices', '#1C82BA')
langle = st.sidebar.slider('Angle of rotation for vertex labels', min_value=0, max_value=360, value = 10)
nsize = st.sidebar.number_input('Node size', min_value=0,value=60)
md = st.sidebar.radio("Choose a theme", ('light','dark'))
if md=='light':
face='white'
else:
face='0E1117'
vlayer_md = 'Graphs use a multipartite graph layout with layers indicating ' + 'the deletion steps. The original DOW is placed on layer 1 ' +'by default and each deletion increases the counter by one.'
st.sidebar.markdown('Change vertex layout.')
vchoice = None
wordgraph = PCELL(word_graph(dow))
betti1 = wordgraph.betti_number(1)
betti2 = wordgraph.betti_number(2)
gvertices = len(wordgraph.G.nodes())
gedges = len(wordgraph.G.edges())
vertices = wordgraph.G.nodes(data=True)
vlabels = ()
layers = [vertices[v[0]]['layer'] for v in vertices]
for v in vertices:
vlabels+=(v[0],)
def redraw_dow():
wordgraph.change_layer(vchoice, nlayer)
with col1:
fig, G = wordgraph.draw(node_color=ncolor,node_size=nsize, angle=langle,
layer_by=layer_choice, mode=md)
#st.pyplot(fig)
svg_write(fig)
filename = dow + ".svg"
fig.savefig(filename, transparent=True, bbox_inches='tight',pad_inches=0, facecolor=face)
with open(filename, "rb") as file:
btn = st.download_button(
label="Download image",
data=file,
file_name=filename,
mime="image/svg"
)
def draw_dow():
with col1:
fig, G = wordgraph.draw(node_color=ncolor,node_size=nsize, angle=langle,
layer_by=layer_choice, mode =md)
#st.pyplot(fig)
svg_write(fig)
filename = dow + ".svg"
fig.savefig(filename, transparent=True, bbox_inches='tight',pad_inches=0, facecolor=face)
with open(filename, "rb") as file:
btn = st.download_button(
label="Download image",
data=file,
file_name=filename,
mime="image/svg"
)
col1, col2 = st.columns([3,1])
layer_choice = st.sidebar.selectbox('Layer vertices by...', ('deletions','length'), help=vlayer_md)
if layer_choice == 'deletions':
vchoice = st.sidebar.selectbox('Choose a vertex to move up/down.',
vlabels)
nlayer = st.sidebar.number_input('New layer', min_value = min(layers)-1,
max_value = max(layers)+1,value = vertices[vchoice]['layer'])
update_button = st.sidebar.button('Update')
if update_button:
redraw_dow()
else:
update_button = st.sidebar.button('Update')
if update_button:
draw_dow()
with col1:
if draw_button:
wordgraph = PCELL(word_graph(dow))
fig, G = wordgraph.draw(node_color=ncolor,node_size=nsize, angle=langle, mode=md,
layer_by=layer_choice)
#st.pyplot(fig)
svg_write(fig)
filename = dow + ".svg"
fig.savefig(filename, transparent=True, bbox_inches='tight',pad_inches=0, facecolor=face)
with open(filename, "rb") as file:
btn = st.download_button(
label="Download image",
data=file,
file_name=filename,
mime="image/svg"
)
with col2:
st.markdown('Properties')
st.latex(r'''\beta_1: ''' +str(betti1))
st.latex(r'''\beta_2: ''' + str(betti2))
st.latex(r'''\text{vertices: }''' + str(gvertices))
st.latex(r'''\text{edges: }''' + str(gedges))
st.markdown('Compute another property')
prop_choice = st.selectbox('Choose a property',('nth Betti number', 'number of n cells', 'separation'))
res = 'The '+ prop_choice + ' is '
if prop_choice == 'nth Betti number':
nvalue = st.number_input('Value of n', min_value=0, max_value=5)
res += str(wordgraph.betti_number(nvalue))
elif prop_choice == 'number of n cells':
nvalue = st.number_input('Value of n', min_value=0, max_value=5)
res += str(len(wordgraph.n_cells(nvalue)))
elif prop_choice == 'separation':
res += str(separation(dow))
st.markdown(res)