1 /** 2 * Constructs a new, empty matrix 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 matrix view. This is, in 7 * effect, a visualization of the graph's <i>adjacency matrix</i>: the cell at 8 * row <i>i</i>, column <i>j</i>, corresponds to the link from node <i>i</i> to 9 * node <i>j</i>. The fill color of each cell is binary by default, and 10 * corresponds to whether a link exists between the two nodes. If the underlying 11 * graph has links with variable values, the <tt>fillStyle</tt> property can be 12 * substited to use an appropriate color function, such as {@link pv.ramp}. 13 * 14 * <p>For undirected networks, the matrix is symmetric around the diagonal. For 15 * directed networks, links in opposite directions can be rendered on opposite 16 * sides of the diagonal using <tt>directed(true)</tt>. The graph is assumed to 17 * be undirected by default. 18 * 19 * <p>The mark prototypes for this network layout are slightly different than 20 * other implementations:<ul> 21 * 22 * <li><tt>node</tt> - unsupported; undefined. No mark is needed to visualize 23 * nodes directly, as the nodes are implicit in the location (rows and columns) 24 * of the links. 25 * 26 * <p><li><tt>link</tt> - for rendering links; typically a {@link pv.Bar}. The 27 * link mark is added directly to the layout, with the data property defined as 28 * all possible pairs of nodes. Each pair is represented as a 29 * {@link pv.Network.Layout.Link}, though the <tt>linkValue</tt> attribute may 30 * be 0 if no link exists in the graph. 31 * 32 * <p><li><tt>label</tt> - for rendering node labels; typically a 33 * {@link pv.Label}. The label mark is added directly to the layout, with the 34 * data property defined via the layout's <tt>nodes</tt> property; note, 35 * however, that the nodes are duplicated so as to provide a label across the 36 * top and down the side. Properties such as <tt>strokeStyle</tt> and 37 * <tt>fillStyle</tt> can be overridden to compute properties from node data 38 * dynamically. 39 * 40 * </ul>For more details on how to use this layout, see 41 * {@link pv.Layout.Network}. 42 * 43 * @extends pv.Layout.Network 44 */ 45 pv.Layout.Matrix = function() { 46 pv.Layout.Network.call(this); 47 var that = this, 48 n, // cached matrix size 49 dx, // cached cell width 50 dy, // cached cell height 51 labels, // cached labels (array of strings) 52 pairs, // cached pairs (array of links) 53 buildImplied = that.buildImplied; 54 55 /** @private Cache layout state to optimize properties. */ 56 this.buildImplied = function(s) { 57 buildImplied.call(this, s); 58 n = s.nodes.length; 59 dx = s.width / n; 60 dy = s.height / n; 61 labels = s.$matrix.labels; 62 pairs = s.$matrix.pairs; 63 }; 64 65 /* Links are all pairs of nodes. */ 66 this.link 67 .data(function() { return pairs; }) 68 .left(function() { return dx * (this.index % n); }) 69 .top(function() { return dy * Math.floor(this.index / n); }) 70 .width(function() { return dx; }) 71 .height(function() { return dy; }) 72 .lineWidth(1.5) 73 .strokeStyle("#fff") 74 .fillStyle(function(l) { return l.linkValue ? "#555" : "#eee"; }) 75 .parent = this; 76 77 /* No special add for links! */ 78 delete this.link.add; 79 80 /* Labels are duplicated for top & left. */ 81 this.label 82 .data(function() { return labels; }) 83 .left(function() { return this.index & 1 ? dx * ((this.index >> 1) + .5) : null; }) 84 .top(function() { return this.index & 1 ? null : dy * ((this.index >> 1) + .5); }) 85 .textMargin(4) 86 .textAlign(function() { return this.index & 1 ? "left" : "right"; }) 87 .textAngle(function() { return this.index & 1 ? -Math.PI / 2 : 0; }); 88 89 /* The node mark is unused. */ 90 delete this.node; 91 }; 92 93 pv.Layout.Matrix.prototype = pv.extend(pv.Layout.Network) 94 .property("directed", Boolean); 95 96 /** 97 * Whether this matrix visualization is directed (bidirectional). By default, 98 * the graph is assumed to be undirected, such that the visualization is 99 * symmetric across the matrix diagonal. If the network is directed, then 100 * forward links are drawn above the diagonal, while reverse links are drawn 101 * below. 102 * 103 * @type boolean 104 * @name pv.Layout.Matrix.prototype.directed 105 */ 106 107 /** 108 * Specifies an optional sort function. The sort function follows the same 109 * comparator contract required by {@link pv.Dom.Node#sort}. Specifying a sort 110 * function provides an alternative to sort the nodes as they are specified by 111 * the <tt>nodes</tt> property; the main advantage of doing this is that the 112 * comparator function can access implicit fields populated by the network 113 * layout, such as the <tt>linkDegree</tt>. 114 * 115 * <p>Note that matrix visualizations are particularly sensitive to order. This 116 * is referred to as the seriation problem, and many different techniques exist 117 * to find good node orders that emphasize clusters, such as spectral layout and 118 * simulated annealing. 119 * 120 * @param {function} f comparator function for nodes. 121 * @returns {pv.Layout.Matrix} this. 122 */ 123 pv.Layout.Matrix.prototype.sort = function(f) { 124 this.$sort = f; 125 return this; 126 }; 127 128 /** @private */ 129 pv.Layout.Matrix.prototype.buildImplied = function(s) { 130 if (pv.Layout.Network.prototype.buildImplied.call(this, s)) return; 131 132 var nodes = s.nodes, 133 links = s.links, 134 sort = this.$sort, 135 n = nodes.length, 136 index = pv.range(n), 137 labels = [], 138 pairs = [], 139 map = {}; 140 141 s.$matrix = {labels: labels, pairs: pairs}; 142 143 /* Sort the nodes. */ 144 if (sort) index.sort(function(a, b) { return sort(nodes[a], nodes[b]); }); 145 146 /* Create pairs. */ 147 for (var i = 0; i < n; i++) { 148 for (var j = 0; j < n; j++) { 149 var a = index[i], 150 b = index[j], 151 p = { 152 row: i, 153 col: j, 154 sourceNode: nodes[a], 155 targetNode: nodes[b], 156 linkValue: 0 157 }; 158 pairs.push(map[a + "." + b] = p); 159 } 160 } 161 162 /* Create labels. */ 163 for (var i = 0; i < n; i++) { 164 var a = index[i]; 165 labels.push(nodes[a], nodes[a]); 166 } 167 168 /* Accumulate link values. */ 169 for (var i = 0; i < links.length; i++) { 170 var l = links[i], 171 source = l.sourceNode.index, 172 target = l.targetNode.index, 173 value = l.linkValue; 174 map[source + "." + target].linkValue += value; 175 if (!s.directed) map[target + "." + source].linkValue += value; 176 } 177 }; 178