📄 reweighted_graphs.html
字号:
<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <!--This HTML is auto-generated from an M-file.To make changes, update the M-file and republish this document. --> <title>Reweighted graphs in MatlabBGL</title> <meta name="generator" content="MATLAB 7.5"> <meta name="date" content="2008-10-22"> <meta name="m-file" content="reweighted_graphs"> <link rel="stylesheet" type="text/css" href="../site.css"><style>body { background: white; color: black;}p.footer { text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;}pre.codeinput { margin-left: 20px; margin-top: 10px; margin-bottom: 10px; background-color: #bbbbbb; border: solid 1px; font-size: 10pt; width: 620px;}p{ margin: 10px;}hr{ color: #bbbbbb; height: 4;}.main{ border-left-style: solid; margin-left: 100px; width: 650px;}.upwhitesq{ position: relative; left: -5px; top: -8px; background: white; }.downwhitesq{ position: relative; left: 95px; bottom: 10px; background: white; }img{ text-align: center;}span.keyword {color: #0000FF}span.comment {color: #228B22}span.string {color: #A020F0}span.untermstring {color: #B20000}span.syscmd {color: #B28C00}pre.showbuttons { margin-left: 30px; border: solid black 2px; padding: 4px; background: #EBEFF3;}pre.codeoutput { margin-left: 20px; margin-top: 10px; margin-bottom: 10px; font-size: 10pt; width: 520px;}pre.error { color: red;}.intro { width: 650px;} </style></head> <body> <h1>Reweighted graphs in MatlabBGL</h1> <introduction> <div class="intro"> <p>Matlab sparse matrices only support non-zero values. Because the structure of the sparse matrix is used to infer the edges of an underlying graph this limitation prevents MatlabBGL from trivially addressing graphs with 0-weight edges. </p> <p>To fix this problem, codes that accept a weighted graph allow the user to specify a vector of edge weights for each edge in the graph using the optional 'weights' parameter. Using the 'weights' parameter correctly can be difficult due to issues with how edges are indexed in MatlabBGL. </p> </div> </introduction> <h2>Contents</h2> <div> <ul> <li><a href="#1">Disclaimer</a></li> <li><a href="#2">"I just want the simpliest solution..."</a></li> <li><a href="#10">A first attempt</a></li> <li><a href="#16">A first solution</a></li> <li><a href="#22">A simplified solution</a></li> <li><a href="#26">An undirected solution</a></li> <li><a href="#31">The undirected simplification</a></li> <li><a href="#34">Summary</a></li> </ul> </div> <div class="main"> <h2>Disclaimer<a name="1"></a></h2> <p>The details of this section are complicated. This means their implementation is error-prone. If you get strange behavior, please let me know. </p> <hr> <div class="upwhitesq"> </div> <h2>"I just want the simpliest solution..."<a name="2"></a></h2> <p><b>new in version 4.0</b> In this section, we'll see the really-easy but somewhat expensive way of reweighting a graph. I'll run through all the cases detailed below with the simple code. If you just need something to work and don't necessarily need to know about all the details, this section is for you! </p> <p>Let's compute shortest paths in a cycle graph with only one weighted edge. The simple case requires a structural and weight matrix. </p> <p>n will be the total size of the graph, and u and v will be the special vertices connected with a weight one edge.</p><pre class="codeinput">n = 8; <span class="comment">% it's just an example, so let's make it small.</span>u = 1;v = 2;</pre><p>These commands create an undirected cycle graph. The cycle is ... n <a href="-">-</a> 1 <a href="-">-</a> 2 <a href="-">-</a> ... <a href="-">-</a> n-1 <a href="-">-</a> n <a href="-">-</a> 1 ... where the weight on every edge is 0 except for the edge between vertex u,v. Notice that the edge list is already symmetric. </p> <p>This setup means that while there is a weight 1 edge between u and v, the shortest path, or smallest weight path, is actually the path from u, circling every vertex except v and so d(v) should be 0. </p><pre class="codeinput">E = [1:n 2:n 1; 2:n 1 1:n]';w = [1 zeros(1,n-1) 1 zeros(1,n-1)]';A = sparse(E(:,1), E(:,2), w, n, n); <span class="comment">% create a weighted sparse matrix</span>As = sparse(E(:,1), E(:,2), true, n, n); <span class="comment">% create a structural sparse matrix</span></pre><p>The relationship between As and A is that As should have a non-zero value for every edge, but the values of As will be ignored and the computation will proceed with the values in the corresponding spots in the matrix A.</p> <p>The wrong way to compute shortest paths.</p><pre class="codeinput">[d pred] = shortest_paths(A,u);d(v)</pre><pre class="codeoutput">ans = 1</pre><p>The right way to compute shortest paths.</p><pre class="codeinput">[d pred] = shortest_paths(As,u,struct(<span class="string">'edge_weight'</span>,edge_weight_vector(As,A)));d(v)</pre><pre class="codeoutput">ans = 0</pre><p>That's better, d(v) = 0 as expected.</p> <hr> <div class="upwhitesq"> </div> <h2>A first attempt<a name="10"></a></h2> <div> <ul> <li>Correct for version 3.0 * A trivial example graph to illustrate the problem that occurs with 0 weighted graphs occurs even with a simple cycle. Suppose that the graph corresponding to adjacency matrix A is a symmetric cycle where all edges have weight 0 except for one edge between vertices (1,2). </li> </ul> </div> <p>These commands create an undirected cycle graph. The cycle is ... n <a href="-">-</a> 1 <a href="-">-</a> 2 <a href="-">-</a> ... <a href="-">-</a> n-1 <a href="-">-</a> n <a href="-">-</a> 1 ... where the weight on every edge is 0 except for the edge between vertex u,v. Notice that the edge list is already symmetric. </p><pre class="codeinput">E = [1:n 2:n 1; 2:n 1 1:n]';w = [1 zeros(1,n-1) 1 zeros(1,n-1)]';A = sparse(E(:,1), E(:,2), w, n, n);</pre><p>The shortest weighted path between u and v is then through the vertex n because traversing the cycle in the other direction will use the u,v edge of weight 1. Let's check this with the shortest_paths function. </p><pre class="codeinput">[d pred] = shortest_paths(A,u);d(v)</pre><pre class="codeoutput">ans = 1</pre><p>That is weird, there is a u-v path of length 0 in the graph! Let's see what path the shortest path algorithm chose.</p><pre class="codeinput">path_from_pred(pred,v)</pre><pre class="codeoutput">ans = 1 2</pre><p>The path it chose was from u to v directly, taking the weight 1 edge. Let's look at the sparse matrix.</p><pre class="codeinput">A</pre><pre class="codeoutput">A = (2,1) 1 (1,2) 1</pre><p>There are only two edges in the matrix corresponding to our symmetric weight 1 edge between u and v. This happens because Matlab removes all 0 weight edges from the graph. </p> <hr> <div class="upwhitesq"> </div> <h2>A first solution<a name="16"></a></h2> <p>The solution to the problem is to use the 'edge_weight' optional parameter to the shortest_paths function to give it a set of weights to use for each edge. </p><pre class="codeinput">help <span class="string">shortest_paths</span></pre><pre class="codeoutput"> SHORTEST_PATHS Compute the weighted single source shortest path problem. [d pred] = shortest_paths(A,u) returns the distance (d) and the predecessor (pred) for each of the vertices along the shortest path from u to every other vertex in the graph. ... = shortest_paths(A,u,...) takes a set of key-value pairs or an options structure. See set_matlab_bgl_options for the standard options. options.algname: the algorithm to use [{'auto'} | 'dijkstra' | 'bellman_ford' | 'dag'] options.inf: the value to use for unreachable vertices [double > 0 | {Inf}] options.target: a special vertex that will stop the search when hit [{'none'} | any vertex number besides the u]; target is ignored if visitor is set. options.visitor: a structure with visitor callbacks. This option only applies to dijkstra or bellman_ford algorithms. See dijkstra_sp or bellman_ford_sp for details on the visitors. options.edge_weight: a double array over the edges with an edge weight for each edge, see EDGE_INDEX and EXAMPLES/REWEIGHTED_GRAPHS for information on how to use this option correctly [{'matrix'} | length(nnz(A)) double vector] Note: if you need to compute shortest paths with 0 weight edges, you must use an edge_weight vector, see the examples for details. Note: 'auto' cannot be used with 'nocheck' = 1. The 'auto' algorithm checks if the graph has negative edges and uses bellman_ford in that case, otherwise, it uses 'dijkstra'. In the future, it may check if the graph is a dag and use 'dag'. Example: load graphs/clr-25-2.mat shortest_paths(A,1) shortest_paths(A,1,struct('algname','bellman_ford')) See also DIJKSTRA_SP, BELLMAN_FORD_SP, DAG_SP</pre><p>Well, shortest_paths says to read this document, so you are on the right track! It also has a pointer to the function edge_weight_index. Let's look at that function </p><pre class="codeinput">help <span class="string">edge_weight_index</span></pre><pre class="codeoutput"> EDGE_WEIGHT_INDEX Build a conformal matrix of edge index values for a graph. [eil Ei] = edge_weight_index(As) returns a vector where As(i,j) not= 0 implies Ei(i,j) not= 0 and Ei(i,j) = eil(i) for an integer value of eil(i) that corresponds to the edge index value passed in the visitors. The input matrix A should be a structural matrix with a non-zero value for each edge. The matrix Ei gives an index for each edge in the graph, and the vector eil will reorder a vector of edge weights to an appropriate input for 'edge_weight' parameter of a function call. The edge_weight_index function assists writing codes that use the edge_weight parameter to reweight a graph based on a vector of weights for the graph or using the ei parameter from an edge visitor. It is critical to obtain high performance when i) constructing algorithms that use 0 weighted edges ii) constructing algorithms that change edge weights often. See the examples reweighted_edges and edge_index_visitor for more information. ... = edge_weight_index(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 Note 1. Note 1: For an undirected graph, the edge indices of the edge corresponding to (u,v) and (v,u) are the same. Consequently, Ei is a symmetric matrix, using this option allows only one value for an undirected edge. Example: load('graphs/bfs_example.mat'); [eil Ei] = edge_weight_index(A,struct('undirected',1)); edge_rand = rand(num_edges(A)/2,1); [iu ju] = find(triu(A,0)); Av = sparse(iu,ju,edge_rand,size(A,1),size(A,1)); Av = Av + Av';⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -