reweighted_graphs.html

模型参考自适应程序。用于无速度传感器

    ee = @(ei,u,v) fprintf('examine_edge %2i, %1i, %1i, %4f, %4f, %4f\n', ...
                ei, u, v, edge_rand(eil(ei)), Av(u,v), edge_rand(Ei(u,v)));
    breadth_first_search(A,1,struct('examine_edge', ee));
 
  See also INDEXED_SPARSE

</pre><p>This function claims to help us.  It requires building a structural matrix which has a non-zero for each edge in the graph.
             Let's do that.
         </p><pre class="codeinput">As = sparse(E(:,1), E(:,2), 1, n, n)
</pre><pre class="codeoutput">
As =

   (2,1)        1
   (8,1)        1
   (1,2)        1
   (3,2)        1
   (2,3)        1
   (4,3)        1
   (3,4)        1
   (5,4)        1
   (4,5)        1
   (6,5)        1
   (5,6)        1
   (7,6)        1
   (6,7)        1
   (8,7)        1
   (1,8)        1
   (7,8)        1

</pre><p>Now the matrix has all of the required edges.  According to the edge_weight_index function, it returns both a matrix and an
            index vector. The index vector is a way to permute an intelligently ordered set of edge weights to the order that MatlabBGL
            requires the edge weights.
         </p><pre class="codeinput">[ei Ei] = edge_weight_index(As);

full(Ei)
ei
</pre><pre class="codeoutput">
ans =

     0     3     0     0     0     0     0    15
     1     0     5     0     0     0     0     0
     0     4     0     7     0     0     0     0
     0     0     6     0     9     0     0     0
     0     0     0     8     0    11     0     0
     0     0     0     0    10     0    13     0
     0     0     0     0     0    12     0    16
     2     0     0     0     0     0    14     0


ei =

     3
    15
     1
     5
     4
     7
     6
     9
     8
    11
    10
    13
    12
    16
     2
    14

</pre><p>Now let's create a new edge weight vector for this graph corresponding to all the edges we want.  Each non-zero in the matrix
            should have an associated edge weight.  Most the edge weights in this case are 0, so it makes it simple.
         </p><pre class="codeinput">ew = zeros(nnz(As),1);
ew(Ei(u,v)) = 1;
ew(Ei(v,u)) = 1;

[d pred] = shortest_paths(As,u,struct(<span class="string">'edge_weight'</span>, ew(ei)));

path_from_pred(pred,v)
</pre><pre class="codeoutput">
ans =

     1     8     7     6     5     4     3     2

</pre><p>Excellent, now the shorest path avoids the edge (u,v) as we would expect it.</p>
         <hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>A simplified solution<a name="22"></a></h2>
         <p>The current example is somewhat tedious because we have to create the sparse matrix, then create the edge index matrix, and
            finally create and edit the edge weight array.
         </p>
         <p>The indexed_sparse function makes the process easier.</p>
         <p>Recall that using the sparse function directly generated an incorrect graph adjacency matrix.</p><pre class="codeinput">A = sparse(E(:,1), E(:,2), w, n, n)
</pre><pre class="codeoutput">
A =

   (2,1)        1
   (1,2)        1

</pre><p>The indexed_sparse function is designed as a replacement for sparse where the adjacency matrix must be indexed using the edge_weight_index
            or contains 0 weight edges.
         </p><pre class="codeinput">help <span class="string">indexed_sparse</span>
</pre><pre class="codeoutput">  INDEXED_SPARSE Create a sparse matrix with indexed edges.
 
  [As,A,eil,Ei] = indexed_sparse(i,j,v,m,n) creates a sparse matrix A just
  like A = sparse(i,j,v,m,n).  However, indexed_sparse returns additional
  information.  The matrix As is a structural matrix for A which
  corresponds to As = sparse(i,j,1,m,n).  Thus, As(i,j) != 0 for all edges.
  The vector eil is a permutation for the vector v, such that v(eil) is the
  correct input for the edge_weight parameter.  The matrix Ei lists the
  index of each edge in the vector v, so that 
  A = sparse(j,i,v(nonzeros(Ei)),m,n)' unless options.istrans = 0.  
 
  This function handles the case when v(k) == 0.  For v(k) = 0,
  A(i(k),j(k)) = 0, but As(i(k),j(k)) = 1, and the vector v(eil) provides
  an appropriate input to the edge_weight parameter for all the algorithms.
   
  See the examples reweighted_edges for more information.
 
  ... = indexed_sparse(A,...) takes a set of
  key-value pairs or an options structure.  See set_matlab_bgl_options
  for the standard options. 
     options.undirected: output edge indices for an undirected graph [{0} | 1]
       See the note about undirected inputs.
 
  Note (Undirected inputs): If options.undirected = 1, the input to the
  graph still must contain both undirected edges and the corresponding
  weight.  
 
  Example:
    % see example/reweighted_edges 

</pre><p>From the documentation of indexed_sparse, the first two return values are the structural sparse matrix (As) and the sparse
            matrix (A) that sparse would have returned.  The final two return values are the edge index list that edge_weight_index returns
            as well as the edge index matrix.
         </p><pre class="codeinput"><span class="comment">% save the old Ei as an example</span>
old_Ei = Ei;

[As A eil Ei] = indexed_sparse(E(:,1), E(:,2), w, n, n);

fprintf(<span class="string">'old_Ei = \n\n'</span>);
disp(full(old_Ei));
fprintf(<span class="string">'Ei = \n\n'</span>);
disp(full(Ei))
</pre><pre class="codeoutput">old_Ei = 

     0     3     0     0     0     0     0    15
     1     0     5     0     0     0     0     0
     0     4     0     7     0     0     0     0
     0     0     6     0     9     0     0     0
     0     0     0     8     0    11     0     0
     0     0     0     0    10     0    13     0
     0     0     0     0     0    12     0    16
     2     0     0     0     0     0    14     0

Ei = 

     0     1     0     0     0     0     0    16
     9     0     2     0     0     0     0     0
     0    10     0     3     0     0     0     0
     0     0    11     0     4     0     0     0
     0     0     0    12     0     5     0     0
     0     0     0     0    13     0     6     0
     0     0     0     0     0    14     0     7
     8     0     0     0     0     0    15     0

</pre><p>Note that the edge indices changed between the two calls.  The reason for this change is that indexed_sparse generates edge
            indices based on order of E(:,1) and E(:,2).  Consequently, this function is much easier to use when you already have a set
            of weighted edges.
         </p>
         <p>In this case, we don't have to create the ew array again!  (Note that the call uses eil instead of ei.)</p><pre class="codeinput">[d pred] = shortest_paths(As,u,struct(<span class="string">'edge_weight'</span>, w(eil)));

path_from_pred(pred,v)
</pre><pre class="codeoutput">
ans =

     1     8     7     6     5     4     3     2

</pre><hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>An undirected solution<a name="26"></a></h2>
         <p>The situation for undirected graphs is more complicated.  The trouble with the previous solution is that each directed edge
            had its own weight in the vector w.  For an undirected graph, we really want each undirected edge to have a single weight,
            so the natural length of v would be nnz(A)/2 instead of nnz(A).
         </p>
         <p>However, MatlabBGL really treats all problems as directed graphs, so it will need a vector w of length nnz(A), but that vector
            should satisfy the requirement w(ei1) = w(ei2) if the edges corresponding to ei1 and ei2 are (i,j) and (j,i), respectively.
         </p>
         <p>Again, the edge_weight_index function provides a solution to this problem.  We just have to tell edge_weight_index we have
            an undirected graph.
         </p>
         <p>Let's start with the same sparse matrix</p><pre class="codeinput">As = sparse(E(:,1), E(:,2), 1, n, n)
</pre><pre class="codeoutput">
As =

   (2,1)        1
   (8,1)        1
   (1,2)        1
   (3,2)        1
   (2,3)        1
   (4,3)        1
   (3,4)        1
   (5,4)        1
   (4,5)        1
   (6,5)        1
   (5,6)        1
   (7,6)        1
   (6,7)        1
   (8,7)        1
   (1,8)        1
   (7,8)        1

</pre><p>Here we use the edge_weight_index</p><pre class="codeinput">[ei Ei] = edge_weight_index(As,struct(<span class="string">'undirected'</span>,1));
full(Ei) <span class="comment">% look at the matrix</span>
</pre><pre class="codeoutput">
ans =

     0     1     0     0     0     0     0     7
     1     0     2     0     0     0     0     0
     0     2     0     3     0     0     0     0
     0     0     3     0     4     0     0     0
     0     0     0     4     0     5     0     0
     0     0     0     0     5     0     6     0
     0     0     0     0     0     6     0     8
     7     0     0     0     0     0     8     0

</pre><p>Let's create the edge weight vector</p><pre class="codeinput">ew = zeros(nnz(As)/2,1); <span class="comment">% only half as many zeros here.</span>
ew(Ei(u,v)) = 1; <span class="comment">% and we only needed to set one entry to 0</span>

[d pred] = shortest_paths(As,u,struct(<span class="string">'edge_weight'</span>, ew(ei)));

path_from_pred(pred,v)
</pre><pre class="codeoutput">
ans =

     1     8     7     6     5     4     3     2

</pre><p>And we get the same output as before!</p>
         <hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>The undirected simplification<a name="31"></a></h2>
         <p>You can probably guess that the simplification for undirected graphs will use the indexed_sparse call again too.</p><pre class="codeinput">help <span class="string">indexed_sparse</span>
</pre><pre class="codeoutput">  INDEXED_SPARSE Create a sparse matrix with indexed edges.
 
  [As,A,eil,Ei] = indexed_sparse(i,j,v,m,n) creates a sparse matrix A just
  like A = sparse(i,j,v,m,n).  However, indexed_sparse returns additional
  information.  The matrix As is a structural matrix for A which
  corresponds to As = sparse(i,j,1,m,n).  Thus, As(i,j) != 0 for all edges.
  The vector eil is a permutation for the vector v, such that v(eil) is the
  correct input for the edge_weight parameter.  The matrix Ei lists the
  index of each edge in the vector v, so that 
  A = sparse(j,i,v(nonzeros(Ei)),m,n)' unless options.istrans = 0.  
 
  This function handles the case when v(k) == 0.  For v(k) = 0,
  A(i(k),j(k)) = 0, but As(i(k),j(k)) = 1, and the vector v(eil) provides
  an appropriate input to the edge_weight parameter for all the algorithms.
   
  See the examples reweighted_edges for more information.
 
  ... = indexed_sparse(A,...) takes a set of
  key-value pairs or an options structure.  See set_matlab_bgl_options
  for the standard options. 
     options.undirected: output edge indices for an undirected graph [{0} | 1]
       See the note about undirected inputs.
 
  Note (Undirected inputs): If options.undirected = 1, the input to the
  graph still must contain both undirected edges and the corresponding
  weight.  
 
  Example:
    % see example/reweighted_edges 

</pre><p>From the documentation, we find that indexed_sparse has an option called "undirected" which is set to 0 by default.</p><pre class="codeinput">[As A eil Ei] = indexed_sparse(E(:,1), E(:,2), w, n, n, struct(<span class="string">'undirected'</span>,1));

fprintf(<span class="string">'Ei = \n\n'</span>);
disp(full(Ei))
</pre><pre class="codeoutput">Ei = 

     0     1     0     0     0     0     0     8
     1     0     2     0     0     0     0     0
     0     2     0     3     0     0     0     0
     0     0     3     0     4     0     0     0
     0     0     0     4     0     5     0     0
     0     0     0     0     5     0     6     0
     0     0     0     0     0     6     0     7
     8     0     0     0     0     0     7     0

</pre><p>In this case, the indexed_sparse routine only issued edge indices that were between 1 and 8, rather than 1 and 16 as in the
            previous case.
         </p><pre class="codeinput">[d pred] = shortest_paths(As,u,struct(<span class="string">'edge_weight'</span>, w(eil)));

path_from_pred(pred,v)
</pre><pre class="codeoutput">
ans =

     1     8     7     6     5     4     3     2

</pre><hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>Summary<a name="34"></a></h2>
         <p>The functions that support reweighted edges as of MatlabBGL 3.0 are shortest_paths, all_shortest_paths, dijkstra_sp, bellman_ford_sp,
            dag_sp, betweenness_centrality, astar_search, johnson_all_sp, floyd_warshall_all_sp, mst, kruskal_mst, and prim_mst.  Note
            that max_flow does not support these indices.
         </p>