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