井戸端の直径
https://gyazo.com/77bef04f5338f47e26c05e1bda65d38b
https://gyazo.com/2b2339f7faba7066d0597b035c98b36e
日記で稼いでるなｗyosider.icon
2021-05-16 10:49:19 日記を除いたver.takker.icon
https://gyazo.com/be92263077003ae4ddde266755e8b2e0
/icons2/すばら.iconyosider.icon
ときどき話題が飛ぶところが面白いyosider.icon
リンクのネットワークのうち、二点間を結ぶ最短経路の中で最も長いもの（graph diameter) そのプロジェクトの屋台骨みたいなものが何となく見えたら面白いかと思ったけど微妙
面白いyosider.icon
直感に合った最長経路を得るには、もっと工夫したほうがいいのかも？yosider.icon
すごく意味的に近いページがたくさんあって、その小さい範囲を全部つないで距離を稼ぐみたいなことが起こりそう
避けるには意味を扱わないといけなさそうで難しそう
経路の長さってどういうことですか？sta.icon
リンクは繋いだか、繋いでないかだけなので、長さという概念がよくわからない
（コードはまだ読んでない読むのだるいから軽率にヒントもらうスタイル）
diameter …… 直径
dist …… 辿ったページリストと現在のページのペア
distList …… distのリスト
続きはウェブで……じゃなくて自分のprojectでsta.icon
ページAとBが最短で2-hop linkで繋がってたら、AとBの間の経路の長さは2、みたいなyosider.icon
なるほど！
リンクでたどり着いたら+1、みたいなニュアンスだ
YES
順リンクしか計算していないので、2-hop linkではありませんtakker.icon
あ、たしかにyosider.icon
/icons/あざっす.icon
2021-05-16
12:44:12 すでにA→B→Cという経路が探索されている時に、A→D→Bという経路が除外されてしまうのをなんとかしたいのだがうまく行かないtakker.icon
WebWorkerだとしても、非常に重い計算をさせると落ちるのか？
2021-11-10 13:35:55 まだ壊れたまんまかな？takker.icon
壊れてるの気付いた人がいたら直してくれ(他力本願)
12:31:33 refactoring
10:48:24 特定ページを除外できるようにした
2021-05-15
08:27:38 井戸端の直径が長すぎて画面がfreezeしたので、WebWorkerで計算するようにしたtakker.icon
ひゃっほー、エラーになるぜー suto3.icon（多分、ページ数が原因）
↓対象のプロジェクトを開いてこれをコンソールにコピペするとそこの経路が表示される
結構すぐ計算できるものなんだなあyosider.icon
全ページに対して、そのページからの最長の経路を求め、そのうち最大のものを表示する
code:diameter.js
(async () => {
const worker = new Worker('/api/code/villagepump/井戸端の直径/worker.js');
const project = scrapbox.Project.name;
const done = new Promise(resolve => {
worker.postMessage({project, exclude: /\d{4}\/\d{2}\/\d{2}/});
worker.onmessage = ({data}) => resolve(data);
});
const win = $(`<div class="page">
<a>
<i class="kamon kamon-cross" style="position: absolute; right: 1em;"></i>
</a>
Diameter path:
<ol>
</ol>
</div>`)
.css({
'position': 'fixed',
'z-index': 1000,
'width': '40%',
'height': 'calc(98% - 140px)',
'top': '140px',
'right': '0',
'margin': '0 6%',
'padding': '1em',
'overflow-y': 'scroll',
'border': '1px solid rgba(0,0,0,0.16)',
});
$('> a:nth(0)', win).click(() => { win.hide('fast', () => win.remove()); });
const ol = $('ol', win);
for (const p of (await done)0) { const li = $(<li><a href="/${project}/${encodeURIComponent(p)}">${p}</a></li>);
ol.append(li);
}
$('body').append(win);
})();
code:worker.js
self.addEventListener('message', async ({data: {project, exclude}}) => {
console.log([worker.js@井戸端の直径] Fetching all link data of "/${project}"...);
const links = await getLinkInfo(project, exclude);
console.log([worker.js@井戸端の直径] Done: , links);
console.log([worker.js@井戸端の直径] Start calculating the graph diameter...);
const diameterLists = Object.keys(links).map(page => {
// page: 距離を測る元ページのタイトル
let visited = new Set();
let distList = page; // 現在ページを含む辿ったページリスト（=経路）のリスト
while (true) {
// 現在ページから1歩進んだ経路のリスト
const nextList = distList.flatMap(pages => {
// pのリンク先の各ページを見る
if (!linkslink) return []; // 空リンクの場合 if (visited.has(link)) return [];
// 未訪問なら1歩進んだ経路を追加する
visited.add(link);
// prev0→prev1→...→prevn→linkと辿ってきたことを表す配列 return ...pages, link;
})
});
// 行き止まり
if (nextList.length == 0) break;
// 現在の経路リストを更新して繰り返す
distList = nextList;
}
//console.log([worker.js@井戸端の直径] length=${distList[0].length - 1}, variation=${distList.length});
return distList;
});
// 一番長いのを返す
const maxLength = Math.max(...diameterLists.map(distList => distList0.length ?? 0)); const diameterList = diameterLists.flatMap(distList => distList.filter(list => list.length === maxLength));
console.log([worker.js@井戸端の直径] Done: , diameterList);
self.postMessage(diameterList);
});
// 全ページのリンク情報を取得
async function getLinkInfo(project = scrapbox.Project.name, exclude) {
const rawPages = [];
let followingId = null;
do {
const param = followingId === null ? '' : ?followingId=${followingId};
const res = await fetch(
https://scrapbox.io/api/pages/${project}/search/titles${param}
);
followingId = res.headers.get('X-Following-Id');
rawPages.push(...(await res.json()));
} while (followingId);
return Object.fromEntries(rawPages.flatMap(p => exclude?.test?.(p.title) ? [] : p.title, p.links));
}
リンクlの走査の順番によっては最長経路を飛ばしてしまう可能性がある？yosider.icon
https://gyazo.com/de8f79fa2ba00e7be0473dd99f4aa436
https://gyazo.com/2a99e249a0943385c917978b12efc5f5
https://gyazo.com/4fb54ac2199fa695ecafaa3d9190f478
なんか違う気もするが.....erniogi.icon