1 /** 2 * Constructs a new, empty rollup network layout. Layouts are not typically 3 * constructed directly; instead, they are added to an existing panel via 4 * {@link pv.Mark#add}. 5 * 6 * @class Implements a network visualization using a node-link diagram where 7 * nodes are rolled up along two dimensions. This implementation is based on the 8 * "PivotGraph" designed by Martin Wattenberg: 9 * 10 * <blockquote>The method is designed for graphs that are "multivariate", i.e., 11 * where each node is associated with several attributes. Unlike visualizations 12 * which emphasize global graph topology, PivotGraph uses a simple grid-based 13 * approach to focus on the relationship between node attributes & 14 * connections.</blockquote> 15 * 16 * This layout requires two psuedo-properties to be specified, which assign node 17 * positions along the two dimensions {@link #x} and {@link #y}, corresponding 18 * to the left and top properties, respectively. Typically, these functions are 19 * specified using an {@link pv.Scale.ordinal}. Nodes that share the same 20 * position in <i>x</i> and <i>y</i> are "rolled up" into a meta-node, and 21 * similarly links are aggregated between meta-nodes. For example, to construct 22 * a rollup to analyze links by gender and affiliation, first define two ordinal 23 * scales: 24 * 25 * <pre>var x = pv.Scale.ordinal(nodes, function(d) d.gender).split(0, w), 26 * y = pv.Scale.ordinal(nodes, function(d) d.aff).split(0, h);</pre> 27 * 28 * Next, define the position psuedo-properties: 29 * 30 * <pre> .x(function(d) x(d.gender)) 31 * .y(function(d) y(d.aff))</pre> 32 * 33 * Linear and other quantitative scales can alternatively be used to position 34 * the nodes along either dimension. Note, however, that the rollup requires 35 * that the positions match exactly, and thus ordinal scales are recommended to 36 * avoid precision errors. 37 * 38 * <p>Note that because this layout provides a visualization of the rolled up 39 * graph, the data properties for the mark prototypes (<tt>node</tt>, 40 * <tt>link</tt> and <tt>label</tt>) are different from most other network 41 * layouts: they reference the rolled-up nodes and links, rather than the nodes 42 * and links of the full network. The underlying nodes and links for each 43 * rolled-up node and link can be accessed via the <tt>nodes</tt> and 44 * <tt>links</tt> attributes, respectively. The aggregated link values for 45 * rolled-up links can similarly be accessed via the <tt>linkValue</tt> 46 * attribute. 47 * 48 * <p>For undirected networks, links are duplicated in both directions. For 49 * directed networks, use <tt>directed(true)</tt>. The graph is assumed to be 50 * undirected by default. 51 * 52 * @extends pv.Layout.Network 53 * @see <a href="http://www.research.ibm.com/visual/papers/pivotgraph.pdf" 54 * >"Visual Exploration of Multivariate Graphs"</a> by M. Wattenberg, CHI 2006. 55 */ 56 pv.Layout.Rollup = function() { 57 pv.Layout.Network.call(this); 58 var that = this, 59 nodes, // cached rollup nodes 60 links, // cached rollup links 61 buildImplied = that.buildImplied; 62 63 /** @private Cache layout state to optimize properties. */ 64 this.buildImplied = function(s) { 65 buildImplied.call(this, s); 66 nodes = s.$rollup.nodes; 67 links = s.$rollup.links; 68 }; 69 70 /* Render rollup nodes. */ 71 this.node 72 .data(function() { return nodes; }) 73 .size(function(d) { return d.nodes.length * 20; }); 74 75 /* Render rollup links. */ 76 this.link 77 .interpolate("polar") 78 .eccentricity(.8); 79 80 this.link.add = function(type) { 81 return that.add(pv.Panel) 82 .data(function() { return links; }) 83 .add(type) 84 .extend(this); 85 }; 86 }; 87 88 pv.Layout.Rollup.prototype = pv.extend(pv.Layout.Network) 89 .property("directed", Boolean); 90 91 /** 92 * Whether the underlying network is directed. By default, the graph is assumed 93 * to be undirected, and links are rendered in both directions. If the network 94 * is directed, then forward links are drawn above the diagonal, while reverse 95 * links are drawn below. 96 * 97 * @type boolean 98 * @name pv.Layout.Rollup.prototype.directed 99 */ 100 101 /** 102 * Specifies the <i>x</i>-position function used to rollup nodes. The rolled up 103 * nodes are positioned horizontally using the return values from the given 104 * function. Typically the function is specified as an ordinal scale. For 105 * single-dimension rollups, a constant value can be specified. 106 * 107 * @param {function} f the <i>x</i>-position function. 108 * @returns {pv.Layout.Rollup} this. 109 * @see pv.Scale.ordinal 110 */ 111 pv.Layout.Rollup.prototype.x = function(f) { 112 this.$x = pv.functor(f); 113 return this; 114 }; 115 116 /** 117 * Specifies the <i>y</i>-position function used to rollup nodes. The rolled up 118 * nodes are positioned vertically using the return values from the given 119 * function. Typically the function is specified as an ordinal scale. For 120 * single-dimension rollups, a constant value can be specified. 121 * 122 * @param {function} f the <i>y</i>-position function. 123 * @returns {pv.Layout.Rollup} this. 124 * @see pv.Scale.ordinal 125 */ 126 pv.Layout.Rollup.prototype.y = function(f) { 127 this.$y = pv.functor(f); 128 return this; 129 }; 130 131 /** @private */ 132 pv.Layout.Rollup.prototype.buildImplied = function(s) { 133 if (pv.Layout.Network.prototype.buildImplied.call(this, s)) return; 134 135 var nodes = s.nodes, 136 links = s.links, 137 directed = s.directed, 138 n = nodes.length, 139 x = [], 140 y = [], 141 rnindex = 0, 142 rnodes = {}, 143 rlinks = {}; 144 145 /** @private */ 146 function id(i) { 147 return x[i] + "," + y[i]; 148 } 149 150 /* Iterate over the data, evaluating the x and y functions. */ 151 var stack = pv.Mark.stack, o = {parent: this}; 152 stack.unshift(null); 153 for (var i = 0; i < n; i++) { 154 o.index = i; 155 stack[0] = nodes[i]; 156 x[i] = this.$x.apply(o, stack); 157 y[i] = this.$y.apply(o, stack); 158 } 159 stack.shift(); 160 161 /* Compute rollup nodes. */ 162 for (var i = 0; i < nodes.length; i++) { 163 var nodeId = id(i), 164 rn = rnodes[nodeId]; 165 if (!rn) { 166 rn = rnodes[nodeId] = pv.extend(nodes[i]); 167 rn.index = rnindex++; 168 rn.x = x[i]; 169 rn.y = y[i]; 170 rn.nodes = []; 171 } 172 rn.nodes.push(nodes[i]); 173 } 174 175 /* Compute rollup links. */ 176 for (var i = 0; i < links.length; i++) { 177 var source = links[i].sourceNode, 178 target = links[i].targetNode, 179 rsource = rnodes[id(source.index)], 180 rtarget = rnodes[id(target.index)], 181 reverse = !directed && rsource.index > rtarget.index, 182 linkId = reverse 183 ? rtarget.index + "," + rsource.index 184 : rsource.index + "," + rtarget.index, 185 rl = rlinks[linkId]; 186 if (!rl) { 187 rl = rlinks[linkId] = { 188 sourceNode: rsource, 189 targetNode: rtarget, 190 linkValue: 0, 191 links: [] 192 }; 193 } 194 rl.links.push(links[i]); 195 rl.linkValue += links[i].linkValue; 196 } 197 198 /* Export the rolled up nodes and links to the scene. */ 199 s.$rollup = { 200 nodes: pv.values(rnodes), 201 links: pv.values(rlinks) 202 }; 203 }; 204