serigraph

相互リンク構造を持つ文書群（互いに参照し合う Web サイトや Scrapbox / Obsidian ヴォルト）を 1 冊の PDF / mdBook に直列化する自作 Rust crate。名前は “serialize” + “graph”。旧 scrapbox_to_latex の書き直し。

動機

• 文書中の用語のリンク先には説明があるので、下位概念（リンク先）を先に配置したい
• だが参照を辿ると循環がしばしば生じ、循環があると一直線の本にできない
• 不要そうなリンクを削除して循環を解消し、トポロジカルソートで並べたい

仕組み

1. ヴォルト（Markdown + frontmatter、backlink・![[image]]・参考文献/BibTeX を解決）を Graph JSON に変換
2. 巡回ありグラフを DAG に変換（求めるものは Maximum Acyclic Subgraph＝NP困難）
   • 素朴解: サイクルを探索し、各サイクル内で被参照数（重み）最小の 1 辺を削除する操作を巡回が無くなるまで反復
3. トポロジカルソートして直列化、serigraph-mdbook で mdBook 出力（1000 頁以下なら動く）

課題

• 頂点数 $N$ に対しサイクル数が指数的に増え、素朴法は遅い（実測でも $N$ 増加に対し探索回数が急増）
• Tree Decomposition で頂点集合ごとに直列化する案 (ser2) は試したが大規模では非常に遅い
• 文書重みは PageRank で付けるべきか検討中
• BibTeX を持つ note へのリンクは \cite に変換する

関連: feedback-arc-set / strongly-connected-components / m2p-pandoc-md2tex / _moc-algorithm