/**
* @fileoverview Generate and draw a Confluent Drawing with and without crossings, Routing Graph and the normal graph for a chosen graph
* @author Michaela Tuscher
*/
var margin = {top: 5, right: 5, bottom: 5, left: 5};
var width = 800 - margin.left - margin.right;
var height = 600 - margin.top - margin.bottom;
var radius = 6;
var graph;
//dropdown list to choose graph
var listData = ["","miserables.json", "dolphins.json", "metaltrade.json", "easy1.json", "easy2.json", "easy3.json", "medium1.json", "medium2.json", "medium3.json", "difficult1.json", "difficult2.json", "difficult3.json"];
var div = d3.select("body")
.append("div")
.attr("class","title1")
.text("Please choose the graph to visualize ");
var select = div.append("select")
.attr("class","select")
.on("change",onChange);
var options = select
.selectAll("option")
.data(listData).enter()
.append("option")
.text(function(d){return d;})
.each(function(d) {
if (d === "") {
d3.select(this).property("disabled", true)
}
});
/**
* onChange
* is called when an item from the dropdown list is klicked, removes drawn graphs and resets zoom before new graph is loaded
*/
function onChange(){
selectedValue = d3.select("select").property("value")
//remove drawn graphs in SVGs and reset zoom
d3.selectAll("g > *").remove();
zoomH.transform(graph1, d3.zoomIdentity);
zoom2.transform(graph2, d3.zoomIdentity);
zoom3.transform(graph3, d3.zoomIdentity);
zoom4.transform(graph4, d3.zoomIdentity);
loadGraph(selectedValue);
};
//original graph
//create "textboxes" and element for drawing the graph
var svg1 = d3.select("body")
.append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom);
svg1.append("text")
.attr("x", width/2)
.attr("y", 30)
.attr("text-anchor", "middle")
.style("font-size", "16px")
.text("Original Graph");
nodeNr = svg1.append("text")
.attr("x", width/30)
.attr("y", 50)
.attr("text-anchor", "left")
.style("font-size", "16px");
edgeNr = svg1.append("text")
.attr("x", width/30)
.attr("y", 70)
.attr("text-anchor", "left")
.style("font-size", "16px");
var graph1 = svg1.append("g");
//create "textboxes" and element to draw routing graph
var svg2 = d3.select("body")
.append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom);
svg2.append("text")
.attr("x", width/2)
.attr("y", 30)
.attr("text-anchor", "middle")
.style("font-size", "16px")
.text("Routing Graph");
nodeNr2 = svg2.append("text")
.attr("x", width/30)
.attr("y", 50)
.attr("text-anchor", "left")
.style("font-size", "16px");
edgeNr2 = svg2.append("text")
.attr("x", width/30)
.attr("y", 70)
.attr("text-anchor", "left")
.style("font-size", "16px");
legend = svg2.append("text")
.attr("x", width/30)
.attr("y", 90)
.attr("text-anchor", "left")
.style("font-size", "16px");
var graph2 = svg2.append("g");
//create "textboxes" and element to draw confluent drawing
var svg3 = d3.select("body")
.append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom);
svg3.append("text")
.attr("x", width/2)
.attr("y", 30)
.attr("text-anchor", "middle")
.style("font-size", "16px")
.text("Confluent Drawing");
nodeNr3 = svg3.append("text")
.attr("x", width/30)
.attr("y", 50)
.attr("text-anchor", "left")
.style("font-size", "16px");
edgeNr3 = svg3.append("text")
.attr("x", width/30)
.attr("y", 70)
.attr("text-anchor", "left")
.style("font-size", "16px");
legend2 = svg3.append("text")
.attr("x", width/30)
.attr("y", 90)
.attr("text-anchor", "left")
.style("font-size", "16px");
var graph3 = svg3.append("g");
//create "textboxes" and elements to draw confluent drawing without crossings
var svg4 = d3.select("body")
.append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom);
svg4.append("text")
.attr("x", width/2)
.attr("y", 30)
.attr("text-anchor", "middle")
.style("font-size", "16px")
.text("Confluent Drawing without Crossing Artifacts");
nodeNr4 = svg4.append("text")
.attr("x", width/30)
.attr("y", 50)
.attr("text-anchor", "left")
.style("font-size", "16px");
edgeNr4 = svg4.append("text")
.attr("x", width/30)
.attr("y", 70)
.attr("text-anchor", "left")
.style("font-size", "16px");
legend3 = svg4.append("text")
.attr("x", width/30)
.attr("y", 90)
.attr("text-anchor", "left")
.style("font-size", "16px");
var graph4 = svg4.append("g");
/**
* loadGraph
* loads graph from JSON file according to the selected graph from the dropdown list
* @param selectedValue name of the chosen graph to be loaded
*/
function loadGraph(selectedValue){
d3.json("graphs/" + selectedValue, function(error, graph) {
if (error) throw error;
graphC = JSON.parse(JSON.stringify(graph));
createGraph(graph);
createConfluent(graphC, new cola.d3adaptor(d3));
});
}
/**
* createGraph
* creates the visualization of the original graph
* @param graph the graph to be drawn as node- and edgelist
*/
function createGraph(graph){
var color = d3.scaleOrdinal(d3.schemeCategory20);
var simulation = d3.forceSimulation()
.force("link", d3.forceLink().id(function(d) {return d.index;}))
.force("charge", d3.forceManyBody().strength(-100))
.force("center", d3.forceCenter(width/2, height/2));
//create link and node elements to be drawn
var link = graph1.append("g")
.attr("class", "links")
.selectAll("line")
.data(graph.links)
.enter().append("line");
var node = graph1.append("g")
.attr("class", "nodes")
.selectAll("circle")
.data(graph.nodes)
.enter().append("circle")
.attr("r", radius)
.attr("fill", function(d, i) {return color(i);})
.call(d3.drag()
.on("start", dragstarted)
.on("drag", dragged)
.on("end", dragended));
node.append("title")
.text(function(d) {return d.id;});
simulation
.nodes(graph.nodes)
.on("tick", ticked);
simulation.force("link")
.links(graph.links);
nodeNr.text("# Nodes: " + Object.keys(graph.nodes).length);
edgeNr.text("# Edges: " + Object.keys(graph.links).length);
/**
* ticked
* is called every tick of the simulation, sets positions of nodes and links
*/
function ticked() {
node
.attr("cx", function(d) {return d.x;})
.attr("cy", function(d) {return d.y;});
link
.attr("x1", function(d) {return d.source.x;})
.attr("y1", function(d) {return d.source.y;})
.attr("x2", function(d) {return d.target.x;})
.attr("y2", function(d) {return d.target.y;});
}
function dragstarted(d) {
if (!d3.event.active) simulation.alphaTarget(0.3).restart();
d.fx = d.x;
d.fy = d.y;
}
function dragged(d) {
d.fx = d3.event.x;
d.fy = d3.event.y;
}
function dragended(d) {
if (!d3.event.active) simulation.alphaTarget(0);
d.fx = null;
d.fy = null;
}
} //end of createGraph
var zoomH = d3.zoom()
.on("zoom", zoomed);
/**
* zoomed
* is used to zoom the first graph
*/
function zoomed(){
graph1.attr("transform", d3.event.transform);
}
zoomH(svg1);
var zoom3 = d3.zoom()
.on("zoom", zoomed3);
/**
* zoomed3
* is used to zoom the third graph
*/
function zoomed3(){
graph3.attr("transform", d3.event.transform);
}
zoom3(svg3);
var zoom2 = d3.zoom()
.on("zoom", zoomed2);
/**
* zoomed2
* is used to zoom the second graph
*/
function zoomed2(){
graph2.attr("transform", d3.event.transform);
}
zoom2(svg2);
var zoom4 = d3.zoom()
.on("zoom", zoomed4);
/**
* zoomed2
* is used to zoom the second graph
*/
function zoomed4(){
graph4.attr("transform", d3.event.transform);
}
zoom4(svg4);
//routing graph
/**
* createConfluent
* creates and draws routing graph, confluent drawing and confluent drawing without crossings
* @param graph the graph to visualize
* @param cola cola d3 adaptor
*/
function createConfluent(graph, cola){
var color = d3.scaleOrdinal(d3.schemeCategory20);
var neighbours = {};
var splitNeighb = {};
var paths = [];
var splitPaths = [];
var neighbIn = {};
var powerGraph;
cola
.avoidOverlaps(true)
.handleDisconnected(true)
.size([width, height]);
var simulation2 = d3.forceSimulation()
.force("link", d3.forceLink().id(function(d) {return d.index;}))
.force("charge", d3.forceManyBody().strength(-50))
.force("center", d3.forceCenter(width/2, height/2));
var simulation3 = d3.forceSimulation()
.force("link", d3.forceLink().distance(30).id(function(d) {return d.index;}))
.force("charge", d3.forceManyBody().strength(-50))
.force("center", d3.forceCenter(width/2, height/2));
//get powergraph
cola
.nodes(graph.nodes)
.links(graph.links)
.powerGraphGroups(function (d) {powerGraph = d;});
var n = graph.nodes.length;
var edges = [];
var nodes = graph.nodes.slice(0);
nodes.forEach((v, i) => v.index = i);
//create routing graph
createRoutingGraph(powerGraph, nodes, edges, neighbours, neighbIn, n);
var splitNodes = nodes.map(a => ({...a}));
var splitEdges = edges.map(a => ({...a}));
var splitNeighb = JSON.parse(JSON.stringify(neighbours));
//split routing nodes for confluent drawing without crossings
splitGraphNodes(neighbIn, neighbours, splitNodes, splitNeighb, splitEdges, n, nodes);
nodeNr2.text("# Nodes: " + nodes.length);
edgeNr2.text("# Edges: " + edges.length);
legend.text("# Routing Nodes (black): " + (nodes.length-n));
//compute shortest paths for all edges of original graph
for (var i = 0; i<graph.links.length; i++){
paths[i]=shortestPath(neighbours,graph.links[i], n);
}
//compute shortest path in split routing graph
for (var i = 0; i<graph.links.length; i++){
splitPaths[i]=shortestPath(splitNeighb,graph.links[i], n);
}
var eConfl = edges.map(a => ({...a}));
var nConfl = nodes.map(a => ({...a}));
//create link and node elements of the routing graph to be drawn
var link = graph2.append("g")
.attr("class", "links")
.selectAll("line")
.data(edges)
.enter().append("line")
.attr("stroke-width", function(d) {return Math.sqrt(d.value);});
var node = graph2.append("g")
.attr("class", "nodes")
.selectAll("circle")
.data(nodes)
.enter().append("circle")
.attr("r", radius)
.attr("fill", function(d) {if (d.index<n) {return color(d.index);} else {return "black";}})
.call(cola.drag)
.on('mouseup', function (d) {
d.fixed = 0;
cola.alpha(1);
});
node.append("title")
.text(function(d) {if (d.index <n){return d.id;} else {return "Group " + d.id}});
//start cola simulation for routing graph
cola
.symmetricDiffLinkLengths(20, 0.3)
.nodes(nodes)
.links(edges)
.start(30);
cola.on("tick", function() {
link
.attr("x1", function(d){return d.source.x;})
.attr("y1", function(d){return d.source.y;})
.attr("x2", function(d){return d.target.x;})
.attr("y2", function(d){return d.target.y;});
node
.attr("cx", function (d){return d.x;})
.attr("cy", function (d){return d.y;});
});
//confluent drawing
/**
* curveFunction
* calculates the curve between the nodes for the given control points
*/
var curveFunction = d3.line().curve(d3.curveBasis);
//create link and node elements for the confluent drawing to be drawn
var linkConfl = graph3.append("g")
.attr("class", "linksC")
.selectAll("path")
.data(paths)
.enter().append("path");
var nodeConfl = graph3.append("g")
.selectAll("circle")
.data(nConfl)
.enter().append("circle")
.attr("class", function (d) {if (d.index<n) {return "nodes";} else {return "rnode";}})
.attr("r", radius)
.attr("fill", function(d) {if (d.index<n) {return color(d.index);} else {return "white";}})
.call(d3.drag()
.on("start", dragstarted)
.on("drag", dragged)
.on("end", dragended));
nodeConfl.append("title")
.text(function(d) {if (d.index <n){return d.id;} else {return "Group " + d.id}});
nodeNr3.text("# Nodes: " + graph.nodes.length);
edgeNr3.text("# Edges: " + graph.links.length);
legend2.text("# Control Points (invisible): " + (nConfl.length-n));
//simulation for confluent drawing
simulation2
.nodes(nConfl)
.on("tick", ticked);
simulation2.force("link")
.links(eConfl);
/**
* ticked
* is called every tick of the simulation, sets positions of nodes and links in the confluent drawing
*/
function ticked() {
//for every path, add x- and y-coordinates of the nodes in the path to the list of control points for the curve
linkConfl
.attr("d", function(d){
var controlP = [];
d.forEach(function (n){
controlP.push([nConfl[n].x, nConfl[n].y]);
});
return curveFunction(controlP);
});
nodeConfl
.attr("cx", function(d) {return d.x;})
.attr("cy", function(d) {return d.y;});
}
function dragstarted(d) {
if (!d3.event.active) simulation2.alphaTarget(0.3).restart();
d.fx = d.x;
d.fy = d.y;
}
function dragged(d) {
d.fx = d3.event.x;
d.fy = d3.event.y;
}
function dragended(d) {
if (!d3.event.active) simulation2.alphaTarget(0);
d.fx = null;
d.fy = null;
}
//create link and node elements for the confluent drawing without crossings to be drawn
var linkConflSplit = graph4.append("g")
.attr("class", "linksC")
.selectAll("path")
.data(splitPaths)
.enter().append("path");
var nodeConflSplit = graph4.append("g")
.selectAll("circle")
.data(splitNodes)
.enter().append("circle")
.attr("class", function (d) {if (d.index<n) {return "nodes";} else {return "rnode";}})
.attr("r", radius)
.attr("fill", function(d) {if (d.index<n) {return color(d.index);} else {return "white";}})
.call(d3.drag()
.on("start", dragstarted2)
.on("drag", dragged2)
.on("end", dragended2));
nodeConflSplit.append("title")
.text(function(d) {if (d.index <n){return d.id;} else {return "Group " + d.id}});
nodeNr4.text("# Nodes: " + graph.nodes.length);
edgeNr4.text("# Edges: " + graph.links.length);
legend3.text("# Control Points (invisible): " + (splitNodes.length-n));
//simulation for the confluent drawing without crossings
simulation3
.nodes(splitNodes)
.on("tick", ticked2);
simulation3.force("link")
.links(splitEdges);
/**
* ticked2
* is called every tick of the simulation, sets positions of nodes and links in the confluent drawing without crossings
*/
function ticked2() {
//for every path, add x- and y-coordinates of the nodes in the path to the list of control points for the curve
linkConflSplit
.attr("d", function(d){
var controlP = [];
d.forEach(function (n){
controlP.push([splitNodes[n].x, splitNodes[n].y]);
});
return curveFunction(controlP);
});
nodeConflSplit
.attr("cx", function(d) {return d.x;})
.attr("cy", function(d) {return d.y;});
}
function dragstarted2(d) {
if (!d3.event.active) simulation3.alphaTarget(0.3).restart();
d.fx = d.x;
d.fy = d.y;
}
function dragged2(d) {
d.fx = d3.event.x;
d.fy = d3.event.y;
}
function dragended2(d) {
if (!d3.event.active) simulation3.alphaTarget(0);
d.fx = null;
d.fy = null;
}
} //end of createConfluent
/**
* addNeighbour
* adds the given nodes respectively to their list of neighbours (used for edges with source and target node). adds source node to target's neighbours and vice versa
* @param source source node of the edge
* @param target target node of the edge
*/
function addNeighbour(neighbours, source, target){
if (neighbours[source] === undefined) {
neighbours[source] = [];
}
//add edge source to target to neighbourlist
neighbours[source].push(target);
if (neighbours[target] === undefined) {
neighbours[target] = [];
}
//add edge target to source to neighbourlist
neighbours[target].push(source);
}
/**
* shortestPath
* finds shortest path in routing graph for edge in original graph, returns path as array of node indices
* @param neigh the list of neighbours for each node
* @param edge the edge containing source and target node, the path is found from source to target
* @param n number of nodes
* @return path from source to target, as list of node indices, containing only routing nodes between source and target node
*/
function shortestPath(neigh, edge, n){
var source = edge.source;
var target = edge.target;
if (source == target){
return;
}
var queue = [source];
var visited = {source: true};
var predecessor = {};
var tail = 0;
while (tail < queue.length){
var u = queue[tail++];
var nb = neigh[u];
for (var i = 0; i < nb.length; ++i){
var v = nb[i];
if (visited[v]){
continue;
}
visited[v] = true;
if (v == target){ //reached target node
var path = [v];
path.push(u);
while (u != source){
u = predecessor[u];
path.push(u);
}
path.reverse();
return path;
}
//avoid routing paths through "normal" graph nodes
if(!(v>=n)){
continue;
}
predecessor[v] = u;
queue.push(v);
}
}
}
/**
* splitGraphNodes
* splits routing nodes with more than 1 incoming and more than 1 outgoing edge. adjusts neighbour-, node- and edgelist according to splits
* @param neighbIn list with incoming neighbours for all routing nodes
* @param neighbours total list of neighbours for each node
* @param splitNodes list with all graph- and routing nodes, new split nodes will be added to that list
* @param splitNeighb same as neighbIn, but the list will be adjustet to the node splits, neighbours will be added or deleted
* @param splitEdges list with edges from the routing graph, will be adjustet to node splits, edges will be added or deleted
* @param n number of graph nodes
* @param nodes list of graph nodes
*/
function splitGraphNodes(neighbIn, neighbours, splitNodes, splitNeighb, splitEdges, n, nodes){
var l = nodes.length;
for (var i = n; i<nodes.length; i++){
if(((neighbIn[i].length >1) && ((neighbours[i].length - neighbIn[i].length)>1))){ //more than 1 incoming edge and more than 1 outgoing edge
//"split" node, create new one
var nid = nodes[i].id + ".2";
splitNodes.push({id: nid, index: l});
var newNeighb = neighbIn[i]; //incoming neighbours of splitted node
splitNeighb[l] = newNeighb; //give new node incoming edges of old node
//link old and new node together as neighbours
splitNeighb[l].push(i);
splitNeighb[i].push(l);
//push new edges and delete the neighbour nodes of the new node in the old node
for (var j = 0; j< newNeighb.length; j++){
var t = newNeighb[j];
var index = splitNeighb[i].indexOf(t);
var indexE = splitEdges.findIndex(e=>(e.source == i && e.target == t));
var indexI = splitNeighb[t].indexOf(i);
splitNeighb[t].push(l);
splitNeighb[t].splice(indexI,1); //delete
if(!(indexE==-1)){
splitEdges.splice(indexE,1); //delete
}
splitEdges.push({source: l, target: t});
if(!(index==-1)){
splitNeighb[i].splice(index,1); //delete
}
}
l++;
}
}
}
/**
* createRoutingGraph
* creates node- and edge-list for the routing graph taking the informations stored in powergraph, also creates neighbourlist for all nodes in routing graph and records incoming edges of routing nodes
* @param powerGraph the powergraph used to create the routing graph
* @param nodes a list of graph nodes, routing nodes will be added to the list
* @param edges an empty list where routing edges will be added
* @param neighbours an empty list which will be filled with neighbours of all nodes
* @param neighbIn an empty list which will be filled with incoming neighbours for all routing nodes
* @param n number of graph nodes
*/
function createRoutingGraph(powerGraph, nodes, edges, neighbours, neighbIn, n){
powerGraph.groups.forEach(g => {
var sourceInd = g.index = g.id + n;
nodes.push(g);
if (typeof g.leaves != 'undefined'){
g.leaves.forEach(v => {edges.push({ source: sourceInd, target: v.index });
addNeighbour(neighbours, sourceInd, v.index);
if (neighbIn[sourceInd] == undefined){
neighbIn[sourceInd] = [];
}
if (neighbIn[v.index] == undefined){
neighbIn[v.index] = [];
}
//for leave-nodes, add the edge to the array for incoming edges (important for split graph)
neighbIn[sourceInd].push(v.index);
neighbIn[v.index].push[sourceInd];
});
}
if (typeof g.groups != 'undefined'){
g.groups.forEach(gg => {edges.push({ source: sourceInd, target: gg.id + n });
addNeighbour(neighbours, sourceInd, gg.id+n);
if (neighbIn[sourceInd] == undefined) {
neighbIn[sourceInd] = [];
}
if (neighbIn[gg.id+n] == undefined) {
neighbIn[gg.id+n] = [];
}
//for subgroup-nodes, add the edge to the array for incoming edges (important for split graph)
neighbIn[sourceInd].push(gg.id+n);
neighbIn[gg.id+n].push[sourceInd];
});
}
});
//outgoing edges
powerGraph.powerEdges.forEach(e=> {
edges.push({ source: e.source.index, target: e.target.index });
addNeighbour(neighbours, e.source.index, e.target.index);
});
}