Skip to content

Instantly share code, notes, and snippets.

@ia7ck

ia7ck/scc.html

Last active December 23, 2018 19:28
Show Gist options
  • Save ia7ck/0325e10bb4821ac7892d01792486d1ff to your computer and use it in GitHub Desktop.
Save ia7ck/0325e10bb4821ac7892d01792486d1ff to your computer and use it in GitHub Desktop.
Download ZIP
Raw
scc.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>scc</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<link href="https://fonts.googleapis.com/css?family=Lato:400,700" rel="stylesheet">
<script src="https://cdnjs.cloudflare.com/ajax/libs/cytoscape/3.2.22/cytoscape.min.js"></script>
<script src="https://unpkg.com/dagre@0.7.4/dist/dagre.js"></script>
<script src="https://cdn.jsdelivr.net/npm/cytoscape-dagre@2.2.2/cytoscape-dagre.min.js"></script>
<script src="https://unpkg.com/webcola/WebCola/cola.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/cytoscape-cola@2.3.0/cytoscape-cola.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/qs/6.6.0/qs.min.js"></script>
</head>
<body>
<div id="cy"></div>
<script defer src="./scc.js"></script>
</body>
<style>
#cy {
width: 100%;
height: 100%;
top: 0;
left: 0;
position: absolute;
}
</style>
</html>
Raw
scc.js
let TIMEOUT = 1000;
const qs = Qs.parse(document.location.search.slice(1));
if (qs["speed"]) {
const s = parseInt(qs["speed"]);
if (1 <= s && s <= 5) {
TIMEOUT /= s;
}
}
const cy = cytoscape({
container: document.getElementById('cy'),
style: [{
selector: "edge",
style: {
"curve-style": "bezier",
"target-arrow-shape": "triangle",
"target-arrow-color": "gray",
"arrow-scale": 1.5,
"line-color": "gray",
},
}, {
selector: "node",
style: {
"label": "data(label)",
"text-valign": "center",
"text-halign": "center",
"font-family": "Lato",
"color": "white",
"background-color": "gray",
"width": 25,
"height": 25,
}
}],
});
const n = 8, m = 16;
let nodes = [];
for (let i = 0; i < n; i++) {
cy.add({ group: "nodes", data: { id: `node-${i}`, label: "" } });
}
let edges = [];
// 木をつくる
for (let i = 1; i < n; i++) {
const source = `node-${randInt(0, i)}`, target = `node-${i}`;
cy.add({ group: "edges", data: { id: `edge-${i}`, source, target } });
}
for (let i = 0; i < m - n; i++) {
const source = `node-${randInt(0, n)}`, target = `node-${randInt(0, n)}`;
const multi = cy.edges(`[source = "${source}"][target = "${target}"]`).size() >= 1;
if (!multi && source !== target) { // 多重辺・自己辺は無し
cy.add({ group: "edges", data: { id: `edge-${i + n}`, source, target } });
}
}
cy.layout({
name: "cola",
animate: false,
edgeLength: 150,
}).run();
const sleep = (ms) => (new Promise(resolve => setTimeout(resolve, ms)));
(async () => {
let seen = [], ord = [], root = [];
async function dfs(node_id) {
await sleep(TIMEOUT);
if (!seen[node_id]) {
seen[node_id] = true;
cy.$(`#${node_id}`).style({ "background-color": "skyblue" });
const edges = cy.$(`#${node_id}`).outgoers().filter((el) => (el.isEdge()));
for (let i = 0; i < edges.size(); i++) {
cy.$(`#${edges[i].id()}`).style({ "line-color": "skyblue", "target-arrow-color": "skyblue" });
await dfs(edges[i].data("target"));
cy.$(`#${edges[i].id()}`).style({ "line-color": "gray", "target-arrow-color": "gray" });
}
ord.push(node_id);
cy.$(`#${node_id}`).data({ label: ord.length });
await sleep(TIMEOUT);
}
}
async function dfs2(node_id, rt) {
await sleep(TIMEOUT);
if (!root[node_id]) {
root[node_id] = rt;
cy.$(`#${node_id}`).style({ "background-color": "skyblue" });
const edges = cy.$(`#${node_id}`).outgoers().filter((el) => (el.isEdge()));
for (let i = 0; i < edges.size(); i++) {
cy.$(`#${edges[i].id()}`).style({ "line-color": "skyblue", "target-arrow-color": "skyblue" });
const next_node = edges[i].data("target");
const revert = root[next_node] && root[next_node] !== rt;
await dfs2(next_node, rt);
if (revert) {
cy.$(`#${edges[i].id()}`).style({ "line-color": "gray", "target-arrow-color": "gray" });
}
}
}
}
await dfs("node-0");
await sleep(TIMEOUT);
cy.nodes().style({ "background-color": "gray" });
await sleep(TIMEOUT);
const rev_edges = cy.edges().map((edge) => ({
group: "edges",
data: {
id: edge.id(),
source: edge.data("target"),
target: edge.data("source"),
}
}));
cy.edges().remove();
cy.add(rev_edges);
ord.reverse();
for (const node_id of ord) {
if (!root[node_id]) {
await dfs2(node_id, node_id);
cy.edges().filter((edge) => {
const source = edge.data("source"), target = edge.data("target");
return root[source] === node_id && root[target] === node_id;
}).style({ "line-color": "salmon", "target-arrow-color": "salmon" });
}
}
await sleep(TIMEOUT * 2);
let del_edges = cy.edges().filter((edge) => {
const source = edge.data("source"), target = edge.data("target");
return source !== root[source] || target !== root[target];
});
del_edges.remove();
let new_edges = del_edges.filter((edge) => {
const source = edge.data("source"), target = edge.data("target");
return root[source] !== root[target];
}).map((edge) => ({
group: "edges",
data: {
id: edge.id(),
source: root[edge.data("source")],
target: root[edge.data("target")],
}
}));
cy.add(new_edges);
cy.nodes().forEach((node) => {
if (node.id() === root[node.id()]) {
const sz = Object.values(root).filter((rt) => (rt === node.id())).length;
cy.$(`#${node.id()}`).style({ width: 20 + sz * 5, height: 20 + sz * 5 });
}
});
cy.nodes().filter((node) => {
return node.id() !== root[node.id()];
}).remove();
const rev_rev_edges = cy.edges().map((edge) => ({
group: "edges",
data: {
id: edge.id(),
source: edge.data("target"),
target: edge.data("source"),
}
}));
await sleep(TIMEOUT * 2);
cy.edges().remove();
cy.add(rev_rev_edges);
})();
function randInt(lb, ub) {
return Math.floor(Math.random() * (ub - lb)) + lb;
}
function getID(str) {
const matches = str.match(/node-(\d+)/);
return parseInt(matches[1]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment