1 /** 2 * Constructs a new, empty arc layout. Layouts are not typically constructed 3 * directly; instead, they are added to an existing panel via 4 * {@link pv.Mark#add}. 5 * 6 * @class Implements a layout for arc diagrams. An arc diagram is a network 7 * visualization with a one-dimensional layout of nodes, using circular arcs to 8 * render links between nodes. For undirected networks, arcs are rendering on a 9 * single side; this makes arc diagrams useful as annotations to other 10 * two-dimensional network layouts, such as rollup, matrix or table layouts. For 11 * directed networks, links in opposite directions can be rendered on opposite 12 * sides using <tt>directed(true)</tt>. 13 * 14 * <p>Arc layouts are particularly sensitive to node ordering; for best results, 15 * order the nodes such that related nodes are close to each other. A poor 16 * (e.g., random) order may result in large arcs with crossovers that impede 17 * visual processing. A future improvement to this layout may include automatic 18 * reordering using, e.g., spectral graph layout or simulated annealing. 19 * 20 * <p>This visualization technique is related to that developed by 21 * M. Wattenberg, <a 22 * href="http://www.research.ibm.com/visual/papers/arc-diagrams.pdf">"Arc 23 * Diagrams: Visualizing Structure in Strings"</a> in <i>IEEE InfoVis</i>, 2002. 24 * However, this implementation is limited to simple node-link networks, as 25 * opposed to structures with hierarchical self-similarity (such as strings). 26 * 27 * <p>As with other network layouts, three mark prototypes are provided:<ul> 28 * 29 * <li><tt>node</tt> - for rendering nodes; typically a {@link pv.Dot}. 30 * <li><tt>link</tt> - for rendering links; typically a {@link pv.Line}. 31 * <li><tt>label</tt> - for rendering node labels; typically a {@link pv.Label}. 32 * 33 * </ul>For more details on how this layout is structured and can be customized, 34 * see {@link pv.Layout.Network}. 35 * 36 * @extends pv.Layout.Network 37 **/ 38 pv.Layout.Arc = function() { 39 pv.Layout.Network.call(this); 40 var interpolate, // cached interpolate 41 directed, // cached directed 42 reverse, // cached reverse 43 buildImplied = this.buildImplied; 44 45 /** @private Cache layout state to optimize properties. */ 46 this.buildImplied = function(s) { 47 buildImplied.call(this, s); 48 directed = s.directed; 49 interpolate = s.orient == "radial" ? "linear" : "polar"; 50 reverse = s.orient == "right" || s.orient == "top"; 51 }; 52 53 /* Override link properties to handle directedness and orientation. */ 54 this.link 55 .data(function(p) { 56 var s = p.sourceNode, t = p.targetNode; 57 return reverse != (directed || (s.breadth < t.breadth)) ? [s, t] : [t, s]; 58 }) 59 .interpolate(function() { return interpolate; }); 60 }; 61 62 pv.Layout.Arc.prototype = pv.extend(pv.Layout.Network) 63 .property("orient", String) 64 .property("directed", Boolean); 65 66 /** 67 * Default properties for arc layouts. By default, the orientation is "bottom". 68 * 69 * @type pv.Layout.Arc 70 */ 71 pv.Layout.Arc.prototype.defaults = new pv.Layout.Arc() 72 .extend(pv.Layout.Network.prototype.defaults) 73 .orient("bottom"); 74 75 /** 76 * Specifies an optional sort function. The sort function follows the same 77 * comparator contract required by {@link pv.Dom.Node#sort}. Specifying a sort 78 * function provides an alternative to sort the nodes as they are specified by 79 * the <tt>nodes</tt> property; the main advantage of doing this is that the 80 * comparator function can access implicit fields populated by the network 81 * layout, such as the <tt>linkDegree</tt>. 82 * 83 * <p>Note that arc diagrams are particularly sensitive to order. This is 84 * referred to as the seriation problem, and many different techniques exist to 85 * find good node orders that emphasize clusters, such as spectral layout and 86 * simulated annealing. 87 * 88 * @param {function} f comparator function for nodes. 89 * @returns {pv.Layout.Arc} this. 90 */ 91 pv.Layout.Arc.prototype.sort = function(f) { 92 this.$sort = f; 93 return this; 94 }; 95 96 /** @private Populates the x, y and angle attributes on the nodes. */ 97 pv.Layout.Arc.prototype.buildImplied = function(s) { 98 if (pv.Layout.Network.prototype.buildImplied.call(this, s)) return; 99 100 var nodes = s.nodes, 101 orient = s.orient, 102 sort = this.$sort, 103 index = pv.range(nodes.length), 104 w = s.width, 105 h = s.height, 106 r = Math.min(w, h) / 2; 107 108 /* Sort the nodes. */ 109 if (sort) index.sort(function(a, b) { return sort(nodes[a], nodes[b]); }); 110 111 /** @private Returns the mid-angle, given the breadth. */ 112 function midAngle(b) { 113 switch (orient) { 114 case "top": return -Math.PI / 2; 115 case "bottom": return Math.PI / 2; 116 case "left": return Math.PI; 117 case "right": return 0; 118 case "radial": return (b - .25) * 2 * Math.PI; 119 } 120 } 121 122 /** @private Returns the x-position, given the breadth. */ 123 function x(b) { 124 switch (orient) { 125 case "top": 126 case "bottom": return b * w; 127 case "left": return 0; 128 case "right": return w; 129 case "radial": return w / 2 + r * Math.cos(midAngle(b)); 130 } 131 } 132 133 /** @private Returns the y-position, given the breadth. */ 134 function y(b) { 135 switch (orient) { 136 case "top": return 0; 137 case "bottom": return h; 138 case "left": 139 case "right": return b * h; 140 case "radial": return h / 2 + r * Math.sin(midAngle(b)); 141 } 142 } 143 144 /* Populate the x, y and mid-angle attributes. */ 145 for (var i = 0; i < nodes.length; i++) { 146 var n = nodes[index[i]], b = n.breadth = (i + .5) / nodes.length; 147 n.x = x(b); 148 n.y = y(b); 149 n.midAngle = midAngle(b); 150 } 151 }; 152 153 /** 154 * The orientation. The default orientation is "left", which means that nodes 155 * will be positioned from left-to-right in the order they are specified in the 156 * <tt>nodes</tt> property. The following orientations are supported:<ul> 157 * 158 * <li>left - left-to-right. 159 * <li>right - right-to-left. 160 * <li>top - top-to-bottom. 161 * <li>bottom - bottom-to-top. 162 * <li>radial - radially, starting at 12 o'clock and proceeding clockwise.</ul> 163 * 164 * @type string 165 * @name pv.Layout.Arc.prototype.orient 166 */ 167 168 /** 169 * Whether this arc digram is directed (bidirectional); only applies to 170 * non-radial orientations. By default, arc digrams are undirected, such that 171 * all arcs appear on one side. If the arc digram is directed, then forward 172 * links are drawn on the conventional side (the same as as undirected 173 * links--right, left, bottom and top for left, right, top and bottom, 174 * respectively), while reverse links are drawn on the opposite side. 175 * 176 * @type boolean 177 * @name pv.Layout.Arc.prototype.directed 178 */ 179