2b:null 2c:["$","title",null,{"children":"Algorithmes de suppression de chevauchements, séminaire LaBRi, Bordeaux | Fati CHEN | Observable"}] 31:T62c,function chartOO() { const $svg = svg`${tex`\text{nni} = 0`}`; const _tex = d3.select($tex); const _svg = d3.select($svg); _svg.on("click", function (e) { e.stopPropagation(); }); const rect = { fill: "#eee", stroke: "lightgray", width: 60, height: 40, rx: 2 }; const text = { "font-size": "16px", "text-anchor": "middle", "dominant-baseline": "middle", dx: 30, dy: 20 }; const lines = [ { orient: "x", d: [ [100, 0], [100, 200] ] }, { orient: "y", d: [ [30, 40], [370, 40] ] } ]; const _lines = _svg .selectAll("path") .data(lines) .join( build({ append: "path", d: ({ d }) => d3.line()(d), stroke: "blue", "stroke-dasharray": "8 16" }) ); _svg .call( build({ append: "g", style: { transform: "translate3d(70px, 20px, 0)" }, call: [ build({ append: "rect", ...rect }), build({ append: "text", text: "A", ...text }) ] }) ) .call( build({ append: "g", style: { transform: "translate3d(270px, 80px, 0)" }, call: [ build({ append: "rect", ...rect }), build({ append: "text", text: "B", ...text }), (g) => g.datum({ x: 270, y: 80 }), ooDrag(_lines, $tex) ] }) ); return _html`

${$svg}${$tex}`; }32:T2362,function spreadGraph(id, state, { $div, graphs: { initial, bad, good } }) { const _div = d3.select($div); const _svg = _div.select("svg"); const hull = (data) => d3.polygonHull( _.flatMap(data, ({ x, y, width, height }) => [ [x - width / 2, y - height / 2], [x + width / 2, y - height / 2], [x + width / 2, y + height / 2], [x - width / 2, y + height / 2] ]) ) ?? []; const initial_small = `translate3d(150px, 10px, 0)scale(0.8)`; const bad_small = "translate3d(30px, 100px, 0)scale(0.8)"; const good_small = "translate3d(250px, 100px, 0)scale(0.8)"; const caption = { append: "text", ...node.text, "font-size": ({ show }) => show === "small" || show === false ? "16px" : "10px", dx: "75px", dy: "110px", text: (v) => `1.00` }; const initialArea = d3.polygonArea(hull(initial.nodes)); const _bad = _svg .selectAll("g.bad") .data([ { graph: state.bad === "initial" ? initial : state.bad === "small" ? bad : { nodes: [], edges: [] }, show: state.bad } ]) .join( build({ append: "g", classed: "bad", style: { transform: ({ show }) => show === "initial" ? initial_small : bad_small }, opacity: ({ show }) => (show === "small" ? 1 : 0), call: [ createGraph, build({ ...caption, property: { _current: 1 } }), (g) => build( { append: "path", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0 }, g ) .transition() .delay(1000) .duration(1000) .call(attrs, { "fill-opacity": 0.3, stroke: "lightred", fill: "red" }) ] }), (update) => update.call((u) => u .call(createGraph) .call((_graph) => _graph .select("path") .attr("d", (v) => `M${hull(v.graph.nodes).join("L")}Z`) .transition() .delay(1000) .duration(1000) .call(attrs, { stroke: "lightred", opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0.3, fill: "red" }) ) .call((u) => u .select("text") .transition() .duration(1000) .call(attrs, { dy: ({ show }) => (show === "small" ? "120px" : "110px"), fill: ({ show }) => (show === "small" ? "red" : "black") }) .textTween(function (d) { const i = d3.interpolate( this._current, d3.polygonArea(hull(d.graph.nodes)) / initialArea ); return function (t) { return (this._current = i(t)).toFixed(2); }; }) ) .attr("opacity", ({ show }) => (show === "small" ? 1 : 0)) .transition() .duration(1000) .call(styles, { transform: ({ show }) => show === "initial" || show === false ? initial_small : bad_small }) ) ); const _good = _svg .selectAll("g.good") .data([ { graph: state.good === "initial" ? initial : state.good === "small" ? good : { nodes: [], edges: [] }, show: state.good } ]) .join( build({ append: "g", classed: "good", style: { transform: ({ show }) => show === "initial" ? initial_small : good_small }, opacity: ({ show }) => (show === "small" ? 1 : 0), call: [ createGraph, build({ ...caption, property: { _current: 1 } }), (g) => build( { append: "path", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0 }, g ) .transition() .delay(1000) .duration(1000) .call(attrs, { "fill-opacity": 0.3, stroke: "lightgreen", fill: "green" }) ] }), (update) => update.call((u) => u .attr("opacity", ({ show }) => (show === "small" ? 1 : 0)) .transition() .duration(1000) .call(styles, { transform: ({ show }) => show === "initial" ? initial_small : good_small }) .selection() .call((u) => u .select("text") .transition() .duration(1000) .attr("dy", ({ show }) => show === "small" ? "120px" : "110px" ) .attr("fill", ({ show }) => show === "small" ? "green" : "black" ) .textTween(function (d) { console.log( hull(d.graph.nodes), d3.polygonArea(hull(d.graph.nodes)), d3.polygonArea(hull(d.graph.nodes)) / initialArea ); const i = d3.interpolate( this._current, d3.polygonArea(hull(d.graph.nodes)) / initialArea ); return function (t) { return (this._current = i(t)).toFixed(2); }; }) ) .call(createGraph) .call((_graph) => _graph .select("path") .attr("d", (v) => `M${hull(v.graph.nodes).join("L")}Z`) .transition() .delay(1000) .duration(1000) .call(attrs, { stroke: "lightgreen", opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0.3, fill: "green" }) ) ) ); const _initial = _svg .selectAll("g.initial") .data([{ graph: initial, show: state.initial }]) .join( build({ append: "g", classed: "initial", style: { transform: ({ show }) => show === "full" || show === "no-hull" ? `translate3d(100px, 10px, 0)scale(1.3)` : initial_small }, call: [ createGraph, build({ append: "path", classed: "hull", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, stroke: "lightblue", "fill-opacity": "0.3", fill: "lightblue", opacity: (d) => (d.show === "no-hull" ? 0 : 1) }), build(caption) ] }), (update) => update.call((u) => u .call((u) => u .select("path.hull") .transition() .attr("opacity", (d) => (d.show === "no-hull" ? 0 : 1)) ) .call((u) => u .select("text") .transition() .attr("font-size", ({ show }) => show === "small" ? "16px" : "10px" ) ) .transition() .call(styles, { transform: ({ show }) => show === "full" || show === "no-hull" ? `translate3d(100px, 10px, 0)scale(1.3)` : initial_small }) ) ); const references = (div) => div .selectAll("span.caption") .data((d) => d) .join( build({ append: ([, d]) => d, style: { opacity: ([d]) => (d === "small" ? 1 : 0) } }), (update) => update.call((u) => { u.transition() .duration(1000) .style("opacity", ([d]) => (d === "small" ? 1 : 0)); }) ); _div .selectAll("div.nts") .data([ [ [state.bad, _html`PFS' ${cite("Hayashi1998")}`], [state.good, _html`VPSC ${cite("Dwyer2005")}`] ] ]) .join( build({ append: (d) => _html`

`, call: references }), (update) => update.call(references) ); return $div; }33:Taa7,spreadBad = ({ edges: spreadInitial.edges, nodes: [ { index: 5, label: 5, x: 122.81323185011709, y: 5, width: 20, height: 10 }, { index: 4, label: 4, x: 72.3536036036036, y: 11, width: 20, height: 10 }, { index: 11, label: 11, x: 52.3536036036036, y: 14.75, width: 20, height: 10 }, { index: 20, label: 20, x: 24, y: 17.477272727272727, width: 20, height: 10 }, { index: 3, label: 3, x: 44.020270270270274, y: 24.75, width: 20, height: 10 }, { index: 10, label: 10, x: 102.79761904761904, y: 28.386363636363637, width: 20, height: 10 }, { index: 16, label: 16, x: 84.74567099567099, y: 38.38636363636364, width: 20, height: 10 }, { index: 17, label: 17, x: 136.7935251023486, y: 40.10064935064935, width: 20, height: 10 }, { index: 13, label: 13, x: 106.82142857142857, y: 48.90064935064935, width: 20, height: 10 }, { index: 19, label: 19, x: 10, y: 49.19050442311312, width: 20, height: 10 }, { index: 14, label: 14, x: 23.75, y: 59.19050442311312, width: 20, height: 10 }, { index: 2, label: 2, x: 43.75, y: 59.19050442311312, width: 20, height: 10 }, { index: 1, label: 1, x: 63.75, y: 65.19050442311311, width: 20, height: 10 }, { index: 18, label: 18, x: 39.30555555555556, y: 74.42127365388235, width: 20, height: 10 }, { index: 0, label: "0", x: 122.32142857142857, y: 74.42127365388235, width: 20, height: 10 }, { index: 12, label: 12, x: 82.32142857142857, y: 75.47390523282972, width: 20, height: 10 }, { index: 15, label: 15, x: 102.32142857142857, y: 78.42127365388235, width: 20, height: 10 }, { index: 8, label: 8, x: 64.92647058823529, y: 87.42127365388235, width: 20, height: 10 }, { index: 7, label: 7, x: 128.20378151260505, y: 90.42127365388235, width: 20, height: 10 }, { index: 6, label: 6, x: 134.8704481792717, y: 100.42127365388235, width: 20, height: 10 }, { index: 9, label: 9, x: 44.9264705882353, y: 101.19050442311311, width: 20, height: 10 } ] })34:T9fd,spreadGood = ({ edges: spreadInitial.edges, nodes: [ { index: 0, label: "0", x: 80.5000005, y: 65.71428528571428, width: 20, height: 10 }, { index: 1, label: 1, x: 48, y: 55.714284285714285, width: 20, height: 10 }, { index: 2, label: 2, x: 39.5000005, y: 45.71428328571429, width: 20, height: 10 }, { index: 3, label: 3, x: 40.5000005, y: 22.0000005, width: 20, height: 10 }, { index: 4, label: 4, x: 62.0000005, y: 11, width: 20, height: 10 }, { index: 5, label: 5, x: 83, y: 5, width: 20, height: 10 }, { index: 6, label: 6, x: 94, y: 95.71428828571428, width: 20, height: 10 }, { index: 7, label: 7, x: 90, y: 85.71428728571428, width: 20, height: 10 }, { index: 8, label: 8, x: 49.9999995, y: 77.2500015, width: 20, height: 10 }, { index: 9, label: 9, x: 42, y: 91, width: 20, height: 10 }, { index: 10, label: 10, x: 72, y: 24.9999995, width: 20, height: 10 }, { index: 11, label: 11, x: 41.9999995, y: 11.999999500000001, width: 20, height: 10 }, { index: 12, label: 12, x: 60.4999995, y: 65.71428528571428, width: 20, height: 10 }, { index: 13, label: 13, x: 79, y: 48, width: 20, height: 10 }, { index: 14, label: 14, x: 19.4999995, y: 57.2499995, width: 20, height: 10 }, { index: 15, label: 15, x: 70.0000005, y: 75.71428628571428, width: 20, height: 10 }, { index: 16, label: 16, x: 69, y: 35.0000005, width: 20, height: 10 }, { index: 17, label: 17, x: 104, y: 37, width: 20, height: 10 }, { index: 18, label: 18, x: 35, y: 67.2500005, width: 20, height: 10 }, { index: 19, label: 19, x: 10, y: 47.249998500000004, width: 20, height: 10 }, { index: 20, label: 20, x: 20.4999995, y: 17, width: 20, height: 10 } ] })35:T94e,spreadInitial = ({ edges: [ { source: 7, target: 8 }, { source: 15, target: 16 }, { source: 14, target: 12 }, { source: 13, target: 10 }, { source: 1, target: 9 }, { source: 6, target: 12 }, { source: 12, target: 10 }, { source: 18, target: 0 }, { source: 15, target: 7 }, { source: 16, target: 0 }, { source: 19, target: 18 }, { source: 7, target: 12 }, { source: 1, target: 2 }, { source: 14, target: 12 }, { source: 8, target: 9 }, { source: 10, target: 17 }, { source: 7, target: 0 }, { source: 15, target: 9 }, { source: 1, target: 19 }, { source: 15, target: 7 }, { source: 9, target: 2 }, { source: 19, target: 20 }, { source: 0, target: 8 }, { source: 8, target: 0 }, { source: 11, target: 5 }, { source: 11, target: 2 }, { source: 17, target: 16 }, { source: 10, target: 12 }, { source: 16, target: 15 } ], nodes: [ { index: 0, label: "0", x: 88, y: 66, width: 20, height: 10 }, { index: 1, label: "1", x: 56, y: 60, width: 20, height: 10 }, { index: 2, label: "2", x: 46, y: 57, width: 20, height: 10 }, { index: 3, label: "3", x: 47, y: 20, width: 20, height: 10 }, { index: 4, label: "4", x: 68, y: 11, width: 20, height: 10 }, { index: 5, label: "5", x: 91, y: 5, width: 20, height: 10 }, { index: 6, label: "6", x: 102, y: 89, width: 20, height: 10 }, { index: 7, label: "7", x: 98, y: 83, width: 20, height: 10 }, { index: 8, label: "8", x: 58, y: 77, width: 20, height: 10 }, { index: 9, label: "9", x: 50, y: 91, width: 20, height: 10 }, { index: 10, label: "10", x: 80, y: 26, width: 20, height: 10 }, { index: 11, label: "11", x: 52, y: 14, width: 20, height: 10 }, { index: 12, label: "12", x: 69, y: 67, width: 20, height: 10 }, { index: 13, label: "13", x: 87, y: 48, width: 20, height: 10 }, { index: 14, label: "14", x: 29, y: 57, width: 20, height: 10 }, { index: 15, label: "15", x: 78, y: 68, width: 20, height: 10 }, { index: 16, label: "16", x: 77, y: 34, width: 20, height: 10 }, { index: 17, label: "17", x: 112, y: 37, width: 20, height: 10 }, { index: 18, label: "18", x: 43, y: 66, width: 20, height: 10 }, { index: 19, label: "19", x: 18, y: 49, width: 20, height: 10 }, { index: 20, label: "20", x: 30, y: 17, width: 20, height: 10 } ] })36:T582,createGraph = (_graph) => { const rect = { ...node.rect, append: "rect", width: (n) => n.width, height: (n) => n.height }; const edge = { append: "path", class: "edges", d: ({ source, target }) => `M ${source.x} ${source.y} L ${target.x} ${target.y}`, stroke: "CornflowerBlue", "stroke-width": 1 }; _graph .selectAll("path.edges") .data(({ graph: { nodes, edges } }) => linkEdges(nodes, edges)) .join(build(edge), (update) => update.call((u) => u .transition() .duration(1000) .attr( "d", ({ source, target }) => `M ${source.x} ${source.y} L ${target.x} ${target.y}` ) ) ); _graph .selectAll("g.nodes") .data( (d) => d.graph.nodes, (d) => d.index ) .join( build({ append: "g", classed: "nodes", style: { transform: ({ x, y, width: w, height: h }) => `translate3d(${x - w / 2}px, ${y - h / 2}px, 0)` }, call: build(rect) }), (update) => update.call((u) => u .transition() .duration(1000) .call(styles, { transform: ({ x, y, width: w, height: h }) => `translate3d(${x - w / 2}px, ${y - h / 2}px, 0)` }) ) ); return _graph; }37:T962,function chartsp() { const rect = { ...node.rect, width: 60, height: 40 }; const text = { ...node.text, dx: 30, dy: 20 }; const data = [ { label: "A", x: 70, y: 20, ...rect }, { label: "B", x: 270, y: 80, ...rect }, { label: "C", x: 130, y: 90, ...rect }, { label: "D", x: 250, y: 10, ...rect } ]; const hull = (data) => d3.polygonHull( _.flatMap(data, ({ x, y, width, height }) => [ [x, y], [x + width, y], [x + width, y + height], [x, y + height] ]) ); const originArea = d3.polygonArea(hull(data)); const $svg = svg`${tex.block`\frac{area(ch')}{area(ch)} = 1.00`}`; const _tex = d3.select($tex); const _svg = d3.select($svg); _svg.on("click", function (e) { e.stopPropagation(); }); const h = build( { append: "path", d: `M${hull(data).join("L")}Z`, stroke: "lightblue", "fill-opacity": "0.3", fill: "lightblue" }, _svg ); _svg .selectAll("g") .data(data) .join( build({ append: "g", style: { transform: ({ x, y }) => `translate3d(${x}px, ${y}px, 0)` }, call: [ build({ append: "rect", ...rect }), build({ append: "text", text: (d) => d.label, ...text }), d3 .drag() .on("start", function (event, d) { d3.select(this).raise().select("rect").attr("stroke", "black"); }) .on("drag", function (event, d) { d3.select(this).style( "transform", `translate3d(${(d.x = event.x)}px, ${(d.y = event.y)}px, 0)` ); const hullpts = hull(data); h.attr("d", `M${hullpts.join("L")}Z`); const diff = d3.polygonArea(hullpts) / originArea; $tex.replaceChildren( tex.block`\frac{area(ch')}{area(ch)} = ${diff.toFixed(2)}` ); }) .on("end", function (event, d) { d3.select(this).select("rect").attr("stroke", "lightgray"); }) ] }) ); return _html`

${$svg}

${$tex}

Convex Hull Area ${cite("Strobelt2012")}

`; }38:T235e,function gsChart(id, state, { $div, graphs: { initial, bad, good } }) { const _div = d3.select($div); const _svg = _div.select("svg"); const hull = (data) => { const [minX, maxX] = d3.extent( data.flatMap((v) => [v.x - v.width / 2, v.x + v.width / 2]) ); const [minY, maxY] = d3.extent( data.flatMap((v) => [v.y - v.height / 2, v.y + v.height / 2]) ); if (minX === undefined) return []; return [ [minX, minY], [minX, maxY], [maxX, maxY], [maxX, minY] ]; }; const initial_small = `translate3d(150px, 1px, 0)scale(0.6)`; const bad_small = "translate3d(40px, 70px, 0)scale(0.6)"; const good_small = "translate3d(270px, 75px, 0)scale(0.6)"; const caption = { append: "text", ...node.text, "font-size": ({ show }) => show === "small" || show === false ? "16px" : "10px", dx: "75px", dy: "110px", text: (v) => `1.00` }; const _bad = _svg .selectAll("g.bad") .data([ { graph: state.bad === "initial" ? initial : state.bad === "small" ? bad : { nodes: [], edges: [] }, show: state.bad } ]) .join( build({ append: "g", classed: "bad", style: { transform: ({ show }) => show === "initial" ? initial_small : bad_small }, opacity: ({ show }) => (show === "small" ? 1 : 0), call: [ createGraph, build({ ...caption, property: { _current: 1 } }), (g) => build( { append: "path", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0 }, g ) .transition() .delay(1000) .duration(1000) .call(attrs, { "fill-opacity": 0.3, stroke: "lightred", fill: "red" }) ] }), (update) => update.call((u) => u .call(createGraph) .call((_graph) => _graph .select("path") .attr("d", (v) => `M${hull(v.graph.nodes).join("L")}Z`) .transition() .delay(1000) .duration(1000) .call(attrs, { stroke: "lightred", opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0.3, fill: "red" }) ) .call((u) => u .select("text") .transition() .duration(1000) .call(attrs, { dy: ({ show }) => (show === "small" ? "130px" : "110px"), dx: ({ show }) => (show === "small" ? "90px" : "75px"), fill: ({ show }) => (show === "small" ? "red" : "black") }) .textTween(function (d) { const i = d3.interpolate( this._current, d.show === "small" ? gs_bb_iar(initial, d.graph).value : 1 ); return function (t) { return (this._current = i(t)).toFixed(2); }; }) ) .attr("opacity", ({ show }) => (show === "small" ? 1 : 0)) .transition() .duration(1000) .call(styles, { transform: ({ show }) => show === "initial" || show === false ? initial_small : bad_small }) ) ); const _good = _svg .selectAll("g.good") .data([ { graph: state.good === "initial" ? initial : state.good === "small" ? good : { nodes: [], edges: [] }, show: state.good } ]) .join( build({ append: "g", classed: "good", style: { transform: ({ show }) => show === "initial" ? initial_small : good_small }, opacity: ({ show }) => (show === "small" ? 1 : 0), call: [ createGraph, build({ ...caption, property: { _current: 1 } }), (g) => build( { append: "path", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0 }, g ) .transition() .delay(1000) .duration(1000) .call(attrs, { "fill-opacity": 0.3, stroke: "lightgreen", fill: "green" }) ] }), (update) => update.call((u) => u .attr("opacity", ({ show }) => (show === "small" ? 1 : 0)) .transition() .duration(1000) .call(styles, { transform: ({ show }) => show === "initial" ? initial_small : good_small }) .selection() .call((u) => u .select("text") .transition() .duration(1000) .attr("dy", ({ show }) => show === "small" ? "120px" : "110px" ) .attr("dx", ({ show }) => (show === "small" ? "60px" : "75px")) .attr("fill", ({ show }) => show === "small" ? "green" : "black" ) .textTween(function (d) { const i = d3.interpolate( this._current, d.show === "small" ? gs_bb_iar(initial, d.graph).value : 1 ); return function (t) { return (this._current = i(t)).toFixed(2); }; }) ) .call(createGraph) .call((_graph) => _graph .select("path") .attr("d", (v) => `M${hull(v.graph.nodes).join("L")}Z`) .transition() .delay(1000) .duration(1000) .call(attrs, { stroke: "lightgreen", opacity: (v) => (v.show === "small" ? 1 : 0), "fill-opacity": 0.3, fill: "green" }) ) ) ); const _initial = _svg .selectAll("g.initial") .data([{ graph: initial, show: state.initial }]) .join( build({ append: "g", classed: "initial", style: { transform: ({ show }) => show === "full" || show === "no-hull" ? `translate3d(100px, 10px, 0)scale(1.3)` : initial_small }, call: [ createGraph, build({ append: "path", classed: "hull", d: (v) => `M${hull(v.graph.nodes).join("L")}Z`, stroke: "lightblue", "fill-opacity": "0.3", fill: "lightblue", opacity: (d) => (d.show === "no-hull" ? 0 : 1) }), build(caption) ] }), (update) => update.call((u) => u .call((u) => u .select("path.hull") .transition() .attr("opacity", (d) => (d.show === "no-hull" ? 0 : 1)) ) .call((u) => u .select("text") .transition() .attr("font-size", ({ show }) => show === "small" ? "16px" : "10px" ) ) .transition() .call(styles, { transform: ({ show }) => show === "full" || show === "no-hull" ? `translate3d(100px, 10px, 0)scale(1.3)` : initial_small }) ) ); const references = (div) => div .selectAll("span.caption") .data((d) => d) .join( build({ append: ([, d]) => d, style: { opacity: ([d]) => (d === "small" ? 1 : 0) } }), (update) => update.call((u) => { u.transition() .duration(1000) .style("opacity", ([d]) => (d === "small" ? 1 : 0)); }) ); _div .selectAll("div.nts") .data([ [ [state.bad, _html`GTREE ${cite("Nachmanson2016")}`], [state.good, _html`VPSC ${cite("Dwyer2005")}`] ] ]) .join( build({ append: (d) => _html`

`, call: references }), (update) => update.call(references) ); return $div; }39:Tb4b,gsBad = ({ edges: spreadInitial.edges, nodes: [ { index: 0, label: "0", x: 151.10959777777776, y: 74.13407404347826, width: 20, height: 10 }, { index: 1, label: 1, x: 78.23811577777778, y: 63.13114368450391, width: 20, height: 10 }, { index: 2, label: 2, x: 53.830455777777786, y: 56.470499118238834, width: 20, height: 10 }, { index: 3, label: 3, x: 95.60744011111112, y: 32.14497804347826, width: 20, height: 10 }, { index: 4, label: 4, x: 132.7609277777778, y: 11.447919043478262, width: 20, height: 10 }, { index: 5, label: 5, x: 157.47795077777778, y: 5, width: 20, height: 10 }, { index: 6, label: 6, x: 156.91214511111113, y: 108.57099704347827, width: 20, height: 10 }, { index: 7, label: 7, x: 147.48760777777778, y: 94.43419104347826, width: 20, height: 10 }, { index: 8, label: 8, x: 86.85462777777778, y: 90.67361837681159, width: 20, height: 10 }, { index: 9, label: 9, x: 78.6122197777778, y: 105.0978323768116, width: 20, height: 10 }, { index: 10, label: 10, x: 145.12453977777778, y: 26.902434043478262, width: 20, height: 10 }, { index: 11, label: 11, x: 107.3881117777778, y: 18.008172043478265, width: 20, height: 10 }, { index: 12, label: 12, x: 102.67637877777778, y: 76.29020837681159, width: 20, height: 10 }, { index: 13, label: 13, x: 150.07929677777778, y: 55.58865604347827, width: 20, height: 10 }, { index: 14, label: 14, x: 29.610261, y: 60.45924915921171, width: 20, height: 10 }, { index: 15, label: 15, x: 126.88158777777778, y: 78.97967604347826, width: 20, height: 10 }, { index: 16, label: 16, x: 139.77628677777778, y: 41.16444204347826, width: 20, height: 10 }, { index: 17, label: 17, x: 178.0941717777778, y: 38.23574504347826, width: 20, height: 10 }, { index: 18, label: 18, x: 51.81933055555555, y: 74.73650815921171, width: 20, height: 10 }, { index: 19, label: 19, x: 10, y: 46.197241159211714, width: 20, height: 10 }, { index: 20, label: 20, x: 70.95162311111112, y: 27.7939515140665, width: 20, height: 10 } ] })3a:T858,function nmChart(id, state, { initial, $div, data, simulation, invalidation }) { data.forEach((v, i) => { v.ox = state.nodes[i].ox; v.oy = state.nodes[i].oy; }); simulation.force("x").initialize(data); simulation.force("y").initialize(data); simulation.alphaTarget(0.3).restart(); const rect = { ...node.rect, width: 60, height: 40 }; const text = { ...node.text, dx: 30, dy: 20 }; const _div = d3.select($div); const _caption = _div.select("p"); if (state.caption) _caption.node().replaceChildren(state.caption); else _caption.node().replaceChildren(_html` `); const _svg = _div.select("svg"); const _links = _svg .select("g.edges") .selectAll("path") .data(d3.zip(initial, data)) .join( build({ append: "path", stroke: "red", "stroke-width": 3, fill: "red" }) ); const _nodes = _svg .select("g.nodes") .selectAll("g") .data(data, (d) => d.label) .join( build({ append: "g", call: [ build({ append: "rect", ...rect }), build({ append: "text", text: (d) => d.label, ...text }), nmDrag(simulation) ] }) ); const _value = _svg .selectAll("text.criteria") .data([""]) .join( build({ append: "text", classed: "criteria", text: 1, dx: "300", dy: "150", ...node.text }) ); const stdgraph = { nodes: initial.map((v, i) => ({ ...v, index: i, x: v.ox, y: v.oy })), edges: [] }; simulation.on("tick", () => { _nodes.style("transform", ({ x, y }) => `translate3d(${x}px, ${y}px, 0)`); _links.call(attrs, { d: ([o, d]) => { return Math.abs(o.ox - d.x) + Math.abs(o.oy - d.y) > 3 ? generateArrow(o.ox + 30, o.oy + 20, d.x + 30, d.y + 20, 4, 0, 0) : ""; } }); _value.text( nm_dm_imse(stdgraph, { nodes: data.map((v, i) => ({ ...v, index: i })), edges: [] }).value.toFixed(2) ); }); invalidation.then(() => simulation.stop()); $div.value = data; return $div; }3b:T971,function elChart( id, state, { initial, edges, $div, data, simulation, invalidation } ) { data.forEach((v, i) => { v.ox = state.nodes[i].ox; v.oy = state.nodes[i].oy; }); simulation.force("x").initialize(data); simulation.force("y").initialize(data); simulation.alphaTarget(0.3).restart(); const rect = { ...node.rect, width: 60, height: 40 }; const text = { ...node.text, dx: 30, dy: 20 }; const _div = d3.select($div); const _caption = _div.select("p"); if (state.caption) _caption.node().replaceChildren(state.caption); else _caption.node().replaceChildren(_html` `); const _svg = _div.select("svg"); const _links = _svg .select("g.edges") .selectAll("path") .data(edges) .join( build({ append: "path", "stroke-width": 3 // opacity: 0.6 }) ); const _nodes = _svg .select("g.nodes") .selectAll("g") .data(data, (d) => d.label) .join( build({ append: "g", call: [ build({ append: "rect", ...rect }), build({ append: "text", text: (d) => d.label, ...text }), nmDrag(simulation) ] }) ); const _value = _svg .selectAll("text.criteria") .data([""]) .join( build({ append: "text", classed: "criteria", text: 1, dx: "300", dy: "150", ...node.text }) ); const ratio = ({ source: s, target: t }) => (Math.pow(data[s].x - data[t].x, 2) + Math.pow(data[s].y - data[t].y, 2)) / (Math.pow(initial[s].ox - initial[t].ox, 2) + Math.pow(initial[s].oy - initial[t].oy, 2)); const colorScale = d3 .scaleLinear() .domain([0, 1, 3]) .range(["red", "blue", "red"]); const stdgraph = { nodes: initial.map((v, i) => ({ ...v, index: i, x: v.ox, y: v.oy })), edges }; simulation.on("tick", () => { _nodes.style("transform", ({ x, y }) => `translate3d(${x}px, ${y}px, 0)`); _links.call(attrs, { d: ({ source: s, target: t }) => `M${data[s].x + 30},${data[s].y + 20} L${data[t].x + 30},${data[t].y + 20}`, stroke: (st) => colorScale(ratio(st)) }); _value.text( eb_rsd(stdgraph, { nodes: data.map((v, i) => ({ ...v, index: i })), edges }).value.toFixed(2) ); }); invalidation.then(() => simulation.stop()); $div.value = data; return $div; }3c:T4f3,

📊 Résultats — graphes synthétiques

Initial

Scale

PFS

${makeTable(resultatsSynth12, _htl.html`On s'intéresse aux résultats de Scale et PFS.`)}3d:T502,

📊 Résultats — graphes synthétiques

Initial

VPSC

FTA

${makeTable(resultatsSynth34, _htl.html`FTA et VPSC ont tendance à produire des graphes étirés.`)}3e:T810,

📊 Résultats — graphes synthétiques

Initial

${makeTable(resultatsSynth5, _htl.html` `)}3f:T916,function makeTable(resultatsSynth, caption = "") { return _htl.html` ${resultatsSynth.map( row => _htl.html`${row.map(v => { if (typeof v !== "number") { return _htl.html`

${caption}
	Scaling	PFS	FTA	VPSC	RWordle-L	PFS'	PRISM	GTREE	Diamond
${v}`; } else { return _htl.html`	`; } })}` )}

`; }40:T4cc,function logo() { return _htl.html`

`; }41:Td47,viewof bibliography = bib( { Chen2020: _html`F. Chen, L. Piccinini, P. Poncelet, and A. Sallaberry. Node Overlap Removal Algorithms: an Extended Comparative Study. Journal of Graph Algorithms and Applications (JGAA), Vol. 24, no. 4, pp. 683-706, 2020. doi:${doi`10.7155/jgaa.00532`}`, Dwyer2005: _html`T. Dwyer, K. Marriott, and P. J. Stuckey. Fast node overlap removal. In Proceedings of the International Symposium on Graph Drawing (GD), pages 153–164. Springer, 2005. doi:${doi("10.1007/11618058_15")}.`, Strobelt2012: _html`H. Strobelt, M. Spicker, A. Stoffel, D. A. Keim, and O. Deussen. Rolled-out wordles: A heuristic method for overlap removal of 2D data representatives. Computer Graphics Forum, 31(3):1135–1144, 2012. doi:${doi("60910.1111/j.1467-8659.2012.03106.x")}.`, Meulemans2019: _html`Meulemans, W. Efficient Optimal Overlap Removal: Algorithms and Experiments. Computer Graphics Forum, 38: 713-723, 2019. doi:${doi("10.1111/cgf.13722")}`, Hayashi1998: _html`K. Hayashi, M. Inoue, T. Masuzawa, and H. Fujiwara. A layout adjustment problem for disjoint rectangles preserving orthogonal order. In Proceedings of the International Symposium on Graph Drawing (GD), pages 183–197. Springer, 1998. doi:${doi("10.1007/3-540-37623-2_14")}`, Nachmanson2016: _html`L. Nachmanson, A. Nocaj, S. Bereg, L. Zhang, and A. Holroyd. Node overlap removal by growing a tree. In Proceedings of the International Symposium on Graph Drawing and Network Visualization (GD), pages 33–43. Springer, 2016. doi:${doi("10.1007/978-3-319-50106-2_3")}.`, Gansner2010: _html`E. R. Gansner and Y. Hu. Efficient, proximity-preserving node overlap removal. Journal of Graph Algorithms and Applications, 14(1):53–74, 2010. doi:${doi("10.7155/jgaa.00198")}.`, Li2005: _html`W. Li, P. Eades, and N. Nikolov. Using spring algorithms to remove node overlapping. In Proceedings of the Asia-Pacific Symposium on Information Visualisation (APVis’05), pages 131–140, 2005.url:${url( "[PDF] crpit", "https://crpit.scem.westernsydney.edu.au/abstracts/CRPITV45Li.html" )}`, Marriott2003: _html`K. Marriott, P. Stuckey, V. Tam, and W. He. Removing node overlapping in graph layout using constrained optimization. Constraints, 8(2):143–171, 2003. doi:${doi("10.1023/A:1022371615202")}.`, Huang2007: _html`X. Huang, W. Lai, A. Sajeev, and J. Gao. A new algorithm for removing node overlapping in graph visualization. Information Sciences, 177(14):2821 – 2844, 2007. doi:${doi("10.1016/j.ins.2007.02.016")}.`, Misue1995: _html`K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. Journal of Visual Languages & Computing, 6(2):183–210, 1995. doi:${doi("10.1006/jvlc.1995.1010")}`, Hu2005: _html`Hu Y. Efficient, high-quality force-directed graph drawing. Mathematica journal. 10(1):37-71, 2005.`, Hachul2004: _html`S. Hachul and M. J¨unger. Drawing large graphs with a potential-fieldbased multilevel algorithm. In Proceedings of the International Symposium on Graph Drawing (GD), pages 285–295. Springer, 2004. doi:${doi("10.1007/978-3-540-31843-9_29")}.` }, { // citation: (citations) => _html`^{${defaultCitation(citations)}}`, numbered: false } )42:T41d,graphstateadd = ({ nodes: [ //lefty { x: 93, y: 40, label: "Jean", index: 8 }, { x: 83, y: 82, label: "Pierre" }, { x: 103, y: 55, label: "Pascal" }, { x: 133, y: 90, label: "Arnaud" }, { x: 68, y: 125, label: "Alexis" }, // righty { x: 253, y: 28, label: "Louise" }, { x: 243, y: 72, label: "Frédéric" }, { x: 318, y: 42, label: "Iris" }, { x: 342, y: 95, label: "Samy" }, { x: 292, y: 69, label: "Louis" }, { x: 232, y: 139, label: "Jérôme" }, { x: 302, y: 109, label: "Maximilien" } ].map(nodeDim(8)), edges: [ l(0, 8), l(0, 9), l(0, 10), l(0, 12), l(1, 8), l(1, 9), l(1, 10), l(2, 7), l(3, 12), l(3, 18), l(4, 13), l(4, 14), l(5, 13), l(5, 15), l(6, 15), l(6, 16), l(7, 16), l(7, 17), l(7, 18), l(7, 19), l(8, 10), l(9, 11), l(10, 11), l(10, 12), l(11, 12), l(12, 19), l(13, 14), l(13, 15), l(13, 17), l(14, 17), l(15, 17), l(16, 19), l(18, 19) ] })43:T5b5,nodesVPSC = [ { index: 0, label: "Julie", x: 26, y: 88, width: 52, height: 32 }, { index: 1, label: "Juliette", x: 121, y: 16, width: 71, height: 32 }, { index: 2, label: "Béranger", x: 111, y: 144, width: 86, height: 32 }, { index: 3, label: "Laure", x: 121, y: 208, width: 60, height: 32 }, { index: 4, label: "Agnes", x: 231, y: 116, width: 66, height: 32 }, { index: 5, label: "Laetitia", x: 267, y: 20, width: 72, height: 32 }, { index: 6, label: "Camille", x: 365, y: 84, width: 72, height: 32 }, { index: 7, label: "Elisabeth", x: 301, y: 180, width: 84, height: 32 }, { index: 8, label: "Jean", x: 94, y: 48, width: 53, height: 32 }, { index: 9, label: "Pierre", x: 83, y: 112, width: 62, height: 32 }, { index: 10, label: "Pascal", x: 104, y: 80, width: 63, height: 32 }, { index: 11, label: "Arnaud", x: 151, y: 112, width: 73, height: 32 }, { index: 12, label: "Alexis", x: 69, y: 176, width: 62, height: 32 }, { index: 13, label: "Louise", x: 254, y: 52, width: 66, height: 32 }, { index: 14, label: "Frédéric", x: 232, y: 84, width: 78, height: 32 }, { index: 15, label: "Iris", x: 324, y: 52, width: 42, height: 32 }, { index: 16, label: "Samy", x: 343, y: 116, width: 59, height: 32 }, { index: 17, label: "Louis", x: 300, y: 84, width: 58, height: 32 }, { index: 18, label: "Jérôme", x: 223, y: 180, width: 72, height: 32 }, { index: 19, label: "Maximilien", x: 303, y: 148, width: 98, height: 32 } ]44:T79d,nodelife = (point) => { const cssCoord = ({ x, y, width, height }) => `translate3d(${x - width / 2}px, ${y - height / 2}px, 0)`; function rect(rect, point) { rect.call(attrs, { fill: ({ fill }) => fill ?? (point ? "black" : "#eee"), stroke: ({ stroke }) => stroke ?? (point ? "black" : "lightgray"), x: ({ width }) => (point ? width / 2 - 2 : 0), y: ({ height }) => (point ? height / 2 - 2 : 0), width: ({ width }) => (point ? 4 : width), height: ({ height }) => (point ? 4 : height) }); } function text(text) { text .text(({ label }) => label) .call(attrs, { "font-size": point ? "0px" : "16px", "text-anchor": "middle", "dominant-baseline": "middle", dx: ({ width }) => width / 2, dy: ({ height }) => height / 2 }); } return [ (enter) => enter .append("g") .style("transform", cssCoord) .attr("opacity", 0) .call((g) => { g.transition().call(attrs, { opacity: 1, "font-style": ({ fontStyle }) => fontStyle }); g.append("rect").attr("rx", "2").call(rect, point); g.append("text").call(text); }), (update) => update.call((up) => { up.transition("position") .duration(1000) .call((t) => t .style("transform", cssCoord) .attr("font-style", ({ fontStyle }) => fontStyle) ); up.transition("style").call((t) => { t.select("text") .text(({ label }) => label) .call(attrs, { "font-size": point ? "0px" : "16px", dx: ({ width }) => width / 2, dy: ({ height }) => height / 2 }); t.select("rect").call(rect, point); }); return up; }), (exit) => exit.transition().attr("opacity", 0).remove() ]; }45:[{"id":"61302fa1299cff3fc0acbb15bb9d1c0c81a29b5c3de86cffc2adad4766d5abaeb32f334b74be7270257854a66bc2c674734860f003083b4dc2e695fc1a441472","href":"https://static.observableusercontent.com/files/61302fa1299cff3fc0acbb15bb9d1c0c81a29b5c3de86cffc2adad4766d5abaeb32f334b74be7270257854a66bc2c674734860f003083b4dc2e695fc1a441472","name":"image_2021-05-26_161621.png","type":"image/png","lastModified":1622038583570.927,"size":27567},{"id":"3735e8e9336662903a45e6d09c7144e1bd59ff659d56cc3dcecf10fd7399cd9d8a964f050242cd6c0bc9ac62c9830aba84f42132d89dd90e160288e89e7017a6","href":"https://static.observableusercontent.com/files/3735e8e9336662903a45e6d09c7144e1bd59ff659d56cc3dcecf10fd7399cd9d8a964f050242cd6c0bc9ac62c9830aba84f42132d89dd90e160288e89e7017a6","name":"mode_initial.svg","type":"image/svg+xml","lastModified":1622046199800.792,"size":52021},{"id":"6b56f736fc08419a685fc3b8f15376bb92545b93c7f58a431d6c972fa87544d3dcbfaa03c27ef53a5867a38a81325c9670372e23d71315de0f80980f115c4303","href":"https://static.observableusercontent.com/files/6b56f736fc08419a685fc3b8f15376bb92545b93c7f58a431d6c972fa87544d3dcbfaa03c27ef53a5867a38a81325c9670372e23d71315de0f80980f115c4303","name":"mode_pfs.svg","type":"image/svg+xml","lastModified":1622046199827.565,"size":64337},{"id":"224889a71b509083252a623c498612fd3585cb261bf9734f2b151d5c5d50e65d82901de35abf452cedf0271197b918d88e7d74c9c5401d7ab89f2672b87efa24","href":"https://static.observableusercontent.com/files/224889a71b509083252a623c498612fd3585cb261bf9734f2b151d5c5d50e65d82901de35abf452cedf0271197b918d88e7d74c9c5401d7ab89f2672b87efa24","name":"mode_rwordle.svg","type":"image/svg+xml","lastModified":1622046199809.286,"size":64469},{"id":"1684fa460b925758253bc7b379a6d049282e578af9d17c2eecac370d06c228a19bb0ba797acfad931ea4ac9f65249e98469198cbb3fed9d32bd9cd3d6ed7c09f","href":"https://static.observableusercontent.com/files/1684fa460b925758253bc7b379a6d049282e578af9d17c2eecac370d06c228a19bb0ba797acfad931ea4ac9f65249e98469198cbb3fed9d32bd9cd3d6ed7c09f","name":"mode_diamond.svg","type":"image/svg+xml","lastModified":1622046199823.553,"size":64968},{"id":"7f87bb3b56d680f6e749e3b6f5c339f7aed12699813ae2b6d12910c1179a7e7bc4418780f133e589af64bc6c4a53777e885f3f00ca8ccfadaafa6b08d70a058f","href":"https://static.observableusercontent.com/files/7f87bb3b56d680f6e749e3b6f5c339f7aed12699813ae2b6d12910c1179a7e7bc4418780f133e589af64bc6c4a53777e885f3f00ca8ccfadaafa6b08d70a058f","name":"mode_scale.svg","type":"image/svg+xml","lastModified":1622046199836.398,"size":64322},{"id":"34ef8ca089e136f0d2af1a0f7e13baed874719d15d99be3606034b78f66f1fb60f92c46750a70e986b7dc8e4d35186b882b747d95ae0c28503b0e2cd4130ca07","href":"https://static.observableusercontent.com/files/34ef8ca089e136f0d2af1a0f7e13baed874719d15d99be3606034b78f66f1fb60f92c46750a70e986b7dc8e4d35186b882b747d95ae0c28503b0e2cd4130ca07","name":"mode_prism.svg","type":"image/svg+xml","lastModified":1622046199773.938,"size":64234},{"id":"61a797168e50b73846f32df4c3c761396ed09e98c94506e73759f8c43bd7868fcda6f4d705bda27c11059d1ac829a5fe94dfc71f52f90596d956d041e66b8426","href":"https://static.observableusercontent.com/files/61a797168e50b73846f32df4c3c761396ed09e98c94506e73759f8c43bd7868fcda6f4d705bda27c11059d1ac829a5fe94dfc71f52f90596d956d041e66b8426","name":"mode_pfsp.svg","type":"image/svg+xml","lastModified":1622046199690.858,"size":64821},{"id":"050800d86b7bcee73debb28c6bccaff405ee7cbb9de735daaa9457e72385c9ad68f5b5c8a5315be611ee56991a433a24bf1139b85a70f4b523c55bcfd8fc064e","href":"https://static.observableusercontent.com/files/050800d86b7bcee73debb28c6bccaff405ee7cbb9de735daaa9457e72385c9ad68f5b5c8a5315be611ee56991a433a24bf1139b85a70f4b523c55bcfd8fc064e","name":"mode_vpsc.svg","type":"image/svg+xml","lastModified":1622046199775.393,"size":62596},{"id":"5c154547ca442fff3fd0c1f0e32464e1a6a4f18f128e0772d5becf0d08c7f7a75584e55ec85028e3b9d33d293a0a423a6ca418c5d879bd385372a843af8ed36a","href":"https://static.observableusercontent.com/files/5c154547ca442fff3fd0c1f0e32464e1a6a4f18f128e0772d5becf0d08c7f7a75584e55ec85028e3b9d33d293a0a423a6ca418c5d879bd385372a843af8ed36a","name":"mode_fta.svg","type":"image/svg+xml","lastModified":1622046199747.378,"size":62569},{"id":"f1f9e196035250ccf85609522f7f1519d10b97c2293d6d4184254dfc97fcffd9b2a0171c7ad482b027b4122ecc2f26c567cab0dd591cd746107b33408e99998d","href":"https://static.observableusercontent.com/files/f1f9e196035250ccf85609522f7f1519d10b97c2293d6d4184254dfc97fcffd9b2a0171c7ad482b027b4122ecc2f26c567cab0dd591cd746107b33408e99998d","name":"mode_gtree.svg","type":"image/svg+xml","lastModified":1622046199681.236,"size":64905},{"id":"6ff456680b9a3021e34f433333ee845c29389590d0a2cf3f1089fac2203d88418b7e9a52adc9331701f5c167b277eb94b6e69153c38d57d7e6122d111f44d20c","href":"https://static.observableusercontent.com/files/6ff456680b9a3021e34f433333ee845c29389590d0a2cf3f1089fac2203d88418b7e9a52adc9331701f5c167b277eb94b6e69153c38d57d7e6122d111f44d20c","name":"rand_100_25-RWordle-L.svg","type":"image/svg+xml","lastModified":1622065374522.485,"size":60514},{"id":"6ea0ce16aaf657fa93d5c1d019e53ce49e21bad7870198ab607057bc4620ef3c6a51339065ff34930c715d8c1207f8db93edf70278231dcf4053b49d9f50c1f8","href":"https://static.observableusercontent.com/files/6ea0ce16aaf657fa93d5c1d019e53ce49e21bad7870198ab607057bc4620ef3c6a51339065ff34930c715d8c1207f8db93edf70278231dcf4053b49d9f50c1f8","name":"rand_100_25-PFS.svg","type":"image/svg+xml","lastModified":1622065374505.553,"size":60026},{"id":"b5a7d8c1c9bf7e1defb17b91b26d45c4fe437f23b1d55b0886f3b0b6ebb89abc8f1e9670468e4d82100159e06ea0d3c84e61df4be3143146de525209ed859234","href":"https://static.observableusercontent.com/files/b5a7d8c1c9bf7e1defb17b91b26d45c4fe437f23b1d55b0886f3b0b6ebb89abc8f1e9670468e4d82100159e06ea0d3c84e61df4be3143146de525209ed859234","name":"rand_100_25-SCALE.svg","type":"image/svg+xml","lastModified":1622065374480.599,"size":55334},{"id":"f8124357b16fea8200d06191321575f2fdd280272013f877377d41ca675e370099d9f98d94163f3ba5562a93994ee52b866545114b9217e0a24f6fab791c612c","href":"https://static.observableusercontent.com/files/f8124357b16fea8200d06191321575f2fdd280272013f877377d41ca675e370099d9f98d94163f3ba5562a93994ee52b866545114b9217e0a24f6fab791c612c","name":"rand_100_25-PRISM.svg","type":"image/svg+xml","lastModified":1622065374436.756,"size":61046},{"id":"b79d0220c065f8854d66cb6605602754fce63fd28ff3b4aaeb59b67354dad847ba3a3472f0815f9a47bc88835d5ac326a585fe5f8c37175937f8229dabb4e488","href":"https://static.observableusercontent.com/files/b79d0220c065f8854d66cb6605602754fce63fd28ff3b4aaeb59b67354dad847ba3a3472f0815f9a47bc88835d5ac326a585fe5f8c37175937f8229dabb4e488","name":"rand_100_25-GTREE.svg","type":"image/svg+xml","lastModified":1622065374433.869,"size":61122},{"id":"f0389eebb502d6811b86a5766d22fb6aca33ed39e4ccec8fa9c1303ec1abb516b9d9daeb6a57ba7829272d8560da4e9e2e2bfe15d7c04ba7ad1e4f1c59d969af","href":"https://static.observableusercontent.com/files/f0389eebb502d6811b86a5766d22fb6aca33ed39e4ccec8fa9c1303ec1abb516b9d9daeb6a57ba7829272d8560da4e9e2e2bfe15d7c04ba7ad1e4f1c59d969af","name":"rand_100_25-Initial.svg","type":"image/svg+xml","lastModified":1622065374414.428,"size":33476},{"id":"86e4a0784979866bbda17b753785c541012ad8d1f4350ea2734676c9228d88589e693d669f083fefa0914ff5779f085764f946e286483558cd28b37f5ea746dc","href":"https://static.observableusercontent.com/files/86e4a0784979866bbda17b753785c541012ad8d1f4350ea2734676c9228d88589e693d669f083fefa0914ff5779f085764f946e286483558cd28b37f5ea746dc","name":"rand_100_25-PFS-.svg","type":"image/svg+xml","lastModified":1622065374456.443,"size":59009},{"id":"7d47e45bfa11db6839d4f6a9d1a6d4621f0c067394a7a6aa410ddbe43689cc8cb4ad077d91384c8590de295e7adcab622877b4b8f6d92eda0693460ed9f3cfe8","href":"https://static.observableusercontent.com/files/7d47e45bfa11db6839d4f6a9d1a6d4621f0c067394a7a6aa410ddbe43689cc8cb4ad077d91384c8590de295e7adcab622877b4b8f6d92eda0693460ed9f3cfe8","name":"rand_100_25-Diamond.svg","type":"image/svg+xml","lastModified":1622065374440.412,"size":61230},{"id":"fab4c6816c9cd3200015a8b44be3ce0b666b5d0bef594a53683831cf862bae5528550eae44b224a90b9fbd4e17555d146740d4299b83c77885da755abc84a208","href":"https://static.observableusercontent.com/files/fab4c6816c9cd3200015a8b44be3ce0b666b5d0bef594a53683831cf862bae5528550eae44b224a90b9fbd4e17555d146740d4299b83c77885da755abc84a208","name":"rand_100_25-VPSC.svg","type":"image/svg+xml","lastModified":1622065374452.918,"size":55201},{"id":"c22594c468a2bcb9708eb8a5d7923ecff91e67dce0b42ef9588096b3269062c6ba0918097b59ff350fbe56264a10b5c2443bb269d426380572cbbf2555d05bb9","href":"https://static.observableusercontent.com/files/c22594c468a2bcb9708eb8a5d7923ecff91e67dce0b42ef9588096b3269062c6ba0918097b59ff350fbe56264a10b5c2443bb269d426380572cbbf2555d05bb9","name":"rand_100_25-FTA.svg","type":"image/svg+xml","lastModified":1622065374376.286,"size":34378},{"id":"294eafcae34621831ac2fd42e14101bc97e4c800c07cf5e35ee301b0a228990806ceada46bb4c0b6973e65626c8bf35fcfc820c14a45b355f3628b6efe809f70","href":"https://static.observableusercontent.com/files/294eafcae34621831ac2fd42e14101bc97e4c800c07cf5e35ee301b0a228990806ceada46bb4c0b6973e65626c8bf35fcfc820c14a45b355f3628b6efe809f70","name":"image@8.png","type":"image/png","lastModified":1622073667860.768,"size":97752},{"id":"709ddcd8d3d5dc0acf1dbc58455285d5fcaa85374d5ae303860690e24e09f72c8ddc9cbf22e6da8ab68bf177794fdfcacd7c77f884bdfe87ec0608dc6ea96e70","href":"https://static.observableusercontent.com/files/709ddcd8d3d5dc0acf1dbc58455285d5fcaa85374d5ae303860690e24e09f72c8ddc9cbf22e6da8ab68bf177794fdfcacd7c77f884bdfe87ec0608dc6ea96e70","name":"image@7.png","type":"image/png","lastModified":1622073641720.139,"size":296785},{"id":"61b9eab1f45c6199fb902b2005305a408572b478418b16e43359d8c6d8e310caf492699ee10ae10ec6d3d74f2da0f5d9a80d08f78bdf7c8d6078203ce6a04e0f","href":"https://static.observableusercontent.com/files/61b9eab1f45c6199fb902b2005305a408572b478418b16e43359d8c6d8e310caf492699ee10ae10ec6d3d74f2da0f5d9a80d08f78bdf7c8d6078203ce6a04e0f","name":"image@6.png","type":"image/png","lastModified":1622072576131.083,"size":341543},{"id":"118c0f405467d78b7a2d1424f9f0b057d87eda72b94f506b2527a737c347f06d20cdff0029e1793066c5ec7a6ec404c937e1109ddcde9c82edd8097a0cc55963","href":"https://static.observableusercontent.com/files/118c0f405467d78b7a2d1424f9f0b057d87eda72b94f506b2527a737c347f06d20cdff0029e1793066c5ec7a6ec404c937e1109ddcde9c82edd8097a0cc55963","name":"image@5.png","type":"image/png","lastModified":1622072527413.573,"size":582987},{"id":"9f493dc6c9e9454989074eeca8a3ed07a8917d36c3ab6975834f01ea7c95223a2eca685004518502df4ea98c7e702f29576c2c2ed4b8958e74cd0f68a79eeecc","href":"https://static.observableusercontent.com/files/9f493dc6c9e9454989074eeca8a3ed07a8917d36c3ab6975834f01ea7c95223a2eca685004518502df4ea98c7e702f29576c2c2ed4b8958e74cd0f68a79eeecc","name":"image@4.png","type":"image/png","lastModified":1622072442494.597,"size":156391},{"id":"81bbc44a0cf27ce4836b13474baeed7e8e353ec7f47f13ef3ff975dec2942f6d84f21f7e1bac60ecd178ac4a5686bd07fdc9be6b15dcd03ff5f0fbc75915e0ca","href":"https://static.observableusercontent.com/files/81bbc44a0cf27ce4836b13474baeed7e8e353ec7f47f13ef3ff975dec2942f6d84f21f7e1bac60ecd178ac4a5686bd07fdc9be6b15dcd03ff5f0fbc75915e0ca","name":"image@3.png","type":"image/png","lastModified":1622072424936.157,"size":593793}] 2f:{"id":"3f248e5b2d8030d3","slug":"agora-presentation-labri","title":"Algorithmes de suppression de chevauchements, séminaire LaBRi, Bordeaux","thumbnail":"a28ac1683d6237de0dfd7e48c11035f5b54d6c3037522613c72cdd240f453df6","access_level":"public","create_time":"$D2021-05-19T18:29:44.666Z","update_time":"$D2022-06-27T18:18:20.117Z","view_time":null,"first_public_time":"$D2021-05-27T09:35:18.548Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"ffbcf8ce47e293f4","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":"starter_2024"},"version":6601,"publish_version":6601,"role":null,"authored":false,"authors":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null}],"members":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Algorithmes de suppression de chevauchements, séminaire LaBRi, Bordeaux","cells":[{"id":2204,"value":"%html\n
Algorithmes de suppression de chevauchements, séminaire LaBRi, Bordeaux","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6466,"value":"_md`> **Warning**:\n>\n> This presentation is tailored for fullscreen (1080p) viewing, some content may look broken for non-fullscreen viewing.\n>\n> To navigate, use arrows or click on the slide. Some slides are interactive, the click-to-next-slide is disabled on interactive elements, to go to the next slide click on title of the slide.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":0,"value":"## Algorithmes de suppression de chevauchements
Etude comparative\n\n${_.capitalize(timefr(Date.now()))}\n\n**Fati Chen**, Laurent Piccinini, \nPascal Poncelet & Arnaud Sallaberry\n\néquipe ADVANSE, LIRMM 🔗${url(\"advanse.lirmm.fr\", \"https://advanse.lirmm.fr\")}\n\n${url(\"observablehq.com/@stardisblue/agora-presentation-labri\",\"https://observablehq.com/@stardisblue/agora-presentation-labri\")}\n\n${logo()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":106,"value":"Introduction\n------------\n\n${_htl.html`
${intro}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":582,"value":"
\n
Principaux Algorithmes
\n
Graph Initial
\n \n
Un exemple de graphe: mode (dataset graphviz placé avec SPDF), échelle 1:1","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5257,"value":"initialId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4887,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
Scale
\n \n
Résultat de scale, échelle 1:10","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":4901,"value":"scaleId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4926,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
PFS ${cite(\"Misue1995\")}
\n \n \n
Résultat de PFS, échelle 1:8","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5205,"value":"pfsId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4967,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
PFS' ${cite(\"Hayashi1998\")}
\n \n
Résultat de PFS', échelle 1:3","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5208,"value":"pfspId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4993,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
VPSC ${cite(\"Dwyer2005\")}
\n \n
Résultat de VPSC, échelle 1:4","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5211,"value":"vpscId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5012,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
FTA ${cite(\"Huang2007\")}
\n \n
Résultat de FTA, échelle 1:3","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5215,"value":"ftaId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5037,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
PRISM ${cite(\"Gansner2010\")}
\n \n
Résultat de PRISM, échelle 1:2","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5218,"value":"prismId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5074,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
RWordle-L ${cite(\"Strobelt2012\")}
\n \n
Résultat de RWordle-L, échelle 2:3","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5225,"value":"rwordleId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5092,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
GTREE ${cite(\"Nachmanson2016\")}
\n \n
Résultat de GTREE, échelle 1:3","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5229,"value":"gtreeId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5117,"value":"
\n 1:3\n \n
Principaux Algorithmes
\n
Diamond ${cite(\"Meulemans2019\")}
\n \n
Résultat de Diamond, échelle 1:5","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5233,"value":"diamondId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4632,"value":"
\n
Principaux Algorithmes
\n ","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":4694,"value":"algopresentation = [\n { alg: scaleId, offset: [0, 0], scale: 0.05 },\n { alg: pfspId, offset: [0, 450], scale: 0.15 },\n { alg: vpscId, offset: [530, 0], scale: 0.15 },\n { alg: pfsId, offset: [700, 0], scale: 0.05 },\n { alg: ftaId, offset: [550, 580], scale: 0.15 },\n { alg: initialId, offset: [1300, 0], scale: 0.15 },\n { alg: rwordleId, offset: [750, 250], scale: 0.15 },\n { alg: prismId, offset: [1200, 600], scale: 0.15 },\n { alg: diamondId, offset: [1070, 150], scale: 0.1 },\n { alg: gtreeId, offset: [680, 390], scale: 0.15 }\n].map(\n ({ alg, offset, scale }) =>\n svg``\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4563,"value":"algorithms_mode = ({\n initial: await FileAttachment(\"mode_initial.svg\").text(),\n scale: await FileAttachment(\"mode_scale.svg\").text(),\n pfs: await FileAttachment(\"mode_pfs.svg\").text(),\n pfsp: await FileAttachment(\"mode_pfsp.svg\").text(),\n vpsc: await FileAttachment(\"mode_vpsc.svg\").text(),\n fta: await FileAttachment(\"mode_fta.svg\").text(),\n prism: await FileAttachment(\"mode_prism.svg\").text(),\n rwordle: await FileAttachment(\"mode_rwordle.svg\").text(),\n gtree: await FileAttachment(\"mode_gtree.svg\").text(),\n diamond: await FileAttachment(\"mode_diamond.svg\").text()\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4525,"value":"function svg2group(file, transform = \"scale(1)\", id = \"undefined\") {\n const _svg = d3.select(svg`${file}`);\n return _htl.svg`${[\n _svg.select(\"g.edges\").node(),\n _svg.select(\"g.nodes\").node()\n ]}`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5573,"value":"_htl.html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1703,"value":"Comment choisir ? \n-----------------\n\n### Quelles sont les propriétés à conserver lorsque l'on supprime les chevauchements ?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1773,"value":"Classes de critères \n-------------------\n22 critères\n\n${[\n { fr: \"Préservation de l'ordre orthogonal\", en: \"Orthogonal Ordering\", count: 4 },\n { fr: \"Minimisation de l'expansion\", en: \"Spread Minimisation\", count: 4 },\n { fr: \"Conservation du rapport de forme\", en: \"Global Shape Preservation\", count: 3 },\n { fr: \"Min. du mouvement des noeuds\", en: \"Node Movement Minimisation\", count: 8 },\n { fr: \"Préservation des longeurs des arêtes\", en: \"Edge Length Preservation\", count: 3 }\n].map(({fr, en, count})=>`- ${en} (${count}) *${fr}*\\n`) } ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2553,"value":"Orthogonal Ordering \n-------------------\n\n### Préserver l'ordre des noeuds sur ${tex`x`} et ${tex`y`}\n\n${chartOO()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3945,"value":"%md\n*code*\n\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2556,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3923,"value":"function ooDrag(_lines, $tex) {\n return d3\n .drag()\n .on(\"start\", function (event, d) {\n d3.select(this).raise().select(\"rect\").attr(\"stroke\", \"black\");\n })\n .on(\"drag\", function (event, d) {\n d3.select(this)\n .style(\n \"transform\",\n `translate3d(${(d.x = event.x)}px, ${(d.y = event.y)}px, 0)`\n )\n .select(\"rect\")\n .attr(\"fill\", d.x <= 70 || d.y <= 20 ? \"red\" : \"#eee\");\n\n _lines.attr(\"stroke\", ({ orient }) =>\n (d.x <= 70 && orient === \"x\") || (d.y <= 20 && orient === \"y\")\n ? \"red\"\n : \"blue\"\n );\n\n $tex.replaceChildren(\n tex`\\text{nni} = ${((d.x <= 70 ? 1 : 0) + (d.y <= 20 ? 1 : 0)) / 2}`\n );\n })\n .on(\"end\", function (event, d) {\n d3.select(this).select(\"rect\").attr(\"stroke\", \"lightgray\");\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1821,"value":"Orthogonal Ordering \n-------------------\n\n### Préserver l'ordre des noeuds sur ${tex`x`} et ${tex`y`}\n\n${tex.block`\\text{ni} = \\sum_{\\overset{(u, v) \\in V^2}{x_u > x_v}}{[x'_u < x'_v] }\n + \\sum_{\\overset{(u, v) \\in V^2}{y_u > y_v}}{[y'_u < y'_v]} \\tag1\n `}\n${tex.block`\\frac{\\text{ni}}{n(n-1)}\\tag2`}\n\n
(1) *Number of Inversions* ${cite(\"Strobelt2012\")} \n (2) *Normalised Number of Inversions* ${cite(\"Chen2020\")}.
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2858,"value":"Spread Minimisation\n-------------------\n### Minimiser l'expansion de ${tex`\\mathcal{E}`}\n\n${_htl.html`
${spread}`}\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3941,"value":"%md\n*code*\n\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2827,"value":"spreadStates = [\n { initial: \"no-hull\", bad: false, good: false },\n { initial: \"full\", bad: false, good: false },\n { initial: \"small\", bad: \"initial\", good: \"initial\" },\n { initial: \"small\", bad: \"small\", good: \"small\" }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2851,"value":"spreadHandle = statefulClick(viewof spread, spreadStates)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2830,"value":"viewof spread = SteppedSetter(\n ({ id, value, untracked }) => spreadGraph(id, value, untracked),\n spreadStates[0],\n {\n $div: _htl.html`
`,\n graphs: { initial: spreadInitial, bad: spreadBad, good: spreadGood }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2839,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2818,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2815,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2809,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3556,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1877,"value":"\nSpread Minimisation\n-------------------\n### Minimiser l'expansion de ${tex`\\mathcal{E}`}\n${chartsp()} ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3937,"value":"%md\n*code*\n\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2721,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1880,"value":"Global Shape Preservation\n-------------------------\n### Préserver le rapport de forme\n${_htl.html`
${global_shape}`}\n
\n${tex.block`\\max{\\left(\n \\frac{w'_{bb} \\times h_{bb}}\n {h'_{bb} \\times w_{bb}}, \n \\frac{h'_{bb} \\times w_{bb}}\n {w'_{bb} \\times h_{bb}}\\right)}`}\n *Improved Aspect Ratio* ${cite(\"Chen2020\")}
extended from ${cite(\"Li2005\")}
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3933,"value":"%md\n*code*\n\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3427,"value":"viewof global_shape = SteppedSetter(\n ({ id, value, untracked }) => gsChart(id, value, untracked),\n spreadStates[0],\n {\n $div: _htl.html`
`,\n graphs: { initial: spreadInitial, bad: gsBad, good: spreadGood }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3425,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3447,"value":"gsStates = spreadStates","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3434,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3438,"value":"gsHandle = statefulClick(viewof global_shape, gsStates)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3533,"value":"gs_bb_iar = criterias.GlobalShape.BoundingBox.ImprovedAspectRatio.criteria","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3952,"value":"%md\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4170,"value":"Global Shape Preservation\n-------------------------\n### Préserver le rapport de forme\n${await FileAttachment(\"image_2021-05-26_161621.png\").image()}\n
\n ${tex`gs\\_bb\\_iar = 1.25`}\n ${tex`gs\\_bb\\_iar = 1`}\n ${tex`gs\\_bb\\_iar = 1.33`}\n ${tex`gs\\_bb\\_iar = 2.25`}\n
\n
\n${tex.block`\\max{\\left(\n \\frac{w'_{bb} \\times h_{bb}}\n {h'_{bb} \\times w_{bb}}, \n \\frac{h'_{bb} \\times w_{bb}}\n {w'_{bb} \\times h_{bb}}\\right)}`}\n *Improved Aspect Ratio* ${cite(\"Chen2020\")}
extended from ${cite(\"Li2005\")}
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1883,"value":"Node Movement Minimisation \n------------------------\n### Minimiser le mouvement des noeuds\n\n${_htl.html`
${nm}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3879,"value":"%md\n*code*\n\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3650,"value":"nmStates = [\n {\n nodes: [\n { label: \"A\", ox: 55, oy: 110 },\n { label: \"B\", ox: 102, oy: 107 },\n { label: \"C\", ox: 87, oy: 74 },\n { label: \"D\", ox: 130, oy: 88 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`Initial ${tex`\\mathcal{E}`}`\n },\n {\n nodes: [\n { label: \"A\", ox: 21.83100439971076, oy: 122.56899510486951 },\n { label: \"B\", ox: 85.89153247215957, oy: 120.9199285514563 },\n { label: \"C\", ox: 84.18211368254869, oy: 63.841778151559375 },\n { label: \"D\", ox: 149.94017298158278, oy: 80.61963603432272 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`Utilisation de PRISM ${cite(\"Gansner2010\")}`\n },\n {\n nodes: [\n { label: \"A\", ox: 48.5, oy: 112 },\n { label: \"B\", ox: 108.5, oy: 117.5 },\n { label: \"C\", ox: 78.5, oy: 72 },\n { label: \"D\", ox: 138.500001, oy: 77.5 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`VPSC ${cite(\"Dwyer2005\")}\nsemble être une meilleure alternative.`\n }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3711,"value":"nmHandle = statefulClick(viewof nm, nmStates)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3646,"value":"viewof nm = SteppedSetter(\n ({ id, value, untracked }) => nmChart(id, value, untracked),\n nmStates[0],\n {\n $div: _htl.html`
\n
`,\n initial: nmStates[0].nodes,\n ...nmSimulation(nmStates[0].nodes),\n invalidation\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3585,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3701,"value":"function nmDrag(simulation) {\n return d3\n .drag()\n .on(\"start\", function (event, d) {\n d3.select(this).raise().select(\"rect\").attr(\"stroke\", \"black\");\n if (!event.active) simulation.alphaTarget(0.3).restart();\n event.subject.fx = event.subject.x;\n event.subject.fy = event.subject.y;\n })\n .on(\"drag\", function (event, d) {\n event.subject.fx = event.x;\n event.subject.fy = event.y;\n })\n .on(\"end\", function (event, d) {\n d3.select(this).select(\"rect\").attr(\"stroke\", \"lightgray\");\n // if (!event.active) simulation.alphaTarget(0.3);\n event.subject.fx = null;\n event.subject.fy = null;\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3666,"value":"function nmSimulation(data) {\n data = data.map((v) => ({ ...v }));\n const simulation = d3\n .forceSimulation(data)\n .force(\n \"x\",\n d3\n .forceX()\n .x((v) => v.ox)\n .strength(0.3)\n )\n .force(\n \"y\",\n d3\n .forceY()\n .y((v) => v.oy)\n .strength(0.3)\n );\n\n return { data, simulation };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3858,"value":"import { generateArrow } from \"@enjalot/drawing-an-arrow-with-an-arrowhead\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4275,"value":"nm_dm_imse = criterias.NodeMovement.DistanceMoved.ImprovedMeanSquaredEuclidean\n .criteria","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3885,"value":"%md\n----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3598,"value":"Node Movement Minimisation \n------------------------\n### Minimiser le mouvement des noeuds\n${tex.block`\\begin{aligned}\n shift(v) =& (x_v + x'_{bb} - x_{bb}, y_v + y'_{bb} - y_{bb} ) \\\\ \n scale(v) =& \\left(x_v \\times \\frac{w'_{bb}}{w_{bb}}, y_v \\times \\frac{h'_{bb}}{h_{bb}}\\right)\n\\end{aligned}`}\n${tex.block`\\boxed{\\frac{1}{n} \\times \\sum_{v \\in V}{{||v' - scale(shift(v))}||^2}}`}\n
Improved Mean Squared Euclidean ${cite(\"Chen2020\")} \nextended from ${cite(\"Strobelt2012\", \"Marriott2003\")}
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2385,"value":"Edge Length Preservation\n------------------------\n\n${_htl.html`
${el}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4035,"value":"elStates = [\n {\n nodes: [\n { label: \"A\", ox: 55, oy: 110 },\n { label: \"B\", ox: 102, oy: 107 },\n { label: \"C\", ox: 87, oy: 74 },\n { label: \"D\", ox: 130, oy: 88 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`Initial ${tex`\\mathcal{E}`}`\n },\n {\n nodes: [\n { label: \"A\", ox: 21.83100439971076, oy: 122.56899510486951 },\n { label: \"B\", ox: 85.89153247215957, oy: 120.9199285514563 },\n { label: \"C\", ox: 84.18211368254869, oy: 63.841778151559375 },\n { label: \"D\", ox: 149.94017298158278, oy: 80.61963603432272 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`Utilisation de PRISM ${cite(\"Gansner2010\")}`\n },\n {\n nodes: [\n { label: \"A\", ox: 48.5, oy: 112 },\n { label: \"B\", ox: 108.5, oy: 117.5 },\n { label: \"C\", ox: 78.5, oy: 72 },\n { label: \"D\", ox: 138.500001, oy: 77.5 },\n { label: \"E\", ox: 300, oy: 20 }\n ],\n caption: _html`VPSC ${cite(\"Dwyer2005\")}\nsemble être une meilleure alternative.`\n }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4042,"value":"elHandle = statefulClick(viewof el, elStates)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4034,"value":"viewof el = SteppedSetter(\n ({ id, value, untracked }) => elChart(id, value, untracked),\n elStates[0],\n {\n $div: _htl.html`
\n
`,\n initial: elStates[0].nodes,\n edges: [l(0, 1), l(0, 2), l(1, 2), l(1, 3), l(2, 3), l(3, 4)],\n ...nmSimulation(elStates[0].nodes),\n invalidation\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4045,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4136,"value":"eb_rsd = criterias.EdgeBased.RelativeStandardDeviation.criteria","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3962,"value":"Edge Length Preservation\n------------------------\n\n${tex.block`\\begin{aligned}\n r_{uv} &= \\frac{||u' - v'||}{||u - v||}, \\quad (u, v) \\in E\\\\\n \\overline{r} &= \\frac{1}{|E|}\\sum_{(u, v) \\in E}{r_{uv}}\\\\\n\\end{aligned}`}\n${tex.block`\\boxed{\\frac{\\sqrt{\n \\frac{1}{|E|} \\sum_{(u, v) \\in E}{(r_{uv} - \\overline{r})^2}}}\n {\\overline{r}}}`}\n\n
*Relative Standard Deviation* ${cite(\"Chen2020\")} \nextended from ${cite(\"Gansner2010\")}
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1892,"value":"Critères sélectionnés\n---------------------\n- *Normalised Number of Inversions* ${cite(\"Chen2020\")} \n *Number of Inversions* ${cite(\"Strobelt2012\")}\n- *Convex Hull Area* ${cite(\"Strobelt2012\")}\n- *Improved Aspect Ratio* ${cite(\"Chen2020\")} \n *Aspect Ratio* ${cite(\"Li2005\")}\n- *Improved Mean Squared Euclidean* ${cite(\"Chen2020\")} \n *Squared Euclidean* ${cite(\"Marriott2003\")} & *Mean Euclidean* ${cite(\"Strobelt2012\")}\n- *Relative Standard Deviation* ${cite(\"Chen2020\")} \n *R.S.D. Delaunay* ${cite(\"Gansner2010\")}\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1895,"value":"📏 Méthodologie 📐\n----------------\n\n**9 algorithmes**\n>
**Scaling** — **PFS** — **PFS'** — **VPSC** — **FTA** — \n **PRISM** — **RWordle-L** — **GTREE** — **Diamond**
\n\n**840 graphes synthétiques**^{[${url(\"ref\", \"https://github.com/agorajs/agora-dataset\")}]}\n>
random — random tree — small world — scale-free \n10 — 20 — 50 — 100 — 200 — 500 — 1000 noeuds \nplacés avec ${tex`FM^3`}${cite(\"Hachul2004\")}\n
\n\n**14 graphes réels**^{[${url(\"ref\", \"https://gitlab.com/graphviz/graphviz/-/tree/master/rtest/graphs\")}]}\n>
graphviz dataset placés avec *SFDP* ${cite(\"Hu2005\")}\n
\n\n**7 686 graphes à évaluer sur 5 critères**\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4455,"value":"🖥Implémentation\n----------------\n### Toutes les implémentations sont faites en JavaScript.\n\n*PFS*, *PFS'*, *FTA* et *Diamond* basés sur leurs articles📄.\n\n*VPSC* disponible en JS^{[${url(\"ref\",\"https://github.com/tgdwyer/WebCola\")}]}.\n\n*RWordle-L* porté depuis Java^{[${url(\"ref\",\"https://github.com/HendrikStrobelt/ditop_server/blob/master/src/main/java/de/hs8/graphics/RWordle.java\")}]}.\n\n*GTREE* et *PRISM* convertis⚙ en JS depuis *MSAGL*^{[${url(\"ref\",\"https://github.com/microsoft/automatic-graph-layout\")}]} avec l'aide de *Sharp-kit*^{[${url(\"ref\",\"https://github.com/SharpKit\")}]}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4434,"value":"📊 Résultats 🎉\n----------------","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5601,"value":"📊 Résultats — graphes synthétiques\n-----------------------------------\n\n${makeTable(resultatsSynth, \"Valeurs aggrégées des métriques selectionnées pour les graphes synthétiques.\")}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5612,"value":"resultatsSynth = [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1],\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1],\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0],\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2],\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5741,"value":"
\n
📊 Résultats — graphes synthétiques
\n${makeTable(resultatsSynthOO, _htl.html`L'ensemble des graphes obtiennent de bons résultats (<4%) sur ce critère. Scaling, PFS et PFS' sont parfaits (0%).`)}\n ","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5734,"value":"resultatsSynthOO = [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1],\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1].map(fade),\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0].map(\n fade\n ),\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2].map(\n fade\n ),\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2].map(fade)\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5859,"value":"📊 Résultats — graphes synthétiques\n-----------------------------------\n\n${makeTable(resultatsSynth2, \"Valeurs aggrégées des métriques selectionnées pour les graphes synthétiques.\")}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6003,"value":"resultatsSynth2 = [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1],\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1],\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0],\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2],\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5844,"value":"$3c","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5865,"value":"resultatsSynth12Id = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5835,"value":"resultatsSynth12 = {\n const fade12 = (v, i) => {\n return i > 2 ? fade(v) : v;\n };\n return [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1].map(fade12),\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1].map(fade12),\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0].map(\n fade12\n ),\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2].map(\n fade12\n ),\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2].map(\n fade12\n )\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5977,"value":"$3d","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":5995,"value":"resultatsSynth34 = {\n const fade12 = (v, i) => {\n return i < 3 || i > 4 ? fade(v) : v;\n };\n return [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1].map(fade12),\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1].map(fade12),\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0].map(\n fade12\n ),\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2].map(\n fade12\n ),\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2].map(\n fade12\n )\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6120,"value":"resultatsSynth34Id = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6028,"value":"$3e","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":6123,"value":"resultatsSynth5Id = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6040,"value":"resultatsSynth5 = {\n const fade12 = (v, i) => {\n return i < 5 ? fade(v) : v;\n };\n return [\n [_htl.html`Orthogonal Ordering`, 0, 0, 1, 1, 1, 0, 1, 1, 1].map(fade12),\n [_htl.html`Spread Minimisation`, 2, 2, 1, 0, 0, 1, 1, 1, 1].map(fade12),\n [_htl.html`Global Shape Preservation`, 0, 2, 1, 1, 0, 0, 0, 0, 0].map(\n fade12\n ),\n [_htl.html`Node Movement Minimisation`, 0, 2, 1, 0, 0, 1, 1, 2, 2].map(\n fade12\n ),\n [_htl.html`Edge Length Preservation`, 0, 1, 1, 0, 1, 0, 1, 1, 2].map(\n fade12\n )\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6152,"value":"📊 Résultats — temps\n-----------------------------------\n${makeTable(resultatsTimes, \"Valeurs aggrégées des temps pour les graphes synthétiques.\")}\n
${tex`>400ms`}
\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5837,"value":"fade = (v) => (typeof v === \"number\" ? v + 3 : v)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5700,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5620,"value":"resultSyntId = DOM.uid().id","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5828,"value":"randGraphs = ({\n initial: await FileAttachment(\"rand_100_25-Initial.svg\").text(),\n scale: await FileAttachment(\"rand_100_25-SCALE.svg\").text(),\n pfs: await FileAttachment(\"rand_100_25-PFS.svg\").text(),\n pfsp: await FileAttachment(\"rand_100_25-PFS-.svg\").text(),\n vpsc: await FileAttachment(\"rand_100_25-VPSC.svg\").text(),\n fta: await FileAttachment(\"rand_100_25-FTA.svg\").text(),\n prism: await FileAttachment(\"rand_100_25-PRISM.svg\").text(),\n rwordle: await FileAttachment(\"rand_100_25-RWordle-L.svg\").text(),\n gtree: await FileAttachment(\"rand_100_25-GTREE.svg\").text(),\n diamond: await FileAttachment(\"rand_100_25-Diamond.svg\").text()\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6155,"value":"resultatsTimes = {\n const fade = v => (typeof v === \"number\" ? v + 6 : v);\n return [\n [_htl.html`10`, 0, 0, 0, 0, 0, 0, 2, 2, 1].map(fade),\n [_htl.html`20`, 0, 0, 0, 0, 0, 0, 2, 2, 1].map(fade),\n [_htl.html`50`, 0, 0, 0, 0, 1, 0, 2, 2, 2].map(fade),\n [_htl.html`100`, 0, 0, 0, 0, 1, 0, 2, 2, 2].map(fade),\n [_htl.html`200`, 0, 0, 0, 0, 1, 0, 1, 1, 2],\n [_htl.html`500`, 0, 0, 0, 0, 1, 0, 1, 1, 2],\n [_htl.html`1000`, 0, 0, 0, 0, 1, 0, 1, 1, 2]\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6288,"value":"📊 Résultats — pour résumer 🤓\n-------------------------------\n\nPrioriser les graphes compactes ?\n
\n${_md`| | VPSC |\tRWordle-L\t| \n|---:|:---:|:---|\n|petit| |✅|\n|grand|✅| |`}\n
\n\n**En règle générale**: \n\n*PFS'*, *PRISM*, *GTREE* and *Diamond* obtiennent de bons résultats.\n\nPour de très grands graphes, utiliser plutot *PFS'* que *PRISM*.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5974,"value":"Bonus\n-----\n### L'influence de la dimension des noeuds sur les résultats\n
\n![image@7.png](${await FileAttachment(\"image@7.png\").url()})\n
Valeurs des métriques avec des noeuds de différents rapports de forme.
\n
\n
\n ![image@8.png](${await FileAttachment(\"image@8.png\").url()})\n
Aperçu des formes obtenues avec *PFS*, *FTA* et *VPSC*.
\n
","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1912,"value":"Démo\n----\n\nhttps://agorajs.github.io/","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2200,"value":"Merci de votre attention\n------------------------\n### Node Overlap Removal Algorithms: an Extended Study \n*Fati CHEN, Laurent Piccinini, Pascal Poncelet & Arnaud Sallaberry*\ndoi:${doi('10.7155/jgaa.00532')} \n\n**Fati CHEN** \n🔗[stardisblue.github.io](https://stardisblue.github.io) | 📚[github.com/stardisblue](https://github.com/stardisblue)\n\n**AGORAjs** \n🔗[agorajs.github.io](https://agorajs.github.io) | 📚 [github.com/agorajs](https://github.com/agorajs)\n\n${logo()}\n ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6375,"value":"$40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1908,"value":"%md\n## Références\n\n${bibliography}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1974,"value":"$41","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1976,"value":"cite = viewof bibliography","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1969,"value":"import { bib, defaultCitation } with { link } from \"@stardisblue/citations\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6255,"value":"Résultats — graphes synthétiques\n--------------------------------------\n${await FileAttachment(\"image@3.png\").image()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6256,"value":"Résultats — graphes réels\n--------------------------------------\n${await FileAttachment(\"image@4.png\").image()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6267,"value":"Résultats temps graphes synthétiques\n--------------------------------------\n${await FileAttachment(\"image@5.png\").image()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6276,"value":"Résultats temps graphes réels\n--------------------------------------\n${await FileAttachment(\"image@6.png\").image()}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6465,"value":"_md`\nremarques\n- aucun algo n'essaie de préserver les propriétés des arêtes.\n- aucun algo ne conserve la topologie.\n- on pourrait imaginer d'autres critères sur les arêtes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1073,"value":"%md\n\n---\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":27,"value":"%md\n_boring zone_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":129,"value":"%md\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1063,"value":"%md\n✨ Introduction","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":504,"value":"handleIntro = statefulClick(viewof intro, introStates)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":505,"value":"viewof intro = SteppedSetter(\n ({ id, value, untracked }) => graphIntro(id, value, untracked),\n introStates[0],\n _htl.html`
`\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1091,"value":"%md\n📚 data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1437,"value":"graphstate0 = ({\n nodes: [\n ...[\n { label: \"a = (40, 65)\" },\n { label: \"b = (120, 30)\" },\n { label: \"c = (110, 110)\" },\n { label: \"d = (120, 180)\" },\n { label: \"e = (230, 85)\" },\n { label: \"f = (270, 20)\" },\n { label: \"g = (359, 75)\" },\n { label: \"h = (290, 130)\" }\n ]\n .map(nodeDim())\n .map((v, i) => ({\n ...v,\n x: (i / 4 >= 1 ? 250 : 50) + v.width / 2,\n y: ((i % 4) + 1) * 32 + v.height / 2,\n fill: \"none\",\n stroke: \"none\",\n fontStyle: \"italic\"\n }))\n ],\n edges: []\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1045,"value":"graphstate1 = ({\n nodes: [\n { label: \"Julie\", x: 40, y: 65 },\n { label: \"Juliette\", x: 120, y: 30 },\n { label: \"Béranger\", x: 110, y: 110 },\n { label: \"Laure\", x: 120, y: 180 },\n { label: \"Agnes\", x: 230, y: 85 },\n { label: \"Laetitia\", x: 270, y: 20 },\n { label: \"Camille\", x: 359, y: 75 },\n { label: \"Elisabeth\", x: 290, y: 130 }\n ].map(nodeDim()),\n edges: [\n l(0, 1),\n l(0, 2),\n l(1, 2),\n l(1, 4),\n l(2, 3),\n l(4, 5),\n l(4, 6),\n l(4, 7),\n l(5, 6),\n // l(5, 7),\n l(6, 7)\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1108,"value":"$42","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1679,"value":"$43","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":329,"value":"introStates = {\n const combined = {\n nodes: [...graphstate1.nodes, ...graphstateadd.nodes],\n edges: [...graphstate1.edges, ...graphstateadd.edges]\n };\n\n return [\n {\n graph: graphstate0,\n caption: _md`Soit un ensemble de points ${tex`V`} dans un espace tel que ${tex`\\forall v \\in V, (x_v, y_v)`}`\n },\n {\n graph: graphstate1,\n point: true,\n caption: _md`Sous forme de dessin ${tex`\\mathcal{E}_G: V \\rightarrow \\mathbb{R}^2`} tel que ${tex`\\forall v\\in V, \\mathcal{E}_G(v) = (x_v, y_v)`}`\n },\n {\n graph: graphstate1,\n caption: _md`Affichés avec leurs labels ${tex`\\forall v \\in V, (w_v, h_v)`}`\n },\n { graph: combined, point: true, caption: _md`— ${tex`\\ `}` },\n { graph: combined, caption: _md`— ${tex`\\ `}` },\n {\n graph: { nodes: nodesVPSC, edges: combined.edges },\n caption: _md`${tex`\\mathcal{E}'_G(v)`} Résultat souhaité (généré avec VPSC${cite(\n \"Dwyer2005\"\n )})`\n }\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1080,"value":"%md\n🖼 render","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":964,"value":"function graphIntro(\n id,\n { graph: { nodes, edges }, caption = \"\", point = false },\n $div\n) {\n const div = d3.select($div);\n\n const svg = div.select(\"svg\");\n if (typeof caption === \"string\") {\n div.select(\"#caption\").text(caption);\n } else {\n div.select(\"#caption\").node().replaceChildren(caption);\n }\n\n const _edges = svg\n .selectAll(\"g.edges\")\n .data([linkEdges(nodes, edges)])\n .join(\"g\")\n .classed(\"edges\", true);\n\n const _nodes = svg\n .selectAll(\"g.nodes\")\n .data([nodes])\n .join(\"g\")\n .classed(\"nodes\", true);\n\n _nodes\n .selectAll(\"g\")\n .data(\n (d) => d,\n ({ index }) => index\n )\n .join(...nodelife(point));\n\n _edges\n .selectAll(\"path\")\n .data((d) => d)\n .join(...edgelife());\n\n return $div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":777,"value":"$44","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":717,"value":"function edgelife() {\n const getPath = ({ source, target }) =>\n `M ${source.x} ${source.y} L ${target.x} ${target.y}`;\n\n return [\n (enter) =>\n enter\n .append(\"path\")\n .call(attrs, {\n d: getPath,\n stroke: \"CornflowerBlue\",\n \"stroke-width\": 0\n })\n .call((p) => p.transition().delay(500).attr(\"stroke-width\", 2)),\n (update) =>\n update.call((up) => up.transition().duration(1000).attr(\"d\", getPath)),\n (exit) => exit.transition().attr(\"stroke-width\", 0).remove()\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1068,"value":"%md\n🚧 utils","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1049,"value":"l = (source, target) => ({ source, target })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":711,"value":"function linkEdges(nodes, edges) {\n const indexNodes = _.keyBy(nodes, \"index\");\n return _.map(edges, ({ source, target, ...rest }) => ({\n ...rest,\n source: indexNodes[source],\n target: indexNodes[target]\n }));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1230,"value":"nodeDim = (offset = 0) => (v, i) => ({\n ...v,\n index: i + offset,\n width: Math.ceil(measure(v.label)) + 20,\n height: 32\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1219,"value":"import { measure } from \"@stardisblue/measure-text\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":123,"value":"%md \n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":559,"value":"SteppedSetter = (get, value, untracked) =>\n Setter(\n { id: 0, value, untracked },\n { set: ({ untracked }, value, id) => ({ id, value, untracked }), get }\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":406,"value":"function statefulClick(callback, states = []) {\n if (states.length === 0) return () => {};\n let id = 1;\n return (e) => {\n if (e.shiftKey) {\n e.stopPropagation();\n if (id > 1) {\n id--;\n callback(states[id - 1], id - 1);\n }\n return;\n }\n if (id < states.length) {\n e.stopPropagation();\n\n callback(states[id], id);\n id++;\n }\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":448,"value":"%md\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2881,"value":"node = ({\n rect: {\n fill: \"#eee\",\n stroke: \"lightgray\",\n rx: 2\n },\n text: {\n \"font-size\": \"16px\",\n \"text-anchor\": \"middle\",\n \"dominant-baseline\": \"middle\"\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2876,"value":"%md\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":12,"value":"style","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2278,"value":"%css\n.katex-display{\n max-width: 40em;\n}\n\n.caption{\n color: gray;\n font-size: 0.75em; \n}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5,"value":"import {\n md as _md,\n html as _html,\n htl as _htl,\n slide,\n notes,\n style,\n keyBindings\n} from \"@stardisblue/slides\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":432,"value":"import { Setter } from \"@stardisblue/setter\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"md = multiMarkup(slide.md, cellmodes)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6523,"value":"htl = ({ ..._htl, html: slide.html })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2219,"value":"cellmodes = ({\n md: _md,\n html: _htl.html,\n slides: slide.md,\n full: slide.md(\"full\"),\n notes: notes.md,\n css: (s) => _htl.html`