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