import%20marimo%0A%0A__generated_with%20%3D%20%220.25.2%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Vietoris%E2%80%93Rips%20persistence%20with%20%60phlite_rips%60%0A%0A%20%20%20%20%20%20%20%20A%20point%20cloud%20sampled%20from%20a%20noisy%20figure%20eight%20has%20two%20loops.%20We%20compute%20its%20Vietoris%E2%80%93Rips%20barcode%20up%20to%0A%20%20%20%20%20%20%20%20dimension%201%2C%20with%20representatives%2C%20draw%20the%20loops%20on%20the%20points%2C%20and%20watch%20the%20filtration%20grow.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20time%0A%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20polars%20as%20pl%0A%20%20%20%20from%20phlite_rips%20import%20Algorithm%2C%20rips%0A%0A%20%20%20%20return%20Algorithm%2C%20alt%2C%20np%2C%20pl%2C%20rips%2C%20time%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20pl)%3A%0A%20%20%20%20rng%20%3D%20np.random.default_rng(3)%0A%20%20%20%20t%20%3D%20rng.uniform(0%2C%202%20*%20np.pi%2C%20300)%0A%20%20%20%20%23%20A%20lemniscate%20(figure%20eight)%2C%20with%20noise%0A%20%20%20%20points%20%3D%20np.c_%5Bnp.cos(t)%2C%20np.sin(t)%20*%20np.cos(t)%5D%20%2F%20(1%20%2B%20np.sin(t)%20**%202)%5B%3A%2C%20None%5D%20*%202%0A%20%20%20%20points%20%2B%3D%20rng.normal(scale%3D0.04%2C%20size%3Dpoints.shape)%0A%20%20%20%20distances%20%3D%20np.linalg.norm(points%5B%3A%2C%20None%5D%20-%20points%5BNone%5D%2C%20axis%3D-1)%0A%20%20%20%20point_frame%20%3D%20pl.DataFrame(%7B%22x%22%3A%20points%5B%3A%2C%200%5D%2C%20%22y%22%3A%20points%5B%3A%2C%201%5D%7D)%0A%20%20%20%20return%20distances%2C%20point_frame%2C%20points%0A%0A%0A%40app.cell%0Adef%20_(distances%2C%20pl%2C%20rips%2C%20time)%3A%0A%20%20%20%20start%20%3D%20time.perf_counter()%0A%20%20%20%20barcode%20%3D%20rips(distances%2C%20max_dim%3D1%2C%20representatives%3DTrue)%0A%20%20%20%20elapsed%20%3D%20time.perf_counter()%20-%20start%0A%20%20%20%20bars%20%3D%20pl.DataFrame(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22dimension%22%3A%20f%22H%7Bdim%7D%22%2C%20%22birth%22%3A%20birth%2C%20%22death%22%3A%20death%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20dim%20in%20(0%2C%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20birth%2C%20death%20in%20barcode.pairings%5Bdim%5D%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20).with_columns(persistence%3Dpl.col(%22death%22)%20-%20pl.col(%22birth%22))%0A%20%20%20%20barcode%0A%20%20%20%20return%20barcode%2C%20bars%2C%20elapsed%0A%0A%0A%40app.cell%0Adef%20_(barcode%2C%20elapsed%2C%20mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22%22%22%0A%20%20%20%20%20%20%20%20%7Blen(barcode.pairings%5B0%5D)%7D%20finite%20H0%20bars%20and%20%7Blen(barcode.pairings%5B1%5D)%7D%20finite%20H1%20bars%20(bars%20of%20length%20zero%0A%20%20%20%20%20%20%20%20are%20omitted)%2C%20computed%20with%20representatives%20in%20%7Belapsed%20*%201000%3A.0f%7D%20ms.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20bars%2C%20pl)%3A%0A%20%20%20%20_top%20%3D%20bars%5B%22death%22%5D.max()%0A%20%20%20%20_diagonal%20%3D%20alt.Chart(pl.DataFrame(%7B%22t%22%3A%20%5B0.0%2C%20_top%5D%7D)).mark_line(color%3D%22grey%22%2C%20strokeWidth%3D1).encode(%0A%20%20%20%20%20%20%20%20x%3D%22t%3AQ%22%2C%20y%3D%22t%3AQ%22%0A%20%20%20%20)%0A%20%20%20%20_diagram%20%3D%20(%0A%20%20%20%20%20%20%20%20_diagonal%0A%20%20%20%20%20%20%20%20%2B%20alt.Chart(bars)%0A%20%20%20%20%20%20%20%20.mark_circle(size%3D40)%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22birth%3AQ%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22death%3AQ%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22dimension%3AN%22%2C%20title%3DNone)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22dimension%22%2C%20%22birth%22%2C%20%22death%22%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20).properties(width%3D320%2C%20height%3D320%2C%20title%3D%22persistence%20diagram%22)%0A%0A%20%20%20%20def%20barcode_panel(dimension)%3A%0A%20%20%20%20%20%20%20%20frame%20%3D%20bars.filter(pl.col(%22dimension%22)%20%3D%3D%20dimension).sort(%22birth%22%2C%20%22death%22).with_row_index(%22bar%22)%0A%20%20%20%20%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20alt.Chart(frame)%0A%20%20%20%20%20%20%20%20%20%20%20%20.mark_rule(strokeWidth%3D1.5)%0A%20%20%20%20%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22birth%3AQ%22%2C%20title%3D%22distance%22%2C%20scale%3Dalt.Scale(domain%3D%5B0%2C%20_top%5D))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x2%3D%22death%3AQ%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22bar%3AO%22%2C%20axis%3DNone)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22dimension%3AN%22%2C%20title%3DNone)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22dimension%22%2C%20%22birth%22%2C%20%22death%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20.properties(width%3D300%2C%20height%3D140%2C%20title%3Df%22%7Bdimension%7D%20barcode%20(%7Blen(frame)%7D%20bars)%22)%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_diagram%20%7C%20(barcode_panel(%22H0%22)%20%26%20barcode_panel(%22H1%22))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20barcode%2C%20np%2C%20pl%2C%20point_frame%2C%20points)%3A%0A%20%20%20%20_order%20%3D%20np.argsort(%5Bb%20-%20d%20for%20b%2C%20d%20in%20barcode.pairings%5B1%5D%5D)%5B%3A2%5D%0A%20%20%20%20_segments%20%3D%20pl.DataFrame(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22loop%22%3A%20f%22%5B%7Bbarcode.pairings%5B1%5D%5B_i%5D%5B0%5D%3A.2f%7D%2C%20%7Bbarcode.pairings%5B1%5D%5B_i%5D%5B1%5D%3A.2f%7D)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22x%22%3A%20points%5B_a%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22y%22%3A%20points%5B_a%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22x2%22%3A%20points%5B_b%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22y2%22%3A%20points%5B_b%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20_order%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_a%2C%20_b%20in%20barcode.pairing_representatives%5B1%5D%5B_i%5D%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20_axis%20%3D%20dict(axis%3DNone%2C%20scale%3Dalt.Scale(zero%3DFalse))%0A%20%20%20%20_points%20%3D%20alt.Chart(point_frame).mark_circle(size%3D12%2C%20color%3D%22black%22).encode(%0A%20%20%20%20%20%20%20%20x%3Dalt.X(%22x%3AQ%22%2C%20**_axis)%2C%20y%3Dalt.Y(%22y%3AQ%22%2C%20**_axis)%0A%20%20%20%20)%0A%20%20%20%20_loops%20%3D%20alt.Chart(_segments).mark_rule(strokeWidth%3D3).encode(%0A%20%20%20%20%20%20%20%20x%3D%22x%3AQ%22%2C%20y%3D%22y%3AQ%22%2C%20x2%3D%22x2%3AQ%22%2C%20y2%3D%22y2%3AQ%22%2C%20color%3Dalt.Color(%22loop%3AN%22%2C%20title%3D%22H1%20bar%22)%0A%20%20%20%20)%0A%20%20%20%20(_points%20%2B%20_loops).properties(width%3D560%2C%20height%3D280%2C%20title%3D%22representatives%20of%20the%20two%20longest%20H1%20bars%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Watching%20the%20filtration%0A%0A%20%20%20%20At%20radius%20%5C(r%5C)%20the%20Vietoris%E2%80%93Rips%20complex%20has%20an%20edge%20between%20every%20two%20points%20at%20distance%20at%20most%20%5C(r%5C)%20(and%0A%20%20%20%20a%20simplex%20on%20every%20set%20of%20points%20that%20are%20pairwise%20that%20close%3B%20only%20the%20edges%20are%20drawn).%20Components%20merge%0A%20%20%20%20quickly%3B%20each%20lobe%20of%20the%20figure%20eight%20closes%20into%20a%20loop%2C%20which%20is%20filled%20in%20once%20the%20points%20across%20it%20are%0A%20%20%20%20within%20%5C(r%5C)%20of%20each%20other.%20On%20the%20right%2C%20the%20bars%20alive%20at%20%5C(r%5C)%20are%20highlighted.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(bars%2C%20distances%2C%20mo%2C%20np%2C%20pl%2C%20points)%3A%0A%20%20%20%20import%20base64%0A%20%20%20%20import%20tempfile%0A%0A%20%20%20%20import%20matplotlib%0A%0A%20%20%20%20matplotlib.use(%22Agg%22)%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20matplotlib.animation%20import%20FuncAnimation%2C%20PillowWriter%0A%20%20%20%20from%20matplotlib.collections%20import%20LineCollection%0A%0A%20%20%20%20def%20animate(draw%2C%20times%2C%20figsize%3D(10%2C%203.8)%2C%20fps%3D6)%3A%0A%20%20%20%20%20%20%20%20%22%22%22An%20animated%20GIF%20of%20%60draw(axes%2C%20t)%60%20over%20%60times%60%2C%20as%20an%20image%20to%20display.%22%22%22%0A%20%20%20%20%20%20%20%20fig%2C%20axes%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3Dfigsize%2C%20gridspec_kw%3D%7B%22width_ratios%22%3A%20%5B1.6%2C%201%5D%7D)%0A%20%20%20%20%20%20%20%20animation%20%3D%20FuncAnimation(fig%2C%20lambda%20t%3A%20draw(axes%2C%20t)%2C%20frames%3Dtimes)%0A%20%20%20%20%20%20%20%20with%20tempfile.NamedTemporaryFile(suffix%3D%22.gif%22)%20as%20file%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20animation.save(file.name%2C%20writer%3DPillowWriter(fps%3Dfps)%2C%20dpi%3D72)%0A%20%20%20%20%20%20%20%20%20%20%20%20plt.close(fig)%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20base64.b64encode(open(file.name%2C%20%22rb%22).read()).decode()%0A%20%20%20%20%20%20%20%20return%20mo.Html(f'%3Cimg%20src%3D%22data%3Aimage%2Fgif%3Bbase64%2C%7Bdata%7D%22%20style%3D%22max-width%3A%20100%25%22%20%2F%3E')%0A%0A%20%20%20%20def%20draw_barcode(ax%2C%20frame%2C%20t%2C%20colours%2C%20top)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Bars%20as%20horizontal%20lines%2C%20those%20alive%20at%20%60t%60%20in%20colour%2C%20the%20rest%20faded%2C%20and%20a%20line%20at%20%60t%60.%22%22%22%0A%20%20%20%20%20%20%20%20ax.clear()%0A%20%20%20%20%20%20%20%20for%20y%2C%20(dimension%2C%20birth%2C%20death)%20in%20enumerate(frame.iter_rows())%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20alive%20%3D%20birth%20%3C%3D%20t%20%3C%20death%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.plot(%5Bbirth%2C%20death%5D%2C%20%5By%2C%20y%5D%2C%20color%3Dcolours%5Bdimension%5D%2C%20lw%3D2.2%2C%20alpha%3D1.0%20if%20alive%20else%200.15)%0A%20%20%20%20%20%20%20%20ax.axvline(t%2C%20color%3D%22black%22%2C%20lw%3D1)%0A%20%20%20%20%20%20%20%20ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20ax.set_xlim(0%2C%20top)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22barcode%2C%20r%20%3D%20%7Bt%3A.2f%7D%22)%0A%0A%20%20%20%20_i%2C%20_j%20%3D%20np.triu_indices(len(points)%2C%201)%0A%20%20%20%20_lengths%20%3D%20distances%5B_i%2C%20_j%5D%0A%20%20%20%20_segments%20%3D%20np.stack(%5Bpoints%5B_i%5D%2C%20points%5B_j%5D%5D%2C%20axis%3D1)%0A%20%20%20%20_shown%20%3D%20bars.filter(pl.col(%22persistence%22)%20%3E%200.03).sort(%22dimension%22%2C%20%22birth%22)%0A%20%20%20%20_top%20%3D%20float(_shown%5B%22death%22%5D.max())%20*%201.1%0A%0A%20%20%20%20def%20_draw(axes%2C%20t)%3A%0A%20%20%20%20%20%20%20%20ax%20%3D%20axes%5B0%5D%0A%20%20%20%20%20%20%20%20ax.clear()%0A%20%20%20%20%20%20%20%20ax.add_collection(LineCollection(_segments%5B_lengths%20%3C%3D%20t%5D%2C%20color%3D%22%23555555%22%2C%20lw%3D0.4%2C%20alpha%3D0.6))%0A%20%20%20%20%20%20%20%20ax.scatter(points%5B%3A%2C%200%5D%2C%20points%5B%3A%2C%201%5D%2C%20s%3D5%2C%20color%3D%22black%22%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20ax.set_xlim(points%5B%3A%2C%200%5D.min()%20-%200.1%2C%20points%5B%3A%2C%200%5D.max()%20%2B%200.1)%0A%20%20%20%20%20%20%20%20ax.set_ylim(points%5B%3A%2C%201%5D.min()%20-%200.1%2C%20points%5B%3A%2C%201%5D.max()%20%2B%200.1)%0A%20%20%20%20%20%20%20%20ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20ax.set_axis_off()%0A%20%20%20%20%20%20%20%20ax.set_title(%22edges%20of%20the%20Rips%20complex%20at%20radius%20r%22)%0A%20%20%20%20%20%20%20%20draw_barcode(axes%5B1%5D%2C%20_shown.select(%22dimension%22%2C%20%22birth%22%2C%20%22death%22)%2C%20t%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22H0%22%3A%20%22tab%3Ablue%22%2C%20%22H1%22%3A%20%22tab%3Aorange%22%7D%2C%20_top)%0A%0A%20%20%20%20animate(_draw%2C%20np.linspace(0%2C%20_top%2C%2044))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Choosing%20an%20algorithm%0A%0A%20%20%20%20The%20default%20(%60Algorithm.serial()%60%3A%20clearing%2C%20heap%20columns%2C%20uncached)%20favours%20memory.%20Every%20configuration%20gives%0A%20%20%20%20the%20same%20barcode%3B%20here%20are%20a%20few%2C%20timed%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Algorithm%2C%20distances%2C%20pl%2C%20rips%2C%20time)%3A%0A%20%20%20%20_configurations%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22serial%20(default)%22%3A%20dict(algorithm%3DAlgorithm.serial())%2C%0A%20%20%20%20%20%20%20%20%22serial%2C%20merged%20columns%2C%20cached%22%3A%20dict(algorithm%3DAlgorithm.serial().with_columns(%22merged%22).with_cache(True))%2C%0A%20%20%20%20%20%20%20%20%22parallel%22%3A%20dict(algorithm%3DAlgorithm.parallel())%2C%0A%20%20%20%20%20%20%20%20%22homology%22%3A%20dict(method%3D%22homology%22)%2C%0A%20%20%20%20%7D%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_name%2C%20_options%20in%20_configurations.items()%3A%0A%20%20%20%20%20%20%20%20_start%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20rips(distances%2C%20max_dim%3D1%2C%20**_options)%0A%20%20%20%20%20%20%20%20_rows.append(%7B%22configuration%22%3A%20_name%2C%20%22time%20(ms)%22%3A%20round((time.perf_counter()%20-%20_start)%20*%201000%2C%201)%7D)%0A%20%20%20%20pl.DataFrame(_rows)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
db48b6a7b4aa789f4a6d45747b9d4034