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