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%20Path%20homology%20of%20a%20digraph%20with%20%60phlite_grpph%60%0A%0A%20%20%20%20%20%20%20%20Grounded%20persistent%20path%20homology%20(GrPPH)%20tells%20apart%20cycles%20that%20an%20undirected%20method%20would%20treat%20alike%3A%0A%20%20%20%20%20%20%20%20a%20long%20directed%20cycle%20lives%20longer%20than%20a%20short%20one%2C%20a%20square%20of%20two%20parallel%20paths%20dies%20quickly%2C%20and%20a%0A%20%20%20%20%20%20%20%20bidirected%20edge%20is%20a%20small%20loop%20of%20its%20own.%20We%20build%20a%20digraph%20with%20a%20few%20of%20each%2C%20compute%20its%20barcode%20with%0A%20%20%20%20%20%20%20%20representatives%2C%20and%20highlight%20them.%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%20math%0A%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20networkx%20as%20nx%0A%20%20%20%20import%20polars%20as%20pl%0A%20%20%20%20from%20phlite_grpph%20import%20grpph%0A%0A%20%20%20%20return%20alt%2C%20grpph%2C%20math%2C%20nx%2C%20pl%0A%0A%0A%40app.cell%0Adef%20_(nx)%3A%0A%20%20%20%20G%20%3D%20nx.DiGraph()%0A%20%20%20%20%23%20A%20directed%20cycle%20of%20length%206%0A%20%20%20%20cycle%20%3D%20%5Bf%22c%7Bi%7D%22%20for%20i%20in%20range(6)%5D%0A%20%20%20%20G.add_weighted_edges_from((cycle%5Bi%5D%2C%20cycle%5B(i%20%2B%201)%20%25%206%5D%2C%201.0)%20for%20i%20in%20range(6))%0A%20%20%20%20%23%20A%20directed%204-cycle%2C%20attached%20at%20c0%0A%20%20%20%20square%20%3D%20%5B%22c0%22%2C%20%22s1%22%2C%20%22s2%22%2C%20%22s3%22%5D%0A%20%20%20%20G.add_weighted_edges_from((square%5Bi%5D%2C%20square%5B(i%20%2B%201)%20%25%204%5D%2C%201.0)%20for%20i%20in%20range(4))%0A%20%20%20%20%23%20Two%20paths%20from%20c3%20to%20t2%3A%20a%20square%2C%20but%20not%20a%20directed%20cycle%0A%20%20%20%20G.add_weighted_edges_from(%5B(%22c3%22%2C%20%22t1%22%2C%201.0)%2C%20(%22t1%22%2C%20%22t2%22%2C%201.0)%2C%20(%22c3%22%2C%20%22t3%22%2C%201.0)%2C%20(%22t3%22%2C%20%22t2%22%2C%201.0)%5D)%0A%20%20%20%20%23%20A%20bidirected%20edge%0A%20%20%20%20G.add_weighted_edges_from(%5B(%22t2%22%2C%20%22b%22%2C%200.5)%2C%20(%22b%22%2C%20%22t2%22%2C%200.5)%5D)%0A%20%20%20%20G%0A%20%20%20%20return%20(G%2C)%0A%0A%0A%40app.cell%0Adef%20_(G%2C%20grpph%2C%20pl)%3A%0A%20%20%20%20barcode%20%3D%20grpph(G%2C%20representatives%3DTrue)%0A%20%20%20%20pl.DataFrame(%0A%20%20%20%20%20%20%20%20%5B%7B%22dimension%22%3A%20%22H0%22%2C%20%22birth%22%3A%20b%2C%20%22death%22%3A%20None%7D%20for%20b%20in%20barcode.essential%5B0%5D%5D%0A%20%20%20%20%20%20%20%20%2B%20%5B%7B%22dimension%22%3A%20%22H1%22%2C%20%22birth%22%3A%20b%2C%20%22death%22%3A%20d%7D%20for%20b%2C%20d%20in%20barcode.pairings%5B1%5D%5D%0A%20%20%20%20)%0A%20%20%20%20return%20(barcode%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Four%20H1%20bars%2C%20all%20born%20at%200%20(in%20the%20grounded%20filtration%20the%20graph's%20own%20edges%20are%20there%20from%20the%20start)%2C%20with%0A%20%20%20%20very%20different%20lifetimes%3A%20the%20bidirected%20edge%20dies%20at%200.5%2C%20its%20weight%3B%20the%20two%20paths%20from%20%60c3%60%20to%20%60t2%60%2C%20which%0A%20%20%20%20are%20not%20a%20directed%20cycle%2C%20at%201%3B%20the%20directed%204-cycle%20at%202%20and%20the%20directed%206-cycle%20at%203.%20A%20directed%20cycle%20of%0A%20%20%20%20%5C(n%5C)%20unit%20edges%20lives%20until%20%5C(n%20%2F%202%5C).%20Each%20representative%20is%20a%20list%20of%20edges%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(G%2C%20alt%2C%20barcode%2C%20math%2C%20nx%2C%20pl)%3A%0A%20%20%20%20position%20%3D%20nx.kamada_kawai_layout(G.to_undirected())%0A%0A%20%20%20%20def%20edge_rows(edges%2C%20bend)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Each%20edge%20as%20a%20segment%2C%20shortened%20at%20both%20ends%2C%20with%20an%20arrowhead%20three%20quarters%20of%20the%20way%20along.%0A%20%20%20%20%20%20%20%20Edges%20in%20both%20directions%20are%20offset%20sideways%20(%60bend%60)%20so%20that%20they%20don't%20overlap.%22%22%22%0A%20%20%20%20%20%20%20%20rows%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20a%2C%20b%20in%20edges%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20(x0%2C%20y0)%2C%20(x1%2C%20y1)%20%3D%20position%5Ba%5D%2C%20position%5Bb%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20dx%2C%20dy%20%3D%20x1%20-%20x0%2C%20y1%20-%20y0%0A%20%20%20%20%20%20%20%20%20%20%20%20length%20%3D%20math.hypot(dx%2C%20dy)%0A%20%20%20%20%20%20%20%20%20%20%20%20ox%2C%20oy%20%3D%20-dy%20%2F%20length%20*%20bend%2C%20dx%20%2F%20length%20*%20bend%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20G.has_edge(b%2C%20a)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ox%20%3D%20oy%20%3D%200.0%0A%20%20%20%20%20%20%20%20%20%20%20%20sx%2C%20sy%20%3D%20x0%20%2B%200.12%20*%20dx%20%2B%20ox%2C%20y0%20%2B%200.12%20*%20dy%20%2B%20oy%0A%20%20%20%20%20%20%20%20%20%20%20%20ex%2C%20ey%20%3D%20x0%20%2B%200.88%20*%20dx%20%2B%20ox%2C%20y0%20%2B%200.88%20*%20dy%20%2B%20oy%0A%20%20%20%20%20%20%20%20%20%20%20%20rows.append(%0A%20%20%20%20%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%20%20%20%20%22x%22%3A%20sx%2C%20%22y%22%3A%20sy%2C%20%22x2%22%3A%20ex%2C%20%22y2%22%3A%20ey%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22hx%22%3A%20x0%20%2B%200.75%20*%20dx%20%2B%20ox%2C%20%22hy%22%3A%20y0%20%2B%200.75%20*%20dy%20%2B%20oy%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Vega's%20angle%20is%20clockwise%20from%20up%3B%20the%20triangle%20points%20up%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22angle%22%3A%20(90%20-%20math.degrees(math.atan2(dy%2C%20dx)))%20%25%20360%2C%0A%20%20%20%20%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%20)%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(rows)%0A%0A%20%20%20%20nodes%20%3D%20pl.DataFrame(%5B%7B%22node%22%3A%20n%2C%20%22x%22%3A%20x%2C%20%22y%22%3A%20y%7D%20for%20n%2C%20(x%2C%20y)%20in%20position.items()%5D)%0A%20%20%20%20_axis%20%3D%20dict(axis%3DNone%2C%20scale%3Dalt.Scale(zero%3DFalse))%0A%0A%20%20%20%20def%20draw(edges%2C%20colour%2C%20title)%3A%0A%20%20%20%20%20%20%20%20frame%20%3D%20edge_rows(edges%2C%200.03)%0A%20%20%20%20%20%20%20%20lines%20%3D%20alt.Chart(frame).mark_rule(color%3Dcolour%2C%20strokeWidth%3D2.5%20if%20colour%20!%3D%20%22%23bbbbbb%22%20else%201.2).encode(%0A%20%20%20%20%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)%2C%20x2%3D%22x2%3AQ%22%2C%20y2%3D%22y2%3AQ%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20heads%20%3D%20alt.Chart(frame).mark_point(shape%3D%22triangle%22%2C%20filled%3DTrue%2C%20size%3D60%2C%20color%3Dcolour).encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%22hx%3AQ%22%2C%20y%3D%22hy%3AQ%22%2C%20angle%3Dalt.Angle(%22angle%3AQ%22%2C%20scale%3DNone)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20return%20lines%20%2B%20heads%0A%0A%20%20%20%20_node_marks%20%3D%20alt.Chart(nodes).mark_circle(size%3D260%2C%20color%3D%22%23dfe9f7%22%2C%20opacity%3D1).encode(x%3D%22x%3AQ%22%2C%20y%3D%22y%3AQ%22)%0A%20%20%20%20_labels%20%3D%20alt.Chart(nodes).mark_text(fontSize%3D9).encode(x%3D%22x%3AQ%22%2C%20y%3D%22y%3AQ%22%2C%20text%3D%22node%3AN%22)%0A%20%20%20%20_panels%20%3D%20%5B%5D%0A%20%20%20%20for%20(_birth%2C%20_death)%2C%20_rep%2C%20_colour%20in%20zip(%0A%20%20%20%20%20%20%20%20barcode.pairings%5B1%5D%2C%20barcode.pairing_representatives%5B1%5D%2C%20%5B%22%23c8453a%22%2C%20%22%23e07b39%22%2C%20%22%233a9d5d%22%2C%20%22%237d5ba6%22%5D%0A%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20_panels.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20(draw(G.edges%2C%20%22%23bbbbbb%22%2C%20%22%22)%20%2B%20draw(%5Btuple(e)%20for%20e%20in%20_rep%5D%2C%20_colour%2C%20%22%22)%20%2B%20_node_marks%20%2B%20_labels)%0A%20%20%20%20%20%20%20%20%20%20%20%20.properties(width%3D230%2C%20height%3D230%2C%20title%3Df%22H1%20bar%20%5B%7B_birth%7D%2C%20%7B_death%7D)%22)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20alt.hconcat(*_panels)%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%20In%20the%20grounded%20filtration%20the%20graph's%20own%20edges%20are%20there%20from%20the%20start%2C%20and%20at%20time%20%5C(t%5C)%20a%20new%20edge%0A%20%20%20%20%5C(u%20%5Cto%20v%5C)%20appears%20(dashed)%20once%20the%20shortest%20path%20from%20%5C(u%5C)%20to%20%5C(v%5C)%20has%20length%20at%20most%20%5C(t%5C).%20Cycles%0A%20%20%20%20are%20filled%20in%20by%20longer%20paths%20through%20the%20digraph.%20The%20bidirected%20edge's%20loop%20and%20the%20two%20parallel%20paths%20die%0A%20%20%20%20(at%200.5%20and%201)%20before%20any%20new%20edge%20appears%3A%20paths%20along%20the%20graph's%20own%20edges%20are%20enough%20to%20fill%20them.%20The%0A%20%20%20%20directed%204-%20and%206-cycles%20need%20the%20new%20edges%2C%20and%20die%20at%202%20and%203.%20On%20the%20right%2C%20the%20bars%20alive%20at%20%5C(t%5C)%20are%0A%20%20%20%20highlighted.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(G%2C%20barcode%2C%20mo%2C%20nx)%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%20import%20numpy%20as%20np%0A%20%20%20%20from%20matplotlib.animation%20import%20FuncAnimation%2C%20PillowWriter%0A%0A%20%20%20%20def%20animate(draw%2C%20times%2C%20figsize%3D(10%2C%204)%2C%20fps%3D4)%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.4%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%20_layout%20%3D%20nx.kamada_kawai_layout(G.to_undirected())%0A%20%20%20%20_distance%20%3D%20dict(nx.all_pairs_dijkstra_path_length(G))%0A%20%20%20%20_shortcuts%20%3D%20%5B(u%2C%20v%2C%20d)%20for%20u%2C%20row%20in%20_distance.items()%20for%20v%2C%20d%20in%20row.items()%20if%20u%20!%3D%20v%20and%20not%20G.has_edge(u%2C%20v)%5D%0A%20%20%20%20_bars%20%3D%20%5B(0%2C%20b%2C%20float(%22inf%22))%20for%20b%20in%20barcode.essential%5B0%5D%5D%20%2B%20%5B(1%2C%20b%2C%20d)%20for%20b%2C%20d%20in%20barcode.pairings%5B1%5D%5D%0A%20%20%20%20_colours%20%3D%20%5B%22tab%3Ablue%22%2C%20%22tab%3Aorange%22%5D%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%20_new%20%3D%20%5B(u%2C%20v)%20for%20u%2C%20v%2C%20d%20in%20_shortcuts%20if%20d%20%3C%3D%20t%5D%0A%20%20%20%20%20%20%20%20nx.draw_networkx_edges(G%2C%20_layout%2C%20edgelist%3D_new%2C%20ax%3Dax%2C%20edge_color%3D%22tab%3Agreen%22%2C%20style%3D%22dashed%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alpha%3D0.5%2C%20arrowsize%3D8%2C%20connectionstyle%3D%22arc3%2Crad%3D0.15%22)%0A%20%20%20%20%20%20%20%20nx.draw_networkx(G%2C%20_layout%2C%20ax%3Dax%2C%20node_size%3D220%2C%20font_size%3D7%2C%20node_color%3D%22%23dfe9f7%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3D%22%23444444%22%2C%20arrowsize%3D10%2C%20connectionstyle%3D%22arc3%2Crad%3D0.1%22)%0A%20%20%20%20%20%20%20%20ax.set_axis_off()%0A%20%20%20%20%20%20%20%20ax.set_title(f%22the%20graph%20and%20its%20shortcuts%20of%20length%20at%20most%20t%20(%7Blen(_new)%7D)%22)%0A%20%20%20%20%20%20%20%20ax%20%3D%20axes%5B1%5D%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(_bars)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20end%20%3D%20death%20if%20death%20!%3D%20float(%22inf%22)%20else%203.5%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.plot(%5Bbirth%2C%20end%5D%2C%20%5By%2C%20y%5D%2C%20color%3D_colours%5Bdimension%5D%2C%20lw%3D4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20alpha%3D1.0%20if%20birth%20%3C%3D%20t%20%3C%20death%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_xlim(-0.1%2C%203.5)%0A%20%20%20%20%20%20%20%20ax.set_ylim(-0.6%2C%20len(_bars)%20-%200.4)%0A%20%20%20%20%20%20%20%20ax.set_yticks(range(len(_bars)))%0A%20%20%20%20%20%20%20%20ax.set_yticklabels(%5Bf%22H%7Bd%7D%22%20for%20d%2C%20_%2C%20_%20in%20_bars%5D)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22barcode%2C%20t%20%3D%20%7Bt%3A.2f%7D%22)%0A%0A%20%20%20%20animate(_draw%2C%20np.linspace(0%2C%203.4%2C%2035))%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
07315b74ab163476fa941aef472c99e8