serigraph

お気持ち

相互リンク構造のある文書をPDFにしたい(具体例: リンクで参照しあっているWebサイト, ScrapBoxの文書)。
文書中の用語のリンク先にはその用語の説明が書いてあるので、リンク先の文書をPDFにする時により上に持っていきたい。
しかし、文書中のリンクを辿ると循環していることがしばしばある、循環があるとPDFにすることは出来ない。不要そうなリンクをいくつか削除して循環を解消したい。

つまり

• 重み付きグラフ $V$ の全ての 閉路 を何らかの評価値に基づいて効率的に削除し 有向非巡回グラフ に変換したあとに トポロジカルソート することでグラフを直列化したい。

ジャストアイデア

1. 閉路を見つけだし、各閉路の中のコストが最小の1辺を削除する
2. 閉路が無くなったら終了、あるなら 1. を再び行う

とても遅い

概要

• vaultをPDFにしたい
  • 下位概念を先に表示したい
    • トポソ するには DAG でなければいけない
      • どうにかして巡回ありグラフを DAG にしたい
• “serigraph” = “serialize” + “graph”
  • serigraphの意味 - goo辞書 英和和英
• GitHub - wakame-tech/scrapbox_to_latex: WIP, 自分用
  • の書き直しでもある

設計

• 文書と参照リンクを持ったJSONを Graph JSON と呼ぶ
• serigraph: Graph JSON の直列化を行うcrate
  • feature-json にしても良いな
• 2022-10-04 serigraph-mdbook: Graph JSON -> mdBook
  • 1000pp以下なら動く

Directed Cyclic Graph -> DAG

• グラフ構造をtreeに変換できれば良い?
  • Tree Decomposition ではなかった
• 2022-08-10 求めているもの, Maximum Acyclic Subgraph という概念らしい
  • NP Hard

なくなるまでサイクルを探して切断する

• 切断箇所: 参照数 を重みとしてmaxの記事とその被参照記事

例

$(V,E)=(\{1,2,3,4\},\{(1,2),(2,3),(2,4),(3,1)\})$

1. サイクルの頂点集合 $\mathcal{C}$ を探索する $\mathcal{C}=\{\{1,2,3\}\}$
2. サイクルの各頂点に対して重みを計算する $[1(1),2(2),3(1)]$
3. 切断箇所 $=(1,2)$ でサイクルを切断する $E^{\prime }=\{(2,3),(2,4),(3,1)\}$
4. 上記をサイクルが存在しなくなるまで行う
5. トポロジカルソートを行い, 頂点列 $[1,3,2,4]$ を得る

計測

[examples\bench.rs:100] n_nodes = 50
[src\outgoing_sorter.rs:115] count = 1266
[examples\bench.rs:100] n_nodes = 100
[src\outgoing_sorter.rs:115] count = 5164
[examples\bench.rs:100] n_nodes = 150
[src\outgoing_sorter.rs:115] count = 12095
[examples\bench.rs:100] n_nodes = 200
[src\outgoing_sorter.rs:115] count = 20915

• $N$ に対して, cycleの数が指数的に増えていくからとても遅くなるのか

• Tree Decomposition してそれぞれの頂点集合に対して, serializeすると割と早い?

density=0.001
ser1(100):37.8µs
[src\serialize.rs:78] &set_graph.node_count() = 100
ser2(100):2.7014ms
ser1(500):93.2µs
[src\serialize.rs:78] &set_graph.node_count() = 500
ser2(500):55.9941ms
ser1(1000):205.4µs
[src\serialize.rs:78] &set_graph.node_count() = 1000
ser2(1000):220.878ms
ser1(2000):964.2µs
[src\serialize.rs:78] &set_graph.node_count() = 1909
ser2(2000):2.1583521s
ser1(3000):58.2105ms
[src\serialize.rs:78] &set_graph.node_count() = 1896
ser2(3000):121.4098062s

ser2 がその方法, 遅い

2022-08-24

• グラフをDFSをして訪れた順に記録 -> Minimum Spanning Tree
  • 2回目の参照は1回目の参照にリンクを付ければいいのでは?
    • DAG になるように頂点をコピーする事に相当?
      • いうなれば Minimum? Acyclic Supergraph

文書の重み

• 2022-10-16 PageRank で文書に重みをつけるべき?

vault -> Graph JSON

• 2022-06-05 idea ファイル間の依存関係をいい感じにクラスタリングして直列化して本にするソフトウェアつくりたいな

2022-08-07

• vault md -> JSON: unist, bibtex
  • unist-gfm
  • Obsidian-md をlegalize
    • backlinkの解決
    • todo $ ![[image]] の解決
• 記事には 参考文献 ヘッダやBiBTeXが存在することがあるが, それをまとめたい

md -> pdf

2021-09-23

• 数学とかの概念のdepgraphマインドマップとかで作る?
• ScrapBoxに貯めてAPI叩くのはあり
• KozanebaでScrapboxのリンクを整理 - 西尾泰和のScrapbox
  • 同じようなことをやっている人がいた
• 成功の主要因はタイミング - 西尾泰和のScrapbox

2021-09-26
ScrapBox → Markdown (scrapbox-converter)
Markdown → TeX (pandoc)
でPDFを自動生成するとか(そこまでしなくて良いし更新履歴がStreamで見れるScrapBoxで良くない?)

• ScrapBox PDF化頑張るか
• 情報の死蔵問題 - くたくたじゅうよん

後で読む: 絶対後で読まない

• Yes prop

• 数学系の勉強ノートをscrapboxにまとめにくい - くたくたじゅうよん

• iPadと組み合わせることで最強に

  • やはり Notionに手書きメモ機能来たら最強に

• ページの繋がりの視覚化 (daiiz) - Scrapbox Drinkup

• ScrapUniverse

2021-10-03

• • 研究用Scrapbox作った
  • scrapboxをTeX化するソフトを作りたい

だいず on Twitter: “Scrapboxで書いたものをTeXに変換して必要な画像を自動ダウンロードしてPDF生成するやつ、この週末で進化を遂げて次バージョンができつつある。入稿可能なフォーマット (PDF/X-1a) に準拠した。chapter単位でのプレビューも可能。 https://t.co/5wf6Vf3O9P pic.twitter.com/Br8cvteE0e / Twitter”

ありそう?
記事を依存関係でトポロジカルソートすればPDFにまとめられそう

2021-11-09

• wish 今後自分が書くすべての文書を同じフォーマットで書いて他でつかうときはエクスポートしたい
  フォーマット候補

• notion

• Markdown with Frontmatter

  • blog
  • zenn
  • kibela(数式が特殊)
  • slidev, marp

• TeX

  • ipu-pdf
  • paper

• Scrapbox

• 非公開記事はgit-crypt使う? idea

• pandoc

  • style + toc
  • 2022-08-16 [Python]Playwrightを利用したWebページのPDF保存方法 メモ - Qiita
    • PDF化もpythonでやる

• 2022-10-04 ReVIEW Starter: ruby

  • 整備されている, dockerで
    • git bashで docker -w /usr/src/projectが失敗 - Qiita

• 2022-10-04 mdBook: rust製

  • 数式
    • $$...$$ -> \[...\]
    • $...$ -> \\(...\\)
  • PDF exportも対応していてthemeもある

2022-12-12

• bib を持っているnoteへのリンクは \cite にする