Homec4science
Diffusion EMPoWER (master) Browse

R1252/simulation-code/cvx/examples/cvxbook/Ch08_geometric_probs/html/floorplan.html
de096106547amaster

Last Change
Raw File

floorplan.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Computes a minimum-perimeter bounding box subject to positioning constraints</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/cvxbook/Ch08_geometric_probs/html/floorplan.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Computes a minimum-perimeter bounding box subject to positioning constraints</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
Text output
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="keyword">function</span> [W, H, w, h, x, y] = floorplan(adj_H, adj_V, rho, Amin, l, u )
<span class="comment">% Inputs:</span>
<span class="comment">% adj_H,adj_V: adjacency matrices</span>
<span class="comment">% Amin: minimum spacing: w_i * h_i &gt;= Amin</span>
<span class="comment">% rho: boundaries: rho &lt;= x_i &lt;= W-rho, rho &lt;= y_i &lt;= H-rho</span>
<span class="comment">% l, u: aspect ratio constraints: l_i &lt;= h_i/w_i &lt;= u_i</span>
<span class="comment">% Only adj_H and adj_V are required; the rest are optional. If n is the</span>
<span class="comment">% number of cells, then adj_H and adj_V must be nxn matrices, and Amin,</span>
<span class="comment">% l, and u must be vectors of length n. rho must be a scalar. The default</span>
<span class="comment">% values of rho and Amin are 0.</span>
<span class="comment">% Joelle Skaf - 12/04/05</span>
<span class="keyword">if</span> nargin &lt; 2
error(<span class="string">'Insufficient number of input arguments'</span>);
<span class="keyword">end</span>
[n1, n2] = size(adj_H);
[m1, m2] = size(adj_V);
<span class="keyword">if</span> n1~=n2
error(<span class="string">'Input adjacency matrix for horizontal graph must be square'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> m1~=m2
error(<span class="string">'Input adjacency matrix for horizontal graph must be square'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> n1~=m1
error(<span class="string">'Input adjacency matrices must be of the same size'</span>);
<span class="keyword">end</span>
n = n1; <span class="comment">% number of cells</span>
<span class="keyword">if</span> nargin &lt;3
rho = 0;
<span class="keyword">end</span>
<span class="keyword">if</span> nargin &lt;4
Amin = zeros(1,n);
<span class="keyword">else</span>
<span class="keyword">if</span> min(size(Amin)) ~=1
error(<span class="string">'Amin should be a vector'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> max(size(Amin)) ~= n
error(<span class="string">'Amin should have the same length as the input graphs'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> size(Amin,1)~=1
Amin = Amin';
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">if</span> nargin == 5
<span class="keyword">if</span> min(size(1)) ~= 1
error(<span class="string">'l must be a vector'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> max(size(l)) ~= n
error(<span class="string">'the vector l must have same length as the input graphs'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> size(l,1) == 1
l = l';
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">if</span> nargin == 6
<span class="keyword">if</span> min(size(1)) ~= 1
error(<span class="string">'u must be a vector'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> max(size(u)) ~= n
error(<span class="string">'the vector u must have same length as the input graphs'</span>);
<span class="keyword">end</span>
<span class="keyword">if</span> size(u,1) == 1
u = u';
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">if</span> nargin &lt; 6
u = [];
<span class="keyword">end</span>
<span class="keyword">if</span> nargin &lt; 5
l = [];
<span class="keyword">end</span>
<span class="comment">% verifying that there is a directed path between any pair of cells in at</span>
<span class="comment">% least one of the 2 graphs</span>
paths_H = adj_H;
paths_V = adj_V;
temp_H = adj_H^2;
temp_V = adj_V^2;
<span class="keyword">while</span> (sum(temp_H(:))&gt;0)
paths_H = paths_H + temp_H;
temp_H = temp_H*adj_H;
<span class="keyword">end</span>
<span class="keyword">while</span> (sum(temp_V(:))&gt;0)
paths_V = paths_V + temp_V;
temp_V = temp_V*adj_V;
<span class="keyword">end</span>
hh = paths_H + paths_H';
vv = paths_V + paths_V';
p = hh+vv+eye(n);
all_paths = p&gt;0;
<span class="keyword">if</span> sum(all_paths(:)) ~= n^2
error(<span class="string">'There must be a directed graph between every pair of cells in one or the other input graphs'</span>);
<span class="keyword">end</span>
par_H = sum(adj_H,2); <span class="comment">% number of parents of each node in H</span>
par_V = sum(adj_V,2); <span class="comment">% number of parents of each node in V</span>
chi_H = sum(adj_H); <span class="comment">% number of children of each node in H</span>
chi_V = sum(adj_V); <span class="comment">% number of children of each node in V</span>
<span class="comment">% find the root(s) for each tree</span>
roots_H = find(par_H==0);
roots_V = find(par_V==0);
<span class="comment">% find all non-root nodes for each tree</span>
nodes_H = find(par_H&gt;0);
nodes_V = find(par_V&gt;0);
<span class="comment">% find leaf(s) for each tree</span>
leafs_H = find(chi_H==0);
leafs_V = find(chi_V==0);
cvx_begin <span class="string">quiet</span>
variables <span class="string">x(n)</span> <span class="string">y(n)</span> <span class="string">w(n)</span> <span class="string">h(n)</span> <span class="string">W</span> <span class="string">H</span>
minimize ( W + H )
w &gt;= 0;
h &gt;= 0;
x(leafs_H) &gt;= rho;
y(leafs_V) &gt;= rho;
x(roots_H) + w(roots_H) + rho &lt;= W;
y(roots_V) + h(roots_V) + rho &lt;= H;
<span class="keyword">for</span> i=1:length(nodes_H)
node = nodes_H(i);
c = adj_H(node,:);
prnt = find(c&gt;0)';
m = length(prnt);
x(node) + w(node) + rho &lt;= x(prnt);
<span class="keyword">end</span>
<span class="keyword">for</span> i=1:length(nodes_V)
node = nodes_V(i);
c = adj_V(node,:);
prnt = find(c&gt;0)';
m = length(prnt);
y(node) + h(node) + rho &lt;= y(prnt);
<span class="keyword">end</span>
<span class="keyword">if</span> sum(size(u))~= 0
h &lt;= u.*w;
<span class="keyword">end</span>
<span class="keyword">if</span> sum(size(l))~= 0
h &gt;= l.*w;
<span class="keyword">end</span>
w' &gt;= quad_over_lin([Amin.^.5;zeros(1,n)],h');
cvx_end
</pre>
</div>
</body>
</html>
c4science · Help